×

On delocalization of eigenvectors of random non-Hermitian matrices. (English) Zbl 1458.15061

Summary: We study delocalization of null vectors and eigenvectors of random matrices with i.i.d entries. Let \(A\) be an \(n \times n\) random matrix with i.i.d real subgaussian entries of zero mean and unit variance. We show that with probability at least \(1-e^{-\log^2 n}\) \[\min \limits_{I\subset [n],|I|= m} \Vert \mathbf{v}_I \Vert \ge \frac{m^{3/2}}{n^{3/2}\log^Cn} \Vert \mathbf{v} \Vert\] for any real eigenvector \(\mathbf{v}\) and any \(m\in[\log^C n,n]\), where \(\mathbf{v}_I\) denotes the restriction of \(\mathbf{v}\) to \(I\). Further, when the entries of \(A\) are complex, with i.i.d real and imaginary parts, we show that with probability at least \(1-e^{-\log^2 n}\) all eigenvectors of \(A\) are delocalized in the sense that \[\min \limits_{I\subset [n],|I|= m} \Vert \mathbf{v}_I \Vert \ge \frac{m}{n\log^Cn} \Vert \mathbf{v} \Vert\] for all \(m\in [\log^C n,n]\). Comparing with related results, in the range \(m \in [\log^{C'} n,n/\log^{C'}n]\) in the i.i.d setting and with weaker probability estimates, our lower bounds on \(\Vert \mathbf{v}_I \Vert\) strengthen an earlier estimate \(\min_{|I|= m}\Vert \mathbf{{v}}_I\Vert \ge c(m/n)^6\Vert \mathbf{{v}}\Vert\) obtained in Rudelson and Vershynin (Geom Funct Anal 26(6):1716-1776, 2016), and bounds \(\min_{|I|= m}\Vert \mathbf{v}_I\Vert \ge c(m/n)^2\Vert \mathbf{v}\Vert\) (in the real setting) and \(\min_{|I|= m}\Vert \mathbf{{v}}_I\Vert \ge c(m/n)^{3/2}\Vert \mathbf{v}\Vert\) (in the complex setting) established in [K. Luh and S. O’Rourke, Random Struct. Algorithms 57, No. 1, 169–210 (2020; Zbl 1448.15046)]. As the case of real and complex Gaussian matrices shows, our bounds are optimal up to the polylogarithmic multiples. We derive stronger estimates without the polylogarithmic error multiples for null vectors of real \((n-1)\times n\) random matrices.

MSC:

15B52 Random matrices (algebraic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
60B20 Random matrices (probabilistic aspects)

Citations:

Zbl 1448.15046

References:

[1] Bai, Z.; Silverstein, JW, Spectral Analysis of Large Dimensional Random Matrices. Springer Series in Statistics (2010), New York: Springer, New York · Zbl 1301.60002
[2] Basak, A., Cook, N., Zeitouni, O.: Circular law for the sum of random permutation matrices. Electron. J. Probab. 23, Paper No. 33, 51 pp (2018) · Zbl 1386.15066
[3] Bloemendal, A.; Erdös, L.; Knowles, A.; Yau, H-T; Yin, J., Isotropic local laws for sample covariance and generalized Wigner matrices, Electron. J. Probab., 19, 33, 53 (2014) · Zbl 1288.15044
[4] Bloemendal, A.; Knowles, A.; Yau, HT; Yin, J., On the principal components of sample covariance matrices, Probab. Theory Relat. Fields, 164, 1-2, 459-552 (2016) · Zbl 1339.15023
[5] Bourgade, P.: Random band matrices. In: Proceedings of the International Congress of Mathematicians (ICM 2018), pp. 2759-2783 (2019) · Zbl 1461.15035
[6] Bourgade, P., Huang, J., Yau, H.-T.: Eigenvector statistics of sparse random matrices. Electron. J. Probab. 22, Paper No. 64, 38 pp (2017) · Zbl 1372.05195
[7] Bourgade, P.; Yau, H-T, The eigenvector moment flow and local quantum unique ergodicity, Commun. Math. Phys., 350, 1, 231-278 (2017) · Zbl 1379.58014
[8] Bourgade, P., Yau, H.-T., Yin, J.: Random band matrices in the delocalized phase, I: quantum unique ergodicity and universality (2018). arXiv:1807.01559 · Zbl 1446.60005
[9] Cacciapuoti, C.; Maltsev, A.; Schlein, B., Local Marchenko-Pastur law at the hard edge of sample covariance matrices, J. Math. Phys., 54, 4, 043302 (2013) · Zbl 1282.15031
[10] Chafaï, D.: Singular Values of Random Matrices. Lecture Notes (2009). http://djalil.chafai.net/docs/sing.pdf (2009) · Zbl 1186.60004
[11] Chung, F., Young, S.J.: Braess’s paradox in large sparse random graphs. In: 6th Workshop on Internet and Network Economics, volume 6484 of Lecture Notes in Computer Science, pp. 194-208 (2010)
[12] Cook, N., The circular law for random regular digraphs, Ann. Inst. H. Poincaré Probab. Statist., 55, 4, 2111-2167 (2019) · Zbl 1432.15035
[13] David, HA, Order Statistics (1981), New York: Wiley, New York · Zbl 0553.62046
[14] Edelman, A.; Kostlan, E.; Shub, M., How many eigenvalues of a random matrix are real?, J. Am. Math. Soc., 7, 1, 247-267 (1994) · Zbl 0790.15017
[15] Eldan, R.; Racz, MZ; Schramm, T., Braess’s paradox for the spectral gap in random graphs and delocalization of eigenvectors, Random Struct. Algorithms, 50, 4, 584-611 (2017) · Zbl 1368.05132
[16] Erdős, P., On a lemma of Littlewood and Offord, Bull. Am. Math. Soc., 51, 898-902 (1945) · Zbl 0063.01270
[17] Erdős, L.; Knowles, A.; Yau, H-T; Yin, J., Delocalization and diffusion profile for random band matrices, Commun. Math. Phys., 323, 1, 367-416 (2013) · Zbl 1279.15027
[18] Erdős, L.; Schlein, B.; Yau, H-T, Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices, Ann. Probab., 37, 3, 815-852 (2009) · Zbl 1175.15028
[19] Esseen, CG, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrsch. Verw. Gebiete, 5, 210-216 (1966) · Zbl 0142.14702
[20] Gordon, Y.; Litvak, AE; Pajor, A.; Tomczak-Jaegermann, N., Random \(\epsilon \)-nets and embeddings in \(l^N_\infty \), Studia Math., 178, 1, 91-98 (2007) · Zbl 1126.46006
[21] Hanson, DL; Wright, FT, A bound on tail probabilities for quadratic forms in independent random variables, Ann. Math. Stat., 42, 1079-1083 (1971) · Zbl 0216.22203
[22] Kesten, H., A sharper form of the Doeblin-Lévy-Kolmogorov-Rogozin inequality for concentration functions, Math. Scand., 25, 133-144 (1969) · Zbl 0218.60035
[23] Klartag, B., Livshyts, G.V.: The lower bound for Koldobsky’s slicing inequality via random rounding (2018). arXiv:1810.06189 · Zbl 1446.52006
[24] Knowles, A.; Yin, J., Eigenvector distribution of Wigner matrices, Probab. Theory Relat. Fields, 155, 3-4, 543-582 (2013) · Zbl 1268.15033
[25] Kolmogorov, A., Sur les propriétés des fonctions de concentrations de M. P. Lévy, Ann. Inst. H. Poincaré, 16, 27-34 (1958) · Zbl 0105.11804
[26] Koltchinskii, V.; Mendelson, S., Bounding the smallest singular value of a random matrix without concentration, Int. Math. Res. Not. IMRN, 23, 12991-13008 (2015) · Zbl 1331.15027
[27] Littlewood, JE; Offord, AC, On the number of real roots of a random algebraic equation. III, Rec. Math. [Mat. Sbornik] N.S., 12, 54, 277-286 (1943) · Zbl 0061.01801
[28] Litvak, A., Lytova, A., Tomczak-Jaegermann, N., Tikhomirov, K., Youssef, P.: Structure of eigenvectors of random regular digraphs. arXiv:1801.05575 · Zbl 1447.05091
[29] Litvak, A., Lytova, A., Tomczak-Jaegermann, N., Tikhomirov, K., Youssef, P.: Circular law for sparse random regular digraphs. arXiv:1801.05576 · Zbl 1447.05091
[30] Litvak, AE; Pajor, A.; Rudelson, M.; Tomczak-Jaegermann, N., Smallest singular value of random matrices and geometry of random polytopes, Adv. Math., 195, 2, 491-523 (2005) · Zbl 1077.15021
[31] Livshyts, G.; Paouris, G.; Pivovarov, P., On sharp bounds for marginal densities of product measures, Isr. J. Math., 216, 2, 877-889 (2016) · Zbl 1373.60046
[32] Luh, K., O’Rourke, S.: Eigenvector delocalization for non-Hermitian random matrices and applications. arXiv:1810.00489 · Zbl 1448.15046
[33] Nguyen, H.; Vu, V., Normal vector of a random hyperplane, Int. Math. Res. Not., 2018, 6, 1754-1778 (2018) · Zbl 1405.15005
[34] O’Rourke, S.; Vu, V.; Wang, K., Eigenvectors of random matrices: a survey, J. Combin. Theory Ser. A, 144, 361-442 (2016) · Zbl 1347.15044
[35] Pillai, NS; Yin, J., Universality of covariance matrices, Ann. Appl. Probab., 24, 3, 935-1001 (2014) · Zbl 1296.15021
[36] Rogers, CA, A note on coverings, Mathematika, 4, 1-6 (1957) · Zbl 0079.27203
[37] Rogozin, BA, On the increase of dispersion of sums of independent random variables, Teor. Verojatnost. i Primenen, 6, 106-108 (1961) · Zbl 0106.34003
[38] Rudelson, M.: Delocalization of eigenvectors of random matrices. Lecture notes (2017). arXiv:1707.08461 · Zbl 1442.15057
[39] Rudelson, M.; Vershynin, R., The least singular value of a random square matrix is \(O(n^{-1/2})\), C. R. Math. Acad. Sci. Paris, 346, 15-16, 893-896 (2008) · Zbl 1152.60042
[40] Rudelson, M.; Vershynin, R., The Littlewood-Offord problem and invertibility of random matrices, Adv. Math., 218, 2, 600-633 (2008) · Zbl 1139.15015
[41] Rudelson, M.; Vershynin, R., Small ball probabilities for linear images of high-dimensional distributions, Int. Math. Res. Not. IMRN, 19, 9594-9617 (2015) · Zbl 1330.60029
[42] Rudelson, M.; Vershynin, R., Smallest singular value of a random rectangular matrix, Commun. Pure Appl. Math., 62, 12, 1707-1739 (2009) · Zbl 1183.15031
[43] Rudelson, M., Vershynin, R.: Non-asymptotic theory of random matrices: extreme singular values. In: Proceedings of the International Congress of Mathematicians, vol. III, pp. 1576-1602. Hindustan Book Agency, New Delhi (2010) · Zbl 1227.60011
[44] Rudelson, M.; Vershynin, R., Hanson-Wright inequality and sub-Gaussian concentration, Electron. Commun. Probab., 18, 82, 9 (2013) · Zbl 1329.60056
[45] Rudelson, M.; Vershynin, R., Delocalization of eigenvectors of random matrices with independent entries, Duke Math. J., 164, 13, 2507-2538 (2015) · Zbl 1352.60007
[46] Rudelson, M.; Vershynin, R., No-gaps delocalization for general random matrices, Geom. Funct. Anal., 26, 6, 1716-1776 (2016) · Zbl 1375.60027
[47] Tao, T.; Vu, V., Random matrices: the distribution of the smallest singular values, Geom. Funct. Anal., 20, 1, 260-297 (2010) · Zbl 1210.60014
[48] Tao, T.; Vu, V., Random covariance matrices: universality of local statistics of eigenvalues, Ann. Probab., 40, 3, 1285-1315 (2012) · Zbl 1247.15036
[49] Tao, T.; Vu, V., Random matrices: universality of local spectral statistics of non-Hermitian matrices, Ann. Probab., 43, 2, 782-874 (2015) · Zbl 1316.15042
[50] Tatarko, K., An upper bound on the smallest singular value of a square random matrix, J. Complex., 48, 119-128 (2018) · Zbl 1395.60008
[51] Tikhomirov, KE, The smallest singular value of random rectangular matrices with no moment assumptions on entries, Isr. J. Math., 212, 1, 289-314 (2016) · Zbl 1346.15038
[52] Tikhomirov, K.: Invertibility via distance for non-centered random matrices with continuous distributions (2017). arXiv:1707.09656
[53] Valiant, G.; Roughgarden, T., Braess’s paradox in large random graphs, Random Struct. Algorithms, 37, 4, 495-515 (2010) · Zbl 1207.05185
[54] Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Eldar, Y.C., Kutyniok, G. (eds.) Compressed Sensing, pp. 210-268. Cambridge University Press, Cambridge (2012)
[55] Vershynin, R.: High-Dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47. Cambridge University Press, Cambridge (2018) · Zbl 1430.60005
[56] Vu, V.; Wang, K., Random weighted projections, random quadratic forms and random eigenvectors, Random Struct. Algorithms, 47, 4, 792-821 (2015) · Zbl 1384.60029
[57] Wang, K., Random covariance matrices: universality of local statistics of eigenvalues up to the edge, Random Matrices Theory Appl., 1, 1, 1150005 (2012) · Zbl 1288.15047
[58] Wei, F., Upper bound for intermediate singular values of random matrices, J. Math. Anal. Appl., 445, 2, 1530-1547 (2017) · Zbl 1348.15016
[59] Yaskov, P., Sharp lower bounds on the least singular value of a random matrix without the fourth moment condition, Electron. Commun. Probab., 20, 44, 9 (2015) · Zbl 1318.60009
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.