×

Eigenvectors of random matrices: A survey. (English) Zbl 1347.15044

Summary: Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random.

MSC:

15B52 Random matrices (algebraic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
60B20 Random matrices (probabilistic aspects)
05C80 Random graphs (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anantharaman, N.; Le Masson, E., Quantum ergodicity on large regular graphs, Duke Math. J., 164, 4, 723-765 (2015) · Zbl 1386.58015
[2] Anderson, G. W.; Guionnet, A.; Zeitouni, O., An Introduction to Random Matrices, Cambridge Studies in Advanced Mathematics, vol. 118 (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1184.15023
[3] Arora, S.; Bhaskara, A., Eigenvectors of random graphs: delocalization and nodal domains, preprint, available at
[4] Auffinger, A.; Ben Arous, G.; Péché, S., Poisson convergence for the largest eigenvalues of heavy tailed random matrices, Ann. Inst. Henri Poincaré Probab. Stat., 45, 3, 589-610 (2009) · Zbl 1177.15037
[5] Bai, Z.; Silverstein, J. W., Spectral Analysis of Large Dimensional Random Matrices, Springer Series in Statistics (2010), Springer: Springer New York · Zbl 1301.60002
[6] Baik, J.; Arous, G. Ben; Péché, S., Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices, Ann. Probab., 33, 5, 1643-1697 (2005) · Zbl 1086.15022
[7] Bauerschmidt, R.; Knowles, A.; Yau, H.-T., Local semicircle law for random regular graphs (2015), preprint
[8] Benaych-Georges, F.; Guionnet, A., Central limit theorem for eigenvectors of heavy tailed matrices, Electron. J. Probab., 19, 54, 1-27 (2014) · Zbl 1293.15021
[9] Benaych-Georges, F.; Nadakuditi, R. Rao, Eigenvalues and eigenvectors of finite, low rank perturbation of large random matrices, Adv. Math., 227, 1, 494-521 (2009) · Zbl 1226.15023
[10] Benaych-Georges, F.; Péché, S., Localization and delocalization for heavy tailed band matrices, Ann. Inst. Henri Poincaré Probab. Stat., 50, 4, 1385-1403 (2014) · Zbl 1307.15054
[11] Bhatia, R., Matrix Analysis, Graduate Texts in Mathematics, vol. 169 (1997), Springer-Verlag: Springer-Verlag New York
[12] Bloemendal, A.; Erdos, L.; Knowles, A.; Yau, H.-T.; Yin, J., Isotropic local laws for sample covariance and generalized Wigner matrices, Electron. J. Probab., 19, 33, 1-53 (2014) · Zbl 1288.15044
[13] Bordenave, C.; Guionnet, A., Localization and delocalization of eigenvectors for heavy-tailed random matrices, Probab. Theory Related Fields, 157, 3, 885-953 (2013) · Zbl 1296.15019
[14] Bordenave, C.; Guionnet, A., Delocalization at small energy for heavy-tailed random matrices (2016), preprint · Zbl 1388.60022
[15] Bourgade, P.; Yau, H.-T., The eigenvector moment flow and local quantum unique ergodicity (2013) · Zbl 1379.58014
[16] Brooks, S.; Lindenstrauss, E., Non-localization of eigenfunctions on large regular graphs, Israel J. Math., 193, 1, 1-14 (2013) · Zbl 1317.05110
[17] Cacciapuoti, C.; Maltsev, A.; Schlein, B., Local Marchenko-Pastur law at the hard edge of sample covariance matrices (2012), preprint
[18] Cizeau, P.; Bouchaud, J. P., Theory of Lévy matrices, Phys. Rev. E, 50 (1994)
[19] Csörgő, S.; Haeusler, E.; Mason, D. M., The asymptotic distribution of extreme sums, Ann. Probab., 19, 2, 783-811 (1991) · Zbl 0736.62015
[20] de Haan, L.; Ferreira, A., Extreme Value Theory: An Introduction, Springer Series in Operations Research and Financial Engineering (2006), Springer: Springer New York · Zbl 1101.62002
[21] Dekel, Y.; Lee, J. R.; Linial, N., Eigenvectors of random graphs: nodal domains, Random Structures Algorithms, 39, 1, 39-58 (2011) · Zbl 1223.05275
[22] Dumitriu, I.; Pal, S., Sparse regular random graphs: spectral density and eigenvectors, Ann. Probab., 40, 5, 2197-2235 (2012) · Zbl 1255.05173
[23] Erdős, L., Universality of Wigner random matrices: a survey of recent results, Uspekhi Mat. Nauk, 66, 3(399), 67-198 (2011)
[24] Erdös, L.; Knowles, A., Quantum diffusion and eigenfunction delocalization in a random band matrix model, Comm. Math. Phys., 303, 2, 509-554 (2011) · Zbl 1226.15024
[25] Erdös, L.; Knowles, A., Quantum diffusion and delocalization for band matrices with general distribution, Ann. Henri Poincaré, 12, 7, 1227-1319 (2011) · Zbl 1247.15033
[26] Erdős, L.; Yau, H.-T., Universality of local spectral statistics of random matrices, Bull. Amer. Math. Soc. (N.S.), 49, 3, 377-414 (2012) · Zbl 1263.15032
[27] Erdős, L.; Schlein, B.; Yau, H.-T., Local semicircle law and complete delocalization for Wigner random matrices, Comm. Math. Phys., 287, 2, 641-655 (2009) · Zbl 1186.60005
[28] 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
[29] Erdős, L.; Ramírez, J.; Schlein, B.; Tao, T.; Vu, V.; Yau, H.-T., Bulk universality for Wigner Hermitian matrices with subexponential decay, Math. Res. Lett., 17, 4, 667-674 (2010) · Zbl 1277.15027
[30] Erdős, L.; Schlein, B.; Yau, H.-T., Wegner estimate and level repulsion for Wigner random matrices, Int. Math. Res. Not. IMRN, 3, 436-479 (2010) · Zbl 1204.15043
[31] Erdős, L.; Schlein, B.; Yau, H.-T., Universality of random matrices and local relaxation flow, Invent. Math., 185, 1, 75-119 (2011) · Zbl 1225.15033
[32] Erdős, L.; Yau, H.-T.; Yin, J., Universality for generalized Wigner matrices with Bernoulli distribution, J. Comb., 2, 1, 15-81 (2011) · Zbl 1235.15029
[33] Erdős, L.; Schlein, B.; Yau, H.-T.; Yin, J., The local relaxation flow approach to universality of the local statistics for random matrices, Ann. Inst. Henri Poincaré Probab. Stat., 48, 1, 1-46 (2012) · Zbl 1285.82029
[34] Erdős, L.; Yau, H.-T.; Yin, J., Bulk universality for generalized Wigner matrices, Probab. Theory Related Fields, 154, 1-2, 341-407 (2012) · Zbl 1277.15026
[35] Erdős, L.; Yau, H.-T.; Yin, J., Rigidity of eigenvalues of generalized Wigner matrices, Adv. Math., 229, 3, 1435-1515 (2012) · Zbl 1238.15017
[36] Erdős, L.; Knowles, A.; Yau, H.-T., Averaging fluctuations in resolvents of random band matrices, Ann. Henri Poincaré, 14, 8, 1837-1926 (2013) · Zbl 1296.15020
[37] Erdős, L.; Knowles, A.; Yau, H.-T.; Yin, J., Spectral statistics of Erdős-Rényi graphs I: local semicircle law, Ann. Probab., 41, 3B, 2279-2375 (2013) · Zbl 1272.05111
[38] Erdős, L.; Knowles, A.; Yau, H.-T.; Yin, J., Delocalization and diffusion profile for random band matrices, Comm. Math. Phys., 323, 1, 367-416 (2013) · Zbl 1279.15027
[39] Feller, W., An Introduction to Probability Theory and Its Applications. Vol. II (1971), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York-London-Sydney · Zbl 0219.60003
[40] Füredi, Z.; Komlós, J., The eigenvalues of random symmetric matrices, Combinatorica, 1, 3, 233-241 (1981) · Zbl 0494.15010
[41] Gallardo, L., Au sujet du contenu probabiliste d’un lemme d’Henri Poincaré, Saint-Flour Probability Summer Schools. Saint-Flour Probability Summer Schools, Saint-Flour, 1979/1980. Saint-Flour Probability Summer Schools. Saint-Flour Probability Summer Schools, Saint-Flour, 1979/1980, Ann. Sci. Univ. Clermont-Ferrand II Math., 19, 185-190 (1981) · Zbl 0491.60029
[42] Gut, A., Probability: A Graduate Course, Springer Texts in Statistics (2005), Springer: Springer New York · Zbl 1076.60001
[43] Horn, R. A.; Johnson, C. R., Matrix Analysis (2013), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1267.15001
[44] Jiang, T., How many entries of a typical orthogonal matrix can be approximated by independent normals?, Ann. Probab., 34, 4, 1497-1529 (2006) · Zbl 1107.15018
[45] Knowles, A.; Yin, J., Eigenvector distribution of Wigner matrices, Probab. Theory Related Fields, 155, 3-4, 543-582 (2013) · Zbl 1268.15033
[46] Knowles, A.; Yin, J., The outliers of a deformed Wigner matrix, Ann. Probab., 42, 5, 1980-2031 (2014) · Zbl 1306.15034
[47] Laurent, B.; Massart, P., Adaptive estimation of a quadratic functional by model selection, Ann. Statist., 28, 5, 1302-1338 (2000) · Zbl 1105.62328
[48] Lee, J. O.; Yin, J., A necessary and sufficient condition for edge universality of Wigner matrices, Duke Math. J., 163, 1, 117-173 (2014) · Zbl 1296.60007
[49] Matoušek, J., Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212 (2002), Springer-Verlag: Springer-Verlag New York · Zbl 0999.52006
[50] McSherry, F., Spectral partitioning of random graphs, (42nd IEEE Symposium on Foundations of Computer Science. 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 2001 (2001), IEEE Computer Soc.: IEEE Computer Soc. Los Alamitos, CA), 529-537
[51] Mitra, P., Entrywise bounds for eigenvectors of random graphs, Electron. J. Combin., 16, 1 (2009), Research Paper 131, 18 pp · Zbl 1186.05109
[52] Newman, M. E., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 3, Article 036104 pp. (2006)
[53] Newman, M. E., Modularity and community structure in networks, Proc. Nat. Acad. Sci., 103, 23, 8577-8582 (2006)
[54] Nguyen, H.; Tao, T.; Vu, V., Random matrices: tail bounds for gaps between eigenvalues (2015), preprint
[55] O’Rourke, S.; Touri, B., Controllability of random systems: universality and minimal controllability (2015), preprint
[56] O’Rourke, S.; Vu, V.; Wang, K., Random perturbation of low rank matrices: improving classical bounds (2016), preprint
[57] Page, L.; Brin, S.; Motwani, R.; Winograd, T., The pagerank citation ranking: bringing order to the web (1999), Stanford InfoLab, Technical report
[58] Pillai, N. S.; Yin, J., Universality of covariance matrices, Ann. Appl. Probab., 24, 3, 935-1001 (2014) · Zbl 1296.15021
[59] Pizzo, A.; Renfrew, D.; Soshnikov, A., On finite rank deformations of Wigner matrices, Ann. Inst. Henri Poincaré Probab. Stat., 49, 1, 64-94 (2013) · Zbl 1278.60014
[60] Pothen, A.; Simon, H. D.; Liou, K.-P., Partitioning sparse matrices with eigenvectors of graphs, Sparse Matrices. Sparse Matrices, Gleneden Beach, OR, 1989. Sparse Matrices. Sparse Matrices, Gleneden Beach, OR, 1989, SIAM J. Matrix Anal. Appl., 11, 3, 430-452 (1990) · Zbl 0711.65034
[61] Renfrew, D.; Soshnikov, A., On finite rank deformations of Wigner matrices II: delocalized perturbations, Random Matrices Theory Appl., 2, 1 (2013) · Zbl 1296.60008
[62] Rudelson, M.; Vershynin, R., Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math., 62, 12, 1707-1739 (2009) · Zbl 1183.15031
[63] Rudelson, M.; Vershynin, R., Non-asymptotic theory of random matrices: extreme singular values, (Proceedings of the International Congress of Mathematicians. Volume III (2010), Hindustan Book Agency: Hindustan Book Agency New Delhi), 1576-1602 · Zbl 1227.60011
[64] Rudelson, M.; Vershynin, R., Delocalization of eigenvectors of random matrices with independent entries, Duke Math. J., 164, 13, 2507-2538 (2015) · Zbl 1352.60007
[65] Rudelson, M.; Vershynin, R., Hanson-Wright inequality and sub-Gaussian concentration, Electron. Commun. Probab., 18, 82, 1-9 (2013) · Zbl 1329.60056
[66] Rudelson, M.; Vershynin, R., No-gaps delocalization for general random matrices (2015), preprint · Zbl 1375.60027
[67] Schenker, J., Eigenvector localization for random band matrices with power law band width, Comm. Math. Phys., 290, 3, 1065-1097 (2009) · Zbl 1179.82079
[68] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22, 8, 888-905 (2000)
[69] Soshnikov, A., Poisson statistics for the largest eigenvalues of Wigner random matrices with heavy tails, Electron. Commun. Probab., 9, 82-91 (2004) · Zbl 1060.60013
[70] Soshnikov, A., Poisson statistics for the largest eigenvalues in random matrix ensembles, (Mathematical Physics of Quantum Mechanics. Mathematical Physics of Quantum Mechanics, Lecture Notes in Phys., vol. 690 (2006), Springer: Springer Berlin), 351-364 · Zbl 1169.15302
[71] Spencer, T., Random banded and sparse matrices, (The Oxford Handbook of Random Matrix Theory (2011), Oxford University Press), 471-488 · Zbl 1236.15074
[72] Springer, M. D., The Algebra of Random Variables, Wiley Series in Probability and Mathematical Statistics (1979), John Wiley & Sons: John Wiley & Sons New York-Chichester-Brisbane · Zbl 0399.60002
[73] Takahashi, R., Normalizing constants of a distribution which belongs to the domain of attraction of the Gumbel distribution, Statist. Probab. Lett., 5, 3, 197-200 (1987) · Zbl 0617.62050
[74] Tao, T., Topics in Random Matrix Theory, vol. 132 (2012), American Mathematical Soc.
[75] Tao, T.; Vu, V., Random matrices: universality of local eigenvalue statistics up to the edge, Comm. Math. Phys., 298, 2, 549-572 (2010) · Zbl 1202.15038
[76] Tao, T.; Vu, V., Random matrices: universality of local eigenvalue statistics, Acta Math., 206, 1, 127-204 (2011) · Zbl 1217.15043
[77] Tao, T.; Vu, V., The Wigner-Dyson-Mehta bulk universality conjecture for Wigner matrices, Electron. J. Probab., 16, 77, 2104-2121 (2011) · Zbl 1245.15041
[78] Tao, T.; Vu, V., Random covariance matrices: universality of local statistics of eigenvalues, Ann. Probab., 40, 3, 1285-1315 (2012) · Zbl 1247.15036
[79] Tao, T.; Vu, V., Random matrices: universal properties of eigenvectors, Random Matrices Theory Appl., 1, 01, 1150001 (2012) · Zbl 1248.15031
[80] Tao, T.; Vu, V., Random matrices: the universality phenomenon for Wigner ensembles, (Modern Aspects of Random Matrix Theory. Modern Aspects of Random Matrix Theory, Proc. Sympos. Appl. Math., vol. 72 (2014), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 121-172 · Zbl 1310.15077
[81] Tao, T.; Vu, V., Random matrices have simple spectrum, available at · Zbl 1399.60008
[82] Tran, L. V.; Vu, V. H.; Wang, K., Sparse random graphs: eigenvalues and eigenvectors, Random Structures Algorithms, 42, 1, 110-134 (2013) · Zbl 1257.05089
[83] Vershynin, R., Spectral norm of products of random and deterministic matrices, Probab. Theory Related Fields, 150, 3-4, 471-509 (2011) · Zbl 1235.60009
[84] Vershynin, R., Introduction to the non-asymptotic analysis of random matrices, (Compressed Sensing (2012), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 210-268
[85] von Luxburg, U., A tutorial on spectral clustering, Stat. Comput., 17, 4, 395-416 (2007)
[86] Vu, V.; Wang, K., Random weighted projections, random quadratic forms and random eigenvectors, Random Structures Algorithms, 47, 4, 792-821 (2015) · Zbl 1384.60029
[87] Wang, K., Random covariance matrices: universality of local statistics of eigenvalues up to the edge, Random Matrices Theory Appl., 1, 01, Article 1150005 pp. (2012) · Zbl 1288.15047
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.