×

Entrywise eigenvector analysis of random matrices with low expected rank. (English) Zbl 1450.62066

This paper is a study on the analysis of eigenvector disturbance, which is a common problem in statistical machine learning. Many estimation problems in statistics involve low-rank matrix estimators that are NP-hard to calculate, and many of these estimators are solutions to nonconvex programs. The authors investigate entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low rank, which helps to settle a conjecture that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. They investigate entry behaviors, self-spaces, for random matrices with low expected rank. The \( \ell_\infty \) distance between the eigenvectors of a random matrix and its expected counterparts may not be the correct to look at; input errors can be distributed asymmetrically. Let \(A\) be a random matrix, \(A^{\ast}=\mathbb{E}(A)\) and \(E = A - A^{\ast}\) be the “error” of \(A\), \(A\) symmetric, \(u_k\), respectively \(u_k^{\ast}\), be the eigenvector corresponding to the \(k\)-th largest eigenvalue of \(A\), respectively \(A^{\ast}\). If \(E\) is moderate, hence \(u_k=\displaystyle\frac{Au_k^{\ast}}{\lambda_k}\approx\displaystyle\frac{Au_k^{\ast}}{\lambda_k^{\ast}}=u_k^{\ast}+\frac{Eu_k^{\ast}}{\lambda_k^{\ast}}\). This perturbation analysis leads to new and sharp theoretical guarantees. To obtain such results, the authors characterize the concentration properties of \( A \) and structural assumptions in their expectation \( A^{\ast} \). For the exact recovery problem in the stochastic block model, the vanilla spectral algorithm reaches the theoretical limit of the information and coincides with the MLE estimator whenever it is successful. Therefore, MLE and SDP have no advantage over the spectral method in terms of exact recovery if the model is correct.

MSC:

62H25 Factor analysis and principal components; correspondence analysis
60B20 Random matrices (probabilistic aspects)
15B52 Random matrices (algebraic aspects)
62H12 Estimation in multivariate analysis

Software:

Wirtinger Flow

References:

[1] Abbe, E. (2017). Community detection and stochastic block models: Recent developments. J. Mach. Learn. Res. 18 177. · Zbl 1403.62110
[2] Abbe, E., Bandeira, A. S. and Hall, G. (2014). Exact recovery in the stochastic block model. arXiv preprint arXiv:1405.3267. · Zbl 1359.94047 · doi:10.1109/TIT.2015.2490670
[3] Abbe, E., Bandeira, A. S. and Hall, G. (2016). Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory 62 471-487. · Zbl 1359.94047 · doi:10.1109/TIT.2015.2490670
[4] Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015 670-688. IEEE Computer Soc., Los Alamitos, CA.
[5] Abbe, E. and Sandon, C. (2018). Proof of the achievability conjectures for the general stochastic block model. Comm. Pure Appl. Math. 71 1334-1406. · Zbl 1394.62082 · doi:10.1002/cpa.21719
[6] Abbe, E., Bandeira, A. S., Bracher, A. and Singer, A. (2014). Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Trans. Netw. Sci. Eng. 1 10-22.
[7] Abbe, E., Fan, J., Wang, K. and Zhong, Y. (2019). Supplement to “Entrywise eigenvector analysis of random matrices with low expected rank.” https://doi.org/10.1214/19-AOS1854SUPP.
[8] Agarwal, N., Bandeira, A. S., Koiliaris, K. and Kolla, A. (2017). Multisection in the stochastic block model using semidefinite programming. In Compressed Sensing and Its Applications. Appl. Numer. Harmon. Anal. 125-162. Birkhäuser/Springer, Cham.
[9] Amini, A. A. and Levina, E. (2018). On semidefinite relaxations for the block model. Ann. Statist. 46 149-179. · Zbl 1393.62021 · doi:10.1214/17-AOS1545
[10] Baik, J., Ben Arous, G. and Péché, S. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab. 33 1643-1697. · Zbl 1086.15022 · doi:10.1214/009117905000000233
[11] Bandeira, A. S. (2018). Random Laplacian matrices and convex relaxations. Found. Comput. Math. 18 345-379. · Zbl 1386.15065 · doi:10.1007/s10208-016-9341-9
[12] Bandeira, A. S., Boumal, N. and Singer, A. (2017). Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program. 163 145-167. · Zbl 1365.90188 · doi:10.1007/s10107-016-1059-6
[13] Banks, J., Moore, C. Neeman, J., and Netrapalli, P. (2016). Information-theoretic thresholds for community detection in sparse networks. In Conference on Learning Theory.
[14] Benaych-Georges, F. and Nadakuditi, R. R. (2011). The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Adv. Math. 227 494-521. · Zbl 1226.15023 · doi:10.1016/j.aim.2011.02.007
[15] Bickel, P. J. (1975). One-step Huber estimates in the linear model. J. Amer. Statist. Assoc. 70 428-434. · Zbl 0322.62038 · doi:10.1080/01621459.1975.10479884
[16] Bordenave, C., Lelarge, M. and Massoulié, L. (2015). Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015 1347-1357. IEEE Computer Soc., Los Alamitos, CA. · Zbl 1386.05174
[17] Candès, E. J., Li, X. and Soltanolkotabi, M. (2015). Phase retrieval via Wirtinger flow: Theory and algorithms. IEEE Trans. Inform. Theory 61 1985-2007. · Zbl 1359.94069 · doi:10.1109/TIT.2015.2399924
[18] Candès, E. J. and Plan, Y. (2010). Matrix completion with noise. Proc. IEEE 98 925-936.
[19] Candès, E. J. and Recht, B. (2009). Exact matrix completion via convex optimization. Found. Comput. Math. 9 717-772. · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[20] Candès, E. J. and Tao, T. (2010). The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory 56 2053-2080. · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061
[21] Candès, E. J., Li, X., Ma, Y. and Wright, J. (2011). Robust principal component analysis? J. ACM 58 11. · Zbl 1327.62369
[22] 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 arXiv:1705.10735. · Zbl 1470.62065 · doi:10.1214/18-AOS1752
[23] Chatterjee, S. (2015). Matrix estimation by universal singular value thresholding. Ann. Statist. 43 177-214. · Zbl 1308.62038 · doi:10.1214/14-AOS1272
[24] Chen, Y., Fan, J., Ma, C. and Wang, K. (2019). Spectral method and regularized MLE are both optimal for top-\(K\) ranking. Ann. Statist. 47 2204-2235. · Zbl 1425.62038 · doi:10.1214/18-AOS1745
[25] 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 Conference on Learning Theory.
[26] Coja-Oghlan, A. (2006). A spectral heuristic for bisecting random graphs. Random Structures Algorithms 29 351-398. · Zbl 1111.05088 · doi:10.1002/rsa.20116
[27] Cucuringu, M., Lipman, Y. and Singer, A. (2012). Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Trans. Sens. Netw. 8. 19.
[28] Davis, C. and Kahan, W. M. (1970). The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal. 7 1-46. · Zbl 0198.47201 · doi:10.1137/0707001
[29] Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84 066106.
[30] Deshpande, Y., Abbe, E. and Montanari, A. (2017). Asymptotic mutual information for the balanced binary stochastic block model. Inf. Inference 6 125-170. · Zbl 1383.62021
[31] Eldridge, J., Belkin, M. and Wang, Y. (2018). Unperturbed: Spectral analysis beyond Davis-Kahan. In Algorithmic Learning Theory 2018. Proc. Mach. Learn. Res. (PMLR) 83 38. · Zbl 1406.60014
[32] Fan, J., Wang, W. and Zhong, Y. (2017). An \(\ell_{\infty}\) eigenvector perturbation bound and its application to robust covariance estimation. J. Mach. Learn. Res. 18 207. · Zbl 1473.15015
[33] Féral, D. and Péché, S. (2007). The largest eigenvalue of rank one deformation of large Wigner matrices. Comm. Math. Phys. 272 185-228. · Zbl 1136.82016
[34] Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H. (2017). Achieving optimal misclassification proportion in stochastic block models. J. Mach. Learn. Res. 18 60. · Zbl 1440.62244
[35] Ge, R., Lee, J. D. and Ma, T. (2016). Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems.
[36] Giridhar, A. and Kumar, P. R. (2006). Distributed clock synchronization over wireless networks: Algorithms and analysis. In Decision and Control, 2006 45th IEEE Conference on IEEE.
[37] Gross, D. (2011). Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inform. Theory 57 1548-1566. · Zbl 1366.94103 · doi:10.1109/TIT.2011.2104999
[38] Guédon, O. and Vershynin, R. (2016). Community detection in sparse networks via Grothendieck’s inequality. Probab. Theory Related Fields 165 1025-1049. · Zbl 1357.90111 · doi:10.1007/s00440-015-0659-z
[39] Hajek, B., Wu, Y. and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Trans. Inform. Theory 62 5918-5937. · Zbl 1359.94951 · doi:10.1109/TIT.2016.2594812
[40] Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Soc. Netw. 5 109-137.
[41] Jain, P. and Netrapalli, P. (2015). Fast exact matrix completion with finite samples. In Conference on Learning Theory.
[42] Jain, P., Netrapalli, P. and Sanghavi, S. (2013). Low-rank matrix completion using alternating minimization (extended abstract). In STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing 665-674. ACM, New York. · Zbl 1293.65073
[43] Javanmard, A., Montanari, A. and Ricci-Tersenghi, F. (2016). Phase transitions in semidefinite relaxations. Proc. Natl. Acad. Sci. USA 113 E2218-E2223. · Zbl 1359.62188 · doi:10.1073/pnas.1523097113
[44] Keshavan, R. H., Montanari, A. and Oh, S. (2010a). Matrix completion from a few entries. IEEE Trans. Inform. Theory 56 2980-2998. · Zbl 1366.62111 · doi:10.1109/TIT.2010.2046205
[45] Keshavan, R. H., Montanari, A. and Oh, S. (2010b). Matrix completion from noisy entries. J. Mach. Learn. Res. 11 2057-2078. · Zbl 1242.62069
[46] Keshavan, R. H. and Oh, S. (2009). A gradient descent algorithm on the Grassman manifold for matrix completion. ArXiv preprint. Available at arXiv:0910.5260.
[47] Koltchinskii, V. and Lounici, K. (2016). Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance. Ann. Inst. Henri Poincaré Probab. Stat. 52 1976-2013. · Zbl 1353.62053 · doi:10.1214/15-AIHP705
[48] Koltchinskii, V., Lounici, K. and Tsybakov, A. B. (2011). Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Statist. 39 2302-2329. · Zbl 1231.62097 · doi:10.1214/11-AOS894
[49] Koltchinskii, V. and Xia, D. (2016). Perturbation of linear forms of singular vectors under Gaussian noise. In High Dimensional Probability VII. Progress in Probability 71 397-423. Springer, Cham. · Zbl 1353.15034
[50] Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L. and Zhang, P. (2013). Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. USA 110 20935-20940. · Zbl 1359.62252 · doi:10.1073/pnas.1312486110
[51] Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. Ann. Statist. 43 215-237. · Zbl 1308.62041 · doi:10.1214/14-AOS1274
[52] Lelarge, M., Massoulié, L. and Xu, J. (2015). Reconstruction in the labelled stochastic block model. IEEE Trans. Netw. Sci. Eng. 2 152-163.
[53] Lelarge, M. and Miolane, L. (2019). Fundamental limits of symmetric low-rank matrix estimation. Probab. Theory Related Fields 173 859-929. · Zbl 1411.60014 · doi:10.1007/s00440-018-0845-x
[54] 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 arXiv:1711.10467. · Zbl 1445.90089 · doi:10.1007/s10208-019-09429-9
[55] Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. In STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing 694-703. ACM, New York. · Zbl 1315.68210
[56] McSherry, F. (2001). Spectral partitioning of random graphs. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) 529-537. IEEE Computer Soc., Los Alamitos, CA.
[57] Montanari, A. and Sen, S. (2016). Semidefinite programs on sparse random graphs and their application to community detection. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing 814-827. ACM, New York. · Zbl 1376.90043
[58] Mossel, E., Neeman, J. and Sly, A. (2014). Consistency thresholds for binary symmetric block models. ArXiv preprint. Available at arXiv:1407.1591. · Zbl 1321.05242
[59] Mossel, E., Neeman, J. and Sly, A. (2018). A proof of the block model threshold conjecture. Combinatorica 38 665-708. · Zbl 1424.05272 · doi:10.1007/s00493-016-3238-8
[60] Ng, A. Y., Jordan, M. I. and Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems.
[61] O’Rourke, S., Vu, V. and Wang, K. (2018). Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra Appl. 540 26-59. · Zbl 1380.65076 · doi:10.1016/j.laa.2017.11.014
[62] 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 arXiv:1609.05573. · Zbl 1404.62065 · doi:10.1214/17-AOS1625
[63] Rayleigh, J. W. S. (1896). The Theory of Sound, 2. Macmillan. · JFM 27.0701.05
[64] Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist. 39 1878-1915. · Zbl 1227.62042 · doi:10.1214/11-AOS887
[65] 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 arXiv:1611.00128.
[66] Schrödinger, E. (1926). Quantisierung als eigenwertproblem. Ann. Phys. 385 437-490. · JFM 52.0966.02 · doi:10.1002/andp.19263851302
[67] Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22 888-905.
[68] Shkolnisky, Y. and Singer, A. (2012). Viewing direction estimation in cryo-EM using synchronization. SIAM J. Imaging Sci. 5 1088-1110. · Zbl 1254.92058 · doi:10.1137/120863642
[69] Singer, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal. 30 20-36. · Zbl 1206.90116 · doi:10.1016/j.acha.2010.02.001
[70] Stewart, G. W. and Sun, J. G. (1990). Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic Press, Boston, MA. · Zbl 0706.65013
[71] Sun, R. and Luo, Z.-Q. (2016). Guaranteed matrix completion via non-convex factorization. IEEE Trans. Inform. Theory 62 6535-6579. · Zbl 1359.94179 · doi:10.1109/TIT.2016.2598574
[72] Sussman, D. L., Tang, M., Fishkind, D. E. and Priebe, C. E. (2012). A consistent adjacency spectral embedding for stochastic blockmodel graphs. J. Amer. Statist. Assoc. 107 1119-1128. · Zbl 1443.62188 · doi:10.1080/01621459.2012.699795
[73] Tron, R. and Vidal, R. (2009). Distributed image-based 3-D localization of camera sensor networks. In Decision and Control, 2009 Held Jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on IEEE. · Zbl 1360.94048 · doi:10.1109/TAC.2014.2351912
[74] Vu, V. (2018). A simple SVD algorithm for finding hidden partitions. Combin. Probab. Comput. 27 124-140. · Zbl 1386.68110 · doi:10.1017/S0963548317000463
[75] Wedin, P. (1972). Perturbation bounds in connection with singular value decomposition. BIT 12 99-111. · Zbl 0239.15015 · doi:10.1007/BF01932678
[76] Xia, D. and Zhou, F. (2017). The \(\ell_{\infty }\) perturbation of HOSVD and low rank tensor denoising. ArXiv preprint. Available at arXiv:1707.01207.
[77] Yun, S.-Y. and Proutiere, A. (2014). Accurate community detection in the stochastic block model via spectral algorithms. ArXiv preprint. Available at arXiv:1412.7335.
[78] Yun, S.-Y. and Proutiere, A. (2016). Optimal cluster recovery in the labeled stochastic block model. In Advances in Neural Information Processing Systems.
[79] Zhang, A. Y. and Zhou, H. H. (2016). Minimax rates of community detection in stochastic block models. Ann. Statist. 44 2252-2280. · Zbl 1355.60125 · doi:10.1214/15-AOS1428
[80] Zhong, Y. (2017). Eigenvector under random perturbation: A nonasymptotic Rayleigh-Schrödinger theory. ArXiv preprint. Available at arXiv:1702.00139.
[81] Zhong, Y. · Zbl 1396.90068 · doi:10.1137/17M1122025
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.