{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T16:02:28Z","timestamp":1791475348329,"version":"4.3.4"},"reference-count":81,"publisher":"Institute of Mathematical Statistics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2020,6,1]]},"abstract":"<jats:p>Recovering low-rank structures via eigenvector perturbation analysis is a common problem in statistical machine learning, such as in factor analysis, community detection, ranking, matrix completion, among others. While a large variety of bounds are available for average errors between empirical and population statistics of eigenvectors, few results are tight for entrywise analyses, which are critical for a number of problems such as community detection. This paper investigates entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low rank, which helps settle the conjecture in Abbe, Bandeira and Hall (2014) that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. The key is a first-order approximation of eigenvectors under the $\\ell _{\\infty }$ norm: \\begin{equation*}u_{k}\\approx \\frac{Au_{k}^{*}}{\\lambda _{k}^{*}},\\end{equation*} where $\\{u_{k}\\}$ and $\\{u_{k}^{*}\\}$ are eigenvectors of a random matrix $A$ and its expectation $\\mathbb{E}A$, respectively. The fact that the approximation is both tight and linear in $A$ facilitates sharp comparisons between $u_{k}$ and $u_{k}^{*}$. In particular, it allows for comparing the signs of $u_{k}$ and $u_{k}^{*}$ even if $\\|u_{k}-u_{k}^{*}\\|_{\\infty }$ is large. The results are further extended to perturbations of eigenspaces, yielding new $\\ell _{\\infty }$-type bounds for synchronization ($\\mathbb{Z}_{2}$-spiked Wigner model) and noisy matrix completion.<\/jats:p>","DOI":"10.1214\/19-aos1854","type":"journal-article","created":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T04:02:13Z","timestamp":1594958533000},"page":"1452-1474","source":"Crossref","is-referenced-by-count":127,"title":["Entrywise eigenvector analysis of random matrices with low expected rank"],"prefix":"10.1214","volume":"48","author":[{"given":"Emmanuel","family":"Abbe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianqing","family":"Fan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaizheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yiqiao","family":"Zhong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"67","doi-asserted-by":"crossref","unstructured":"Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. <i>IEEE Trans. Pattern Anal. Mach. Intell.<\/i> <b>22<\/b> 888\u2013905.","DOI":"10.1109\/34.868688"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. <i>Soc. Netw.<\/i> <b>5<\/b> 109\u2013137.","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"64","doi-asserted-by":"publisher","unstructured":"Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. <i>Ann. Statist.<\/i> <b>39<\/b> 1878\u20131915.","DOI":"10.1214\/11-AOS887"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. <i>Ann. Statist.<\/i> <b>43<\/b> 215\u2013237.","DOI":"10.1214\/14-AOS1274"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Baik, J., Ben Arous, G. and P\u00e9ch\u00e9, S. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. <i>Ann. Probab.<\/i> <b>33<\/b> 1643\u20131697.","DOI":"10.1214\/009117905000000233"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Benaych-Georges, F. and Nadakuditi, R. R. (2011). The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. <i>Adv. Math.<\/i> <b>227<\/b> 494\u2013521.","DOI":"10.1016\/j.aim.2011.02.007"},{"key":"72","doi-asserted-by":"publisher","unstructured":"Sussman, D. L., Tang, M., Fishkind, D. E. and Priebe, C. E. (2012). A consistent adjacency spectral embedding for stochastic blockmodel graphs. <i>J. Amer. Statist. Assoc.<\/i> <b>107<\/b> 1119\u20131128.","DOI":"10.1080\/01621459.2012.699795"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J. and Recht, B. (2009). Exact matrix completion via convex optimization. <i>Found. Comput. Math.<\/i> <b>9<\/b> 717\u2013772.","DOI":"10.1007\/s10208-009-9045-5"},{"key":"79","doi-asserted-by":"publisher","unstructured":"Zhang, A. Y. and Zhou, H. H. (2016). Minimax rates of community detection in stochastic block models. <i>Ann. Statist.<\/i> <b>44<\/b> 2252\u20132280.","DOI":"10.1214\/15-AOS1428"},{"key":"18","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E. J. and Plan, Y. (2010). Matrix completion with noise. <i>Proc. IEEE<\/i> <b>98<\/b> 925\u2013936.","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Davis, C. and Kahan, W. M. (1970). The rotation of eigenvectors by a perturbation. III. <i>SIAM J. Numer. Anal.<\/i> <b>7<\/b> 1\u201346.","DOI":"10.1137\/0707001"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J. and Tao, T. (2010). The power of convex relaxation: Near-optimal matrix completion. <i>IEEE Trans. Inform. Theory<\/i> <b>56<\/b> 2053\u20132080.","DOI":"10.1109\/TIT.2010.2044061"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Gross, D. (2011). Recovering low-rank matrices from few coefficients in any basis. <i>IEEE Trans. Inform. Theory<\/i> <b>57<\/b> 1548\u20131566.","DOI":"10.1109\/TIT.2011.2104999"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Koltchinskii, V., Lounici, K. and Tsybakov, A. B. (2011). Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. <i>Ann. Statist.<\/i> <b>39<\/b> 2302\u20132329.","DOI":"10.1214\/11-AOS894"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Bickel, P. J. (1975). One-step Huber estimates in the linear model. <i>J. Amer. Statist. Assoc.<\/i> <b>70<\/b> 428\u2013434.","DOI":"10.1080\/01621459.1975.10479884"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborov\u00e1, L. and Zhang, P. (2013). Spectral redemption in clustering sparse networks. <i>Proc. Natl. Acad. Sci. USA<\/i> <b>110<\/b> 20935\u201320940.","DOI":"10.1073\/pnas.1312486110"},{"key":"29","doi-asserted-by":"crossref","unstructured":"Decelle, A., Krzakala, F., Moore, C. and Zdeborov\u00e1, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. <i>Phys. Rev. E<\/i> <b>84<\/b> 066106.","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Chatterjee, S. (2015). Matrix estimation by universal singular value thresholding. <i>Ann. Statist.<\/i> <b>43<\/b> 177\u2013214.","DOI":"10.1214\/14-AOS1272"},{"key":"33","doi-asserted-by":"crossref","unstructured":"F\u00e9ral, D. and P\u00e9ch\u00e9, S. (2007). The largest eigenvalue of rank one deformation of large Wigner matrices. <i>Comm. Math. Phys.<\/i> <b>272<\/b> 185\u2013228.","DOI":"10.1007\/s00220-007-0209-3"},{"key":"75","doi-asserted-by":"publisher","unstructured":"Wedin, P. (1972). Perturbation bounds in connection with singular value decomposition. <i>BIT<\/i> <b>12<\/b> 99\u2013111.","DOI":"10.1007\/BF01932678"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Javanmard, A., Montanari, A. and Ricci-Tersenghi, F. (2016). Phase transitions in semidefinite relaxations. <i>Proc. Natl. Acad. Sci. USA<\/i> <b>113<\/b> E2218\u2013E2223.","DOI":"10.1073\/pnas.1523097113"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Singer, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. <i>Appl. Comput. Harmon. Anal.<\/i> <b>30<\/b> 20\u201336.","DOI":"10.1016\/j.acha.2010.02.001"},{"key":"21","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E. J., Li, X., Ma, Y. and Wright, J. (2011). Robust principal component analysis? <i>J. ACM<\/i> <b>58<\/b> 11.","DOI":"10.1145\/1970392.1970395"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Abbe, E., Bandeira, A. S. and Hall, G. (2016). Exact recovery in the stochastic block model. <i>IEEE Trans. Inform. Theory<\/i> <b>62<\/b> 471\u2013487.","DOI":"10.1109\/TIT.2015.2490670"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Koltchinskii, V. and Lounici, K. (2016). Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance. <i>Ann. Inst. Henri Poincar\u00e9 Probab. Stat.<\/i> <b>52<\/b> 1976\u20132013.","DOI":"10.1214\/15-AIHP705"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Ma, C., Wang, K., Chi, Y. and Chen, Y. (2017). Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution. ArXiv preprint. Available at <a href=\"ArXiv:1711.10467\">ArXiv:1711.10467<\/a>.","DOI":"10.1007\/s10208-019-09429-9"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Amini, A. A. and Levina, E. (2018). On semidefinite relaxations for the block model. <i>Ann. Statist.<\/i> <b>46<\/b> 149\u2013179.","DOI":"10.1214\/17-AOS1545"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Lelarge, M. and Miolane, L. (2019). Fundamental limits of symmetric low-rank matrix estimation. <i>Probab. Theory Related Fields<\/i> <b>173<\/b> 859\u2013929.","DOI":"10.1007\/s00440-018-0845-x"},{"key":"1","doi-asserted-by":"crossref","unstructured":"Abbe, E. (2017). Community detection and stochastic block models: Recent developments. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> 177.","DOI":"10.1561\/9781680834772"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Abbe, E., Bandeira, A. S. and Hall, G. (2014). Exact recovery in the stochastic block model. arXiv preprint <a href=\"arXiv:1405.3267\">arXiv:1405.3267<\/a>.","DOI":"10.1109\/TIT.2015.2490670"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Abbe, E. and Sandon, C. (2018). Proof of the achievability conjectures for the general stochastic block model. <i>Comm. Pure Appl. Math.<\/i> <b>71<\/b> 1334\u20131406.","DOI":"10.1002\/cpa.21719"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Abbe, E., Bandeira, A. S., Bracher, A. and Singer, A. (2014). Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. <i>IEEE Trans. Netw. Sci. Eng.<\/i> <b>1<\/b> 10\u201322.","DOI":"10.1109\/TNSE.2014.2368716"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Abbe, E., Fan, J., Wang, K. and Zhong, Y. (2019). Supplement to \u201cEntrywise eigenvector analysis of random matrices with low expected rank.\u201d <a href=\"https:\/\/doi.org\/10.1214\/19-AOS1854SUPP\">https:\/\/doi.org\/10.1214\/19-AOS1854SUPP<\/a>.","DOI":"10.1214\/19-AOS1854SUPP"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Bandeira, A. S. (2018). Random Laplacian matrices and convex relaxations. <i>Found. Comput. Math.<\/i> <b>18<\/b> 345\u2013379.","DOI":"10.1007\/s10208-016-9341-9"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Bandeira, A. S., Boumal, N. and Singer, A. (2017). Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. <i>Math. Program.<\/i> <b>163<\/b> 145\u2013167.","DOI":"10.1007\/s10107-016-1059-6"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J., Li, X. and Soltanolkotabi, M. (2015). Phase retrieval via Wirtinger flow: Theory and algorithms. <i>IEEE Trans. Inform. Theory<\/i> <b>61<\/b> 1985\u20132007.","DOI":"10.1109\/TIT.2015.2399924"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Cape, J., Tang, M. and Priebe, C. E. (2017). The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. ArXiv preprint. Available at <a href=\"arXiv:1705.10735\">arXiv:1705.10735<\/a>.","DOI":"10.1214\/18-AOS1752"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Chen, Y., Fan, J., Ma, C. and Wang, K. (2019). Spectral method and regularized MLE are both optimal for top-$K$ ranking. <i>Ann. Statist.<\/i> <b>47<\/b> 2204\u20132235.","DOI":"10.1214\/18-AOS1745"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Coja-Oghlan, A. (2006). A spectral heuristic for bisecting random graphs. <i>Random Structures Algorithms<\/i> <b>29<\/b> 351\u2013398.","DOI":"10.1002\/rsa.20116"},{"key":"27","doi-asserted-by":"crossref","unstructured":"Cucuringu, M., Lipman, Y. and Singer, A. (2012). Sensor network localization by eigenvector synchronization over the Euclidean group. <i>ACM Trans. Sens. Netw.<\/i> <b>8<\/b>. 19.","DOI":"10.1145\/2240092.2240093"},{"key":"30","doi-asserted-by":"crossref","unstructured":"Deshpande, Y., Abbe, E. and Montanari, A. (2017). Asymptotic mutual information for the balanced binary stochastic block model. <i>Inf. Inference<\/i> <b>6<\/b> 125\u2013170.","DOI":"10.1093\/imaiai\/iaw017"},{"key":"31","unstructured":"Eldridge, J., Belkin, M. and Wang, Y. (2018). Unperturbed: Spectral analysis beyond Davis\u2013Kahan. In <i>Algorithmic Learning Theory 2018<\/i>. <i>Proc. Mach. Learn. Res. (PMLR)<\/i> <b>83<\/b> 38."},{"key":"32","unstructured":"Fan, J., Wang, W. and Zhong, Y. (2017). An $\\ell_{\\infty}$ eigenvector perturbation bound and its application to robust covariance estimation. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> 207."},{"key":"34","unstructured":"Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H. (2017). Achieving optimal misclassification proportion in stochastic block models. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> 60."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Gu\u00e9don, O. and Vershynin, R. (2016). Community detection in sparse networks via Grothendieck\u2019s inequality. <i>Probab. Theory Related Fields<\/i> <b>165<\/b> 1025\u20131049.","DOI":"10.1007\/s00440-015-0659-z"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Hajek, B., Wu, Y. and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming: Extensions. <i>IEEE Trans. Inform. Theory<\/i> <b>62<\/b> 5918\u20135937.","DOI":"10.1109\/TIT.2016.2594812"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Keshavan, R. H., Montanari, A. and Oh, S. (2010a). Matrix completion from a few entries. <i>IEEE Trans. Inform. Theory<\/i> <b>56<\/b> 2980\u20132998.","DOI":"10.1109\/TIT.2010.2046205"},{"key":"45","unstructured":"Keshavan, R. H., Montanari, A. and Oh, S. (2010b). Matrix completion from noisy entries. <i>J. Mach. Learn. Res.<\/i> <b>11<\/b> 2057\u20132078."},{"key":"46","unstructured":"Keshavan, R. H. and Oh, S. (2009). A gradient descent algorithm on the Grassman manifold for matrix completion. ArXiv preprint. Available at <a href=\"arXiv:0910.5260\">arXiv:0910.5260<\/a>."},{"key":"49","doi-asserted-by":"crossref","unstructured":"Koltchinskii, V. and Xia, D. (2016). Perturbation of linear forms of singular vectors under Gaussian noise. In <i>High Dimensional Probability VII<\/i>. <i>Progress in Probability<\/i> <b>71<\/b> 397\u2013423. Springer, Cham.","DOI":"10.1007\/978-3-319-40519-3_18"},{"key":"52","doi-asserted-by":"crossref","unstructured":"Lelarge, M., Massouli\u00e9, L. and Xu, J. (2015). Reconstruction in the labelled stochastic block model. <i>IEEE Trans. Netw. Sci. Eng.<\/i> <b>2<\/b> 152\u2013163.","DOI":"10.1109\/TNSE.2015.2490580"},{"key":"58","unstructured":"Mossel, E., Neeman, J. and Sly, A. (2014). Consistency thresholds for binary symmetric block models. ArXiv preprint. Available at <a href=\"arXiv:1407.1591\">arXiv:1407.1591<\/a>."},{"key":"59","doi-asserted-by":"publisher","unstructured":"Mossel, E., Neeman, J. and Sly, A. (2018). A proof of the block model threshold conjecture. <i>Combinatorica<\/i> <b>38<\/b> 665\u2013708.","DOI":"10.1007\/s00493-016-3238-8"},{"key":"61","doi-asserted-by":"publisher","unstructured":"O\u2019Rourke, S., Vu, V. and Wang, K. (2018). Random perturbation of low rank matrices: Improving classical bounds. <i>Linear Algebra Appl.<\/i> <b>540<\/b> 26\u201359.","DOI":"10.1016\/j.laa.2017.11.014"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Perry, A., Wein, A. S., Bandeira, A. S. and Moitra, A. (2016). Optimality and sub-optimality of PCA for spiked random matrices and synchronization. ArXiv preprint. Available at <a href=\"arXiv:1609.05573\">arXiv:1609.05573<\/a>.","DOI":"10.1214\/17-AOS1625"},{"key":"65","unstructured":"Rosen, D. M., Carlone, L., Bandeira, A. S. and Leonard, J. J. (2016). A certifiably correct algorithm for synchronization over the special Euclidean group. ArXiv preprint. Available at <a href=\"arXiv:1611.00128\">arXiv:1611.00128<\/a>."},{"key":"66","doi-asserted-by":"publisher","unstructured":"Schr\u00f6dinger, E. (1926). Quantisierung als eigenwertproblem. <i>Ann. Phys.<\/i> <b>385<\/b> 437\u2013490.","DOI":"10.1002\/andp.19263851302"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Shkolnisky, Y. and Singer, A. (2012). Viewing direction estimation in cryo-EM using synchronization. <i>SIAM J. Imaging Sci.<\/i> <b>5<\/b> 1088\u20131110.","DOI":"10.1137\/120863642"},{"key":"71","doi-asserted-by":"publisher","unstructured":"Sun, R. and Luo, Z.-Q. (2016). Guaranteed matrix completion via non-convex factorization. <i>IEEE Trans. Inform. Theory<\/i> <b>62<\/b> 6535\u20136579.","DOI":"10.1109\/TIT.2016.2598574"},{"key":"74","doi-asserted-by":"publisher","unstructured":"Vu, V. (2018). A simple SVD algorithm for finding hidden partitions. <i>Combin. Probab. Comput.<\/i> <b>27<\/b> 124\u2013140.","DOI":"10.1017\/S0963548317000463"},{"key":"76","unstructured":"Xia, D. and Zhou, F. (2017). The $\\ell _{\\infty }$ perturbation of HOSVD and low rank tensor denoising. ArXiv preprint. Available at <a href=\"arXiv:1707.01207\">arXiv:1707.01207<\/a>."},{"key":"77","unstructured":"Yun, S.-Y. and Proutiere, A. (2014). Accurate community detection in the stochastic block model via spectral algorithms. ArXiv preprint. Available at <a href=\"arXiv:1412.7335\">arXiv:1412.7335<\/a>."},{"key":"80","unstructured":"Zhong, Y. (2017). Eigenvector under random perturbation: A nonasymptotic Rayleigh\u2013Schr\u00f6dinger theory. ArXiv preprint. Available at <a href=\"arXiv:1702.00139\">arXiv:1702.00139<\/a>."},{"key":"81","doi-asserted-by":"publisher","unstructured":"Zhong, Y. and Boumal, N. (2018). Near-optimal bounds for phase synchronization. <i>SIAM J. Optim.<\/i> <b>28<\/b> 989\u20131016.","DOI":"10.1137\/17M1122025"},{"key":"70","unstructured":"Stewart, G. W. and Sun, J. G. (1990). <i>Matrix Perturbation Theory<\/i>. <i>Computer Science and Scientific Computing<\/i>. Academic Press, Boston, MA."},{"key":"4","doi-asserted-by":"crossref","unstructured":"Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In <i>2015 IEEE 56th Annual Symposium on Foundations of Computer Science\u2014FOCS 2015<\/i> 670\u2013688. IEEE Computer Soc., Los Alamitos, CA.","DOI":"10.1109\/FOCS.2015.47"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Agarwal, N., Bandeira, A. S., Koiliaris, K. and Kolla, A. (2017). Multisection in the stochastic block model using semidefinite programming. In <i>Compressed Sensing and Its Applications<\/i>. <i>Appl. Numer. Harmon. Anal.<\/i> 125\u2013162. Birkh\u00e4user\/Springer, Cham.","DOI":"10.1007\/978-3-319-69802-1_4"},{"key":"13","unstructured":"Banks, J., Moore, C. Neeman, J., and Netrapalli, P. (2016). Information-theoretic thresholds for community detection in sparse networks. In <i>Conference on Learning Theory<\/i>."},{"key":"16","doi-asserted-by":"crossref","unstructured":"Bordenave, C., Lelarge, M. and Massouli\u00e9, L. (2015). Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs. In <i>2015 IEEE 56th Annual Symposium on Foundations of Computer Science\u2014FOCS 2015<\/i> 1347\u20131357. IEEE Computer Soc., Los Alamitos, CA.","DOI":"10.1109\/FOCS.2015.86"},{"key":"25","unstructured":"Chin, P., Rao, A. and Vu, V. (2015). Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. In <i>Conference on Learning Theory<\/i>."},{"key":"35","unstructured":"Ge, R., Lee, J. D. and Ma, T. (2016). Matrix completion has no spurious local minimum. In <i>Advances in Neural Information Processing Systems<\/i>."},{"key":"36","doi-asserted-by":"crossref","unstructured":"Giridhar, A. and Kumar, P. R. (2006). Distributed clock synchronization over wireless networks: Algorithms and analysis. In <i>Decision and Control, 2006 45th IEEE Conference on<\/i> IEEE.","DOI":"10.1109\/CDC.2006.377325"},{"key":"41","unstructured":"Jain, P. and Netrapalli, P. (2015). Fast exact matrix completion with finite samples. In <i>Conference on Learning Theory<\/i>."},{"key":"42","doi-asserted-by":"crossref","unstructured":"Jain, P., Netrapalli, P. and Sanghavi, S. (2013). Low-rank matrix completion using alternating minimization (extended abstract). In <i>STOC\u201913\u2014Proceedings of the 2013 ACM Symposium on Theory of Computing<\/i> 665\u2013674. ACM, New York.","DOI":"10.1145\/2488608.2488693"},{"key":"55","doi-asserted-by":"crossref","unstructured":"Massouli\u00e9, L. (2014). Community detection thresholds and the weak Ramanujan property. In <i>STOC\u201914\u2014Proceedings of the 2014 ACM Symposium on Theory of Computing<\/i> 694\u2013703. ACM, New York.","DOI":"10.1145\/2591796.2591857"},{"key":"56","doi-asserted-by":"crossref","unstructured":"McSherry, F. (2001). Spectral partitioning of random graphs. In <i>42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001)<\/i> 529\u2013537. IEEE Computer Soc., Los Alamitos, CA.","DOI":"10.1109\/SFCS.2001.959929"},{"key":"57","doi-asserted-by":"crossref","unstructured":"Montanari, A. and Sen, S. (2016). Semidefinite programs on sparse random graphs and their application to community detection. In <i>STOC\u201916\u2014Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing<\/i> 814\u2013827. ACM, New York.","DOI":"10.1145\/2897518.2897548"},{"key":"60","unstructured":"Ng, A. Y., Jordan, M. I. and Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. In <i>Advances in Neural Information Processing Systems<\/i>."},{"key":"63","unstructured":"Rayleigh, J. W. S. (1896). <i>The Theory of Sound<\/i>, <b>2<\/b>. Macmillan."},{"key":"73","doi-asserted-by":"publisher","unstructured":"Tron, R. and Vidal, R. (2009). Distributed image-based 3-D localization of camera sensor networks. In <i>Decision and Control, 2009 Held Jointly with the 2009 28th Chinese Control Conference. CDC\/CCC 2009. Proceedings of the 48th IEEE Conference on<\/i> IEEE.","DOI":"10.1109\/TAC.2014.2351912"},{"key":"78","unstructured":"Yun, S.-Y. and Proutiere, A. (2016). Optimal cluster recovery in the labeled stochastic block model. In <i>Advances in Neural Information Processing Systems<\/i>."}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1594972825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T15:46:11Z","timestamp":1791474371000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-48\/issue-3\/Entrywise-eigenvector-analysis-of-random-matrices-with-low-expected-rank\/10.1214\/19-AOS1854.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,1]]},"references-count":81,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,6,1]]}},"URL":"https:\/\/doi.org\/10.1214\/19-aos1854","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,1]]}}}