Lower bounds for the smallest singular value of structured random matrices. (English) Zbl 1426.60006

Summary: We obtain lower tail estimates for the smallest singular value of random matrices with independent but nonidentically distributed entries. Specifically, we consider \(n\times n\) matrices with complex entries of the form
\[ M=A\circ X+B=(a_{ij}\xi_{ij}+b_{ij}), \] where \(X=(\xi_{ij})\) has i.i.d. centered entries of unit variance and \(A\) and \(B\) are fixed matrices. In our main result, we obtain polynomial bounds on the smallest singular value of \(M\) for the case that \(A\) has bounded (possibly zero) entries, and \(B=Z\sqrt{n}\) where \(Z\) is a diagonal matrix with entries bounded away from zero. As a byproduct of our methods we can also handle general perturbations \(B\) under additional hypotheses on \(A\), which translate to connectivity hypotheses on an associated graph. In particular, we extend a result of M. Rudelson and O. Zeitouni [Random Struct. Algorithms 48, No. 1, 183–212 (2016; Zbl 1362.15028)] for Gaussian matrices to allow for general entry distributions satisfying some moment hypotheses. Our proofs make use of tools which (to our knowledge) were previously unexploited in random matrix theory, in particular Szemerédi’s regularity lemma, and a version of the restricted invertibility theorem due to D. A. Spielman and N. Srivastava [Isr. J. Math. 190, 83–91 (2012; Zbl 1261.46007)].


60B20 Random matrices (probabilistic aspects)
15B52 Random matrices (algebraic aspects)
Full Text: DOI arXiv Euclid


[1] Aljadeff, J., Renfrew, D. and Stern, M. (2015). Eigenvalues of block structured asymmetric random matrices. J. Math. Phys.56 103502. · Zbl 1327.15073
[2] Alon, N. and Shapira, A. (2004). Testing subgraphs in directed graphs. J. Comput. System Sci.69 353–382. · Zbl 1084.68087
[3] Anderson, G. W., Guionnet, A. and Zeitouni, O. (2010). An Introduction to Random Matrices. Cambridge Studies in Advanced Mathematics118. Cambridge Univ. Press, Cambridge. · Zbl 1184.15023
[4] Bai, Z. D., Silverstein, J. W. and Yin, Y. Q. (1988). A note on the largest eigenvalue of a large-dimensional sample covariance matrix. J. Multivariate Anal.26 166–168. · Zbl 0652.60040
[5] Bandeira, A. S. and van Handel, R. (2016). Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Ann. Probab.44 2479–2506. · Zbl 1372.60004
[6] Bordenave, C. and Chafaï, D. (2012). Around the circular law. Probab. Surv.9 1–89. · Zbl 1243.15022
[7] Bourgade, P., Erdos, L., Yau, H.-T. and Yin, J. Universality for a class of random band matrices. Preprint. Available at arXiv:1602.02312. · Zbl 1381.15029
[8] Bourgain, J. and Tzafriri, L. (1987). Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis. Israel J. Math.57 137–224. · Zbl 0631.46017
[9] Cook, N. (2018). Supplement to “Lower bounds for the smallest singular value of structured random matrices.” DOI:10.1214/17-AOP1251SUPP.
[10] Cook, N. A., Hachem, W., Najim, J. and Renfrew, D. Limiting spectral distribution for non-Hermitian random matrices with a variance profile. Preprint. Available at arXiv:1612.04428. · Zbl 1401.60008
[11] Edelman, A. (1988). Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl.9 543–560. · Zbl 0678.15019
[12] Gowers, W. T. (1997). Lower bounds of tower type for Szemerédi’s uniformity lemma. Geom. Funct. Anal.7 322–337. · Zbl 0876.05053
[13] Hachem, W., Loubaton, P. and Najim, J. (2007). Deterministic equivalents for certain functionals of large random matrices. Ann. Appl. Probab.17 875–930. · Zbl 1181.15043
[14] Komlós, J. Circulated manuscript, 1977. Edited version available online at http://www.math.rutgers.edu/ komlos/01short.pdf.
[15] Komlós, J. (1967). On the determinant of \((0,1)\) matrices. Studia Sci. Math. Hungar.2 7–21.
[16] Komlós, J. (1968). On the determinant of random matrices. Studia Sci. Math. Hungar.3 387–399.
[17] Komlós, J. and Simonovits, M. (1996). Szemerédi’s regularity lemma and its applications in graph theory. In Combinatorics, Paul Erdős Is Eighty, Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud.2 295–352. János Bolyai Math. Soc., Budapest.
[18] Latała, R. (2005). Some estimates of norms of random matrices. Proc. Amer. Math. Soc.133 1273–1282. · Zbl 1067.15022
[19] Litvak, A. E., Lytova, A., Tikhomirov, K., Tomczak-Jaegermann, N. and Youssef, P. (2017). Adjacency matrices of random digraphs: Singularity and anti-concentration. J. Math. Anal. Appl.445 1447–1491. · Zbl 1344.05126
[20] Litvak, A. E., Pajor, A., Rudelson, M. and Tomczak-Jaegermann, N. (2005). Smallest singular value of random matrices and geometry of random polytopes. Adv. Math.195 491–523. · Zbl 1077.15021
[21] Litvak, A. E., Pajor, A., Rudelson, M., Tomczak-Jaegermann, N. and Vershynin, R. (2005). Euclidean embeddings in spaces of finite volume ratio via random matrices. J. Reine Angew. Math.589 1–19. · Zbl 1090.52002
[22] Litvak, A. E. and Rivasplata, O. (2012). Smallest singular value of sparse random matrices. Studia Math.212 195–218. · Zbl 1277.60016
[23] Marcus, A. W., Spielman, D. A. and Srivastava, N. (2014). Ramanujan graphs and the solution of the Kadison–Singer problem. In Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. III 363–386. Kyung Moon Sa, Seoul. · Zbl 1373.05108
[24] Nguyen, H. H. and Vu, V. H. (2018). Normal vector of a random hyperplane. International Mathematics Research Notices2018 1754-1778.
[25] Rajan, K. and Abbott, L. F. (2006). Eigenvalue spectra of random matrices for neural networks. Phys. Rev. Lett.97 188104.
[26] Rebrova, E. and Tikhomirov, K. Covering of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries. Preprint. Available at arXiv:1508.06690.
[27] Rudelson, M. (2008). Invertibility of random matrices: Norm of the inverse. Ann. of Math. (2) 168 575–600. · Zbl 1175.15030
[28] Rudelson, M. and Vershynin, R. (2008). The Littlewood–Offord problem and invertibility of random matrices. Adv. Math.218 600–633. · Zbl 1139.15015
[29] Rudelson, M. and Vershynin, R. (2008). The least singular value of a random square matrix is \(O(n^{-1/2})\). C. R. Math. Acad. Sci. Paris346 893–896. · Zbl 1152.60042
[30] Rudelson, M. and Zeitouni, O. (2016). Singular values of Gaussian matrices and permanent estimators. Random Structures Algorithms48 183–212. · Zbl 1362.15028
[31] Sankar, A., Spielman, D. A. and Teng, S.-H. (2006). Smoothed analysis of the condition numbers and growth factors of matrices. SIAM J. Matrix Anal. Appl.28 446–476. · Zbl 1179.65033
[32] Spielman, D. A. and Srivastava, N. (2012). An elementary proof of the restricted invertibility theorem. Israel J. Math.190 83–91. · Zbl 1261.46007
[33] Szemerédi, E. (1978). Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloq. Internat. CNRS260 399–401. CNRS, Paris.
[34] Talagrand, M. (1996). A new look at independence. Ann. Probab.24 1–34. · Zbl 0858.60019
[35] Tao, T. and Vu, V. (2008). Random matrices: The circular law. Commun. Contemp. Math.10 261–307. · Zbl 1156.15010
[36] Tao, T. and Vu, V. (2010). Random matrices: The distribution of the smallest singular values. Geom. Funct. Anal.20 260–297. · Zbl 1210.60014
[37] Tao, T. and Vu, V. (2010). Random matrices: Universality of ESDs and the circular law. Ann. Probab.38 2023–2065. With an appendix by Manjunath Krishnapur. · Zbl 1203.15025
[38] Tao, T. and Vu, V. (2010). Smooth analysis of the condition number and the least singular value. Math. Comp.79 2333–2352. · Zbl 1253.65067
[39] Tao, T. and Vu, V. H. (2009). Inverse Littlewood–Offord theorems and the condition number of random discrete matrices. Ann. of Math. (2) 169 595–632. · Zbl 1250.60023
[40] Tulino, A. M. and Verdú, S. (2004). Random Matrix Theory and Wireless Communications1. Now Publishers Inc.
[41] van Handel, R. (2017). On the spectral norm of Gaussian random matrices. Trans. Amer. Math. Soc.369 8161–8178. · Zbl 1423.60017
[42] Vershynin, R. (2011). Spectral norm of products of random and deterministic matrices. Probab. Theory Related Fields150 471–509. · Zbl 1235.60009
[43] von Neumann, J. and Goldstine, H. H. (1947). Numerical inverting of matrices of high order. Bull. Amer. Math. Soc.53 1021–1099. · Zbl 0031.31402
[44] Yin, Y. Q., Bai, Z. D. and Krishnaiah, P. R. (1988). On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix. Probab. Theory Related Fields78 509–521. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.