The Littlewood-Offord problem and invertibility of random matrices.(English)Zbl 1139.15015
Summary: We prove two basic conjectures on the distribution of the smallest singular value of random \(n\times n\) matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order \(n^{ - 1/2}\), which is optimal for Gaussian matrices. Moreover, we give an optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables \(X_k\) and real numbers \(a_k\), determine the probability \(p\) that the sum \(\sum_ka_kX_k\) lies near some number \(v\). For arbitrary coefficients \(a_k\) of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length \(1/p\).
Cite
References:
| [1] | Bai, Z. D.; Silverstein, J.; Yin, Y. Q., A note on the largest eigenvalue of a large-dimensional sample covariance matrix, J. Multivariate Anal., 26, 166-168 (1988) ·Zbl 0652.60040 |
| [2] | Bollobás, B., Combinatorics. Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge ·Zbl 0595.05001 |
| [3] | Candes, E. J.; Tao, T., Near-optimal signal recovery from random projections: Universal encoding strategies, IEEE Trans. Inform. Theory, 52, 5406-5425 (2004) ·Zbl 1309.94033 |
| [4] | Davidson, K.; Szarek, S. J., Local operator theory, random matrices and Banach spaces, (Handbook of the Geometry of Banach Spaces, vol. I (2001), North-Holland: North-Holland Amsterdam), 317-366 ·Zbl 1067.46008 |
| [5] | Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 1289-1306 (2006) ·Zbl 1288.94016 |
| [6] | Edelman, A., Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9, 543-560 (1988) ·Zbl 0678.15019 |
| [7] | Erdös, P., On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 51, 898-902 (1945) ·Zbl 0063.01270 |
| [8] | Erdös, P., Extremal problems in number theory, (Proc. Sympos. Pure Math., vol. VIII (1965), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 181-189 ·Zbl 0144.28103 |
| [9] | Esseen, C. G., On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 5, 210-216 (1966) ·Zbl 0142.14702 |
| [10] | Frankl, P.; Füredi, Z., Solution of the Littlewood-Offord problem in high dimensions, Ann. of Math. (2), 128, 2, 259-270 (1988) ·Zbl 0667.05017 |
| [11] | Halász, G., On the distribution of additive arithmetic functions, Acta Arith., 27, 143-152 (1975) ·Zbl 0256.10028 |
| [12] | Halász, G., Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar., 8, 197-211 (1977) ·Zbl 0336.10050 |
| [13] | Kahn, J.; Komlós, J.; Szemerédi, E., On the probability that a random ±1-matrix is singular, J. Amer. Math. Soc., 8, 1, 223-240 (1995) ·Zbl 0829.15018 |
| [14] | Komlós, J., On the determinant of \((0, 1)\) matrices, Studia Sci. Math. Hungar., 2, 7-21 (1967) ·Zbl 0153.05002 |
| [15] | Latala, R., Some estimates of norms of random matrices, Proc. Amer. Math. Soc., 133, 1273-1282 (2005) ·Zbl 1067.15022 |
| [16] | Ledoux, M.; Talagrand, M., Probability in Banach Spaces. Isoperimetry and Processes, Ergeb. Math. Grenzgeb. (3), vol. 23 (1991), Springer-Verlag: Springer-Verlag Berlin ·Zbl 0748.60004 |
| [17] | Li, W. V.; Shao, Q.-M., Gaussian processes: Inequalities, small ball probabilities and applications, (Stochastic Processes: Theory and Methods. Stochastic Processes: Theory and Methods, Handbook of Statist., vol. 19 (2001), North-Holland: North-Holland Amsterdam), 533-597 ·Zbl 0987.60053 |
| [18] | Litvak, A. E.; Pajor, A.; Rudelson, M.; Tomczak-Jaegermann, N., Smallest singular value of random matrices and geometry of random polytopes, Adv. Math., 195, 491-523 (2005) ·Zbl 1077.15021 |
| [19] | Milman, V. D.; Schechtman, G., Asymptotic Theory of Finite-Dimensional Normed Spaces, Lecture Notes in Math., vol. 1200 (1986), Springer-Verlag: Springer-Verlag Berlin, with an appendix by M. Gromov ·Zbl 0911.52002 |
| [20] | Odlyzko, A. M., On subspaces spanned by random selections of ±1 vectors, J. Combin. Theory Ser. A, 47, 124-133 (1988) ·Zbl 0664.05004 |
| [21] | G. Pan, W. Zhou, Circular law, extreme singular values and potential theory, preprint; G. Pan, W. Zhou, Circular law, extreme singular values and potential theory, preprint ·Zbl 1203.60011 |
| [22] | M. Rudelson, Invertibility of random matrices: Norm of the inverse, Ann. of Math., in press; M. Rudelson, Invertibility of random matrices: Norm of the inverse, Ann. of Math., in press ·Zbl 1175.15030 |
| [23] | Sárközy, A.; Szemerédi, E., Über ein Problem von Erdös und Moser, Acta Arith., 11, 205-208 (1965) ·Zbl 0134.27801 |
| [24] | Smale, S., On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.), 13, 87-121 (1985) ·Zbl 0592.65032 |
| [25] | Soshnikov, A., A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices, J. Stat. Phys., 108, 1033-1056 (2002) ·Zbl 1018.62042 |
| [26] | Spielman, D.; Teng, S.-H., Smoothed analysis of algorithms, (Proceedings of the International Congress of Mathematicians, vol. I. Proceedings of the International Congress of Mathematicians, vol. I, Beijing, 2002 (2002), Higher Ed. Press: Higher Ed. Press Beijing), 597-606 ·Zbl 1056.65148 |
| [27] | Stroock, D. W., Probability Theory, an Analytic View (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge ·Zbl 0925.60004 |
| [28] | Szarek, S., Condition numbers of random matrices, J. Complexity, 7, 2, 131-149 (1991) ·Zbl 0760.15018 |
| [29] | Tao, T.; Vu, V., On random ±1 matrices: Singularity and determinant, Random Structures Algorithms, 28, 1-23 (2006) ·Zbl 1086.60008 |
| [30] | Tao, T.; Vu, V., On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc., 20, 603-628 (2007) ·Zbl 1116.15021 |
| [31] | T. Tao, V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. of Math., in press; T. Tao, V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. of Math., in press ·Zbl 1250.60023 |
| [32] | von Neumann, J., Collected Works, vol. V: Design of Computers, Theory of Automata and Numerical Analysis (1963), Pergamon Press Book, The Macmillan Co.: Pergamon Press Book, The Macmillan Co. New York, general editor: A.H. Taub ·Zbl 0188.00104 |
| [33] | Yin, Y. Q.; Bai, Z. D.; Krishnaiah, P. R., On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix, Probab. Theory Related Fields, 78, 509-521 (1988) ·Zbl 0627.62022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
