{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T08:43:16Z","timestamp":1793090596460,"version":"4.5.0"},"reference-count":61,"publisher":"Institute of Mathematical Statistics","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2019,10,1]]},"abstract":"<jats:p>The singular value matrix decomposition plays a ubiquitous role throughout statistics and related fields. Myriad applications including clustering, classification, and dimensionality reduction involve studying and exploiting the geometric structure of singular values and singular vectors. This paper provides a novel collection of technical and theoretical tools for studying the geometry of singular subspaces using the two-to-infinity norm. Motivated by preliminary deterministic Procrustes analysis, we consider a general matrix perturbation setting in which we derive a new Procrustean matrix decomposition. Together with flexible machinery developed for the two-to-infinity norm, this allows us to conduct a refined analysis of the induced perturbation geometry with respect to the underlying singular vectors even in the presence of singular value multiplicity. Our analysis yields singular vector entrywise perturbation bounds for a range of popular matrix noise models, each of which has a meaningful associated statistical inference task. In addition, we demonstrate how the two-to-infinity norm is the preferred norm in certain statistical settings. Specific applications discussed in this paper include covariance estimation, singular subspace recovery, and multiple graph inference. Both our Procrustean matrix decomposition and the technical machinery developed for the two-to-infinity norm may be of independent interest.<\/jats:p>","DOI":"10.1214\/18-aos1752","type":"journal-article","created":{"date-parts":[[2019,8,2]],"date-time":"2019-08-02T22:05:09Z","timestamp":1564783509000},"page":"2405-2439","source":"Crossref","is-referenced-by-count":77,"title":["The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics"],"prefix":"10.1214","volume":"47","author":[{"given":"Joshua","family":"Cape","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minh","family":"Tang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carey E.","family":"Priebe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] 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":"39","doi-asserted-by":"publisher","unstructured":"[39] Nadler, B. (2008). Finite sample approximation results for principal component analysis: A matrix perturbation approach. <i>Ann. Statist.<\/i> <b>36<\/b> 2791\u20132817.","DOI":"10.1214\/08-AOS618"},{"key":"45","doi-asserted-by":"publisher","unstructured":"[45] 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":"5","doi-asserted-by":"crossref","unstructured":"[5] Bhatia, R. (1997). <i>Matrix Analysis. Graduate Texts in Mathematics<\/i> <b>169<\/b>. Springer, New York.","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"1","unstructured":"[1] Abbe, E., Fan, J., Wang, K. and Zhong, Y. (2017). Entrywise eigenvector analysis of random matrices with low expected rank. Preprint. Available at <a href=\"arXiv:1709.09565\">arXiv:1709.09565<\/a>."},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] 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":"6","doi-asserted-by":"publisher","unstructured":"[6] Bojanczyk, A. W. and Lutoborski, A. (1999). The Procrustes problem for orthogonal Stiefel matrices. <i>SIAM J. Sci. Comput.<\/i> <b>21<\/b> 1291\u20131304.","DOI":"10.1137\/S106482759630992X"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] Cai, T. T., Ma, Z. and Wu, Y. (2013). Sparse PCA: Optimal rates and adaptive estimation. <i>Ann. Statist.<\/i> <b>41<\/b> 3074\u20133110.","DOI":"10.1214\/13-AOS1178"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] Cai, T. T. and Zhang, A. (2018). Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. <i>Ann. Statist.<\/i> <b>46<\/b> 60\u201389.","DOI":"10.1214\/17-AOS1541"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] 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":"10","doi-asserted-by":"publisher","unstructured":"[10] Cape, J., Tang, M. and Priebe, C. E. (2018). Signal-plus-noise matrix models: Eigenvector deviations and fluctuations. <i>Biometrika<\/i>. To appear. Available at <a href=\"arXiv:1802.00381\">arXiv:1802.00381<\/a>.","DOI":"10.1093\/biomet\/asy070"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] Chen, L., Vogelstein, J. T., Lyzinski, V. and Priebe, C. E. (2016). A joint graph inference case study: The C. elegans chemical and electrical connectome. <i>Worm<\/i> <b>5<\/b> 1\u20138.","DOI":"10.1080\/21624054.2016.1142041"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] Chikuse, Y. (2003). <i>Statistics on Special Manifolds. Lecture Notes in Statistics<\/i> <b>174<\/b>. Springer, New York.","DOI":"10.1007\/978-0-387-21540-2"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] Dryden, I. L., Koloydenko, A. and Zhou, D. (2009). Non-Euclidean statistics for covariance matrices, with applications to diffusion tensor imaging. <i>Ann. Appl. Stat.<\/i> <b>3<\/b> 1102\u20131123.","DOI":"10.1214\/09-AOAS249"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] Edelman, A., Arias, T. A. and Smith, S. T. (1999). The geometry of algorithms with orthogonality constraints. <i>SIAM J. Matrix Anal. Appl.<\/i> <b>20<\/b> 303\u2013353.","DOI":"10.1137\/S0895479895290954"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] Fan, J., Liao, Y. and Mincheva, M. (2013). Large covariance estimation by thresholding principal orthogonal complements. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>75<\/b> 603\u2013680.","DOI":"10.1111\/rssb.12016"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] Fan, J., Rigollet, P. and Wang, W. (2015). Estimation of functionals of sparse covariance matrices. <i>Ann. Statist.<\/i> <b>43<\/b> 2706\u20132737.","DOI":"10.1214\/15-AOS1357"},{"key":"21","unstructured":"[21] 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> 1\u201342."},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] Fishkind, D. E., Sussman, D. L., Tang, M., Vogelstein, J. T. and Priebe, C. E. (2013). Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown. <i>SIAM J. Matrix Anal. Appl.<\/i> <b>34<\/b> 23\u201339.","DOI":"10.1137\/120875600"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] Gower, J. C. and Dijksterhuis, G. B. (2004). <i>Procrustes Problems. Oxford Statistical Science Series<\/i> <b>30<\/b>. Oxford Univ. Press, Oxford.","DOI":"10.1093\/acprof:oso\/9780198510581.001.0001"},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] 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":"26","doi-asserted-by":"publisher","unstructured":"[26] Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. <i>Ann. Statist.<\/i> <b>29<\/b> 295\u2013327.","DOI":"10.1214\/aos\/1009210544"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Koltchinskii, V. and Lounici, K. (2017). Concentration inequalities and moment bounds for sample covariance operators. <i>Bernoulli<\/i> <b>23<\/b> 110\u2013133.","DOI":"10.3150\/15-BEJ730"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[29] Koltchinskii, V. and Lounici, K. (2017). New asymptotic results in principal component analysis. <i>Sankhy\u0101 A<\/i> <b>79<\/b> 254\u2013297.","DOI":"10.1007\/s13171-017-0106-6"},{"key":"30","doi-asserted-by":"publisher","unstructured":"[30] Le, C. M., Levina, E. and Vershynin, R. (2016). Optimization via low-rank approximation for community detection in networks. <i>Ann. Statist.<\/i> <b>44<\/b> 373\u2013400.","DOI":"10.1214\/15-AOS1360"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[31] 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":"32","doi-asserted-by":"crossref","unstructured":"[32] Levin, K., Athreya, A., Tang, M., Lyzinski, V. and Priebe, C. E. (2017). A central limit theorem for an omnibus embedding of random dot product graphs. Preprint. Available at <a href=\"arXiv:1705.09355\">arXiv:1705.09355<\/a>.","DOI":"10.1109\/ICDMW.2017.132"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] Lu, L. and Peng, X. (2013). Spectra of edge-independent random graphs. <i>Electron. J. Combin.<\/i> <b>20<\/b> 1\u201318.","DOI":"10.37236\/3576"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] Lyzinski, V. (2018). Information recovery in shuffled graphs via graph matching. <i>IEEE Trans. Inform. Theory<\/i> <b>64<\/b> 3254\u20133273.","DOI":"10.1109\/TIT.2018.2808999"},{"key":"35","doi-asserted-by":"crossref","unstructured":"[35] Lyzinski, V., Park, Y., Priebe, C. E. and Trosset, M. (2017). Fast embedding for JOFC using the raw stress criterion. <i>J. Comput. Graph. Statist.<\/i> <b>26<\/b> 786\u2013802.","DOI":"10.1080\/10618600.2017.1321551"},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] Lyzinski, V., Sussman, D. L., Fishkind, D. E., Pao, H., Chen, L., Vogelstein, J. T., Park, Y. and Priebe, C. E. (2015). Spectral clustering for divide-and-conquer graph matching. <i>Parallel Comput.<\/i> <b>47<\/b> 70\u201387.","DOI":"10.1016\/j.parco.2015.03.004"},{"key":"37","doi-asserted-by":"publisher","unstructured":"[37] Lyzinski, V., Sussman, D. L., Tang, M., Athreya, A. and Priebe, C. E. (2014). Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. <i>Electron. J. Stat.<\/i> <b>8<\/b> 2905\u20132922.","DOI":"10.1214\/14-EJS978"},{"key":"38","unstructured":"[38] Mao, X., Sarkar, P. and Chakrabarti, D. (2017). Estimating mixed memberships with sharp eigenvector deviations. Preprint. Available at <a href=\"arXiv:1709.00407\">arXiv:1709.00407<\/a>."},{"key":"40","doi-asserted-by":"publisher","unstructured":"[40] O\u2019Rourke, S., Vu, V. and Wang, K. (2016). Eigenvectors of random matrices: A survey. <i>J. Combin. Theory Ser. A<\/i> <b>144<\/b> 361\u2013442.","DOI":"10.1016\/j.jcta.2016.06.008"},{"key":"41","doi-asserted-by":"publisher","unstructured":"[41] 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":"42","doi-asserted-by":"publisher","unstructured":"[42] Paul, D. and Aue, A. (2014). Random matrix theory in statistics: A review. <i>J. Statist. Plann. Inference<\/i> <b>150<\/b> 1\u201329.","DOI":"10.1016\/j.jspi.2013.09.005"},{"key":"43","doi-asserted-by":"publisher","unstructured":"[43] Priebe, C. E., Marchette, D. J., Ma, Z. and Adali, S. (2013). Manifold matching: Joint optimization of fidelity and commensurability. <i>Braz. J. Probab. Stat.<\/i> <b>27<\/b> 377\u2013400.","DOI":"10.1214\/12-BJPS188"},{"key":"44","doi-asserted-by":"publisher","unstructured":"[44] Rebrova, E. and Vershynin, R. (2018). Norms of random matrices: Local and global problems. <i>Adv. Math.<\/i> <b>324<\/b> 40\u201383.","DOI":"10.1016\/j.aim.2017.11.001"},{"key":"46","doi-asserted-by":"publisher","unstructured":"[46] Rudelson, M. and Vershynin, R. (2015). Delocalization of eigenvectors of random matrices with independent entries. <i>Duke Math. J.<\/i> <b>164<\/b> 2507\u20132538.","DOI":"10.1215\/00127094-3129809"},{"key":"47","doi-asserted-by":"publisher","unstructured":"[47] Sarkar, P. and Bickel, P. J. (2015). Role of normalization in spectral clustering for stochastic blockmodels. <i>Ann. Statist.<\/i> <b>43<\/b> 962\u2013990.","DOI":"10.1214\/14-AOS1285"},{"key":"49","doi-asserted-by":"publisher","unstructured":"[49] 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":"50","doi-asserted-by":"crossref","unstructured":"[50] Sussman, D. L., Tang, M. and Priebe, C. E. (2014). Consistent latent position estimation and vertex classification for random dot product graphs. <i>IEEE Trans. Pattern Anal. Mach. Intell.<\/i> <b>36<\/b> 48\u201357.","DOI":"10.1109\/TPAMI.2013.135"},{"key":"51","doi-asserted-by":"publisher","unstructured":"[51] Tang, M., Athreya, A., Sussman, D. L., Lyzinski, V., Park, Y. and Priebe, C. E. (2017). A semiparametric two-sample hypothesis testing problem for random graphs. <i>J. Comput. Graph. Statist.<\/i> <b>26<\/b> 344\u2013354.","DOI":"10.3150\/15-BEJ789"},{"key":"52","doi-asserted-by":"publisher","unstructured":"[52] Tang, M., Athreya, A., Sussman, D. L., Lyzinski, V. and Priebe, C. E. (2017). A nonparametric two-sample hypothesis testing problem for random graphs. <i>Bernoulli<\/i> <b>23<\/b> 1599\u20131630.","DOI":"10.3150\/15-BEJ789"},{"key":"53","unstructured":"[53] Tang, M., Cape, J. and Priebe, C. E. (2017). Asymptotically efficient estimators for stochastic blockmodels: The naive MLE, the rank-constrained MLE, and the spectral. Preprint. Available at <a href=\"arXiv:1710.10936\">arXiv:1710.10936<\/a>."},{"key":"54","doi-asserted-by":"publisher","unstructured":"[54] Tang, M. and Priebe, C. E. (2018). Limit theorems for eigenvectors of the normalized Laplacian for random graphs. <i>Ann. Statist.<\/i> <b>46<\/b> 2360\u20132415.","DOI":"10.1214\/17-AOS1623"},{"key":"56","doi-asserted-by":"crossref","unstructured":"[56] von Luxburg, U. (2007). A tutorial on spectral clustering. <i>Stat. Comput.<\/i> <b>17<\/b> 395\u2013416.","DOI":"10.1007\/s11222-007-9033-z"},{"key":"57","doi-asserted-by":"publisher","unstructured":"[57] Wedin, P. (1972). Perturbation bounds in connection with singular value decomposition. <i>BIT<\/i> <b>12<\/b> 99\u2013111.","DOI":"10.1007\/BF01932678"},{"key":"58","doi-asserted-by":"publisher","unstructured":"[58] Weyl, H. (1912). Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung). <i>Math. Ann.<\/i> <b>71<\/b> 441\u2013479.","DOI":"10.1007\/BF01456804"},{"key":"59","doi-asserted-by":"crossref","unstructured":"[59] Yao, J., Zheng, S. and Bai, Z. (2015). <i>Large Sample Covariance Matrices and High-Dimensional Data Analysis. Cambridge Series in Statistical and Probabilistic Mathematics<\/i> <b>39<\/b>. Cambridge Univ. Press, New York.","DOI":"10.1017\/CBO9781107588080"},{"key":"60","doi-asserted-by":"crossref","unstructured":"[60] Young, S. J. and Scheinerman, E. R. (2007). Random dot product graph models for social networks. In <i>Algorithms and Models for the Web-Graph. Lecture Notes in Computer Science<\/i> <b>4863<\/b> 138\u2013149. Springer, Berlin.","DOI":"10.1007\/978-3-540-77004-6_11"},{"key":"61","doi-asserted-by":"publisher","unstructured":"[61] Yu, Y., Wang, T. and Samworth, R. J. (2015). A useful variant of the Davis\u2013Kahan theorem for statisticians. <i>Biometrika<\/i> <b>102<\/b> 315\u2013323.","DOI":"10.1093\/biomet\/asv008"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] Bai, Z. and Silverstein, J. W. (2010). <i>Spectral Analysis of Large Dimensional Random Matrices<\/i>, 2nd ed. <i>Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4419-0661-8"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] Benidis, K., Sun, Y., Babu, P. and Palomar, D. P. (2016). Orthogonal sparse eigenvectors: A Procrustes problem. In: <i>IEEE International Conference on Acoustics<\/i>, <i>Speech and Signal Processing<\/i> (<i>ICASSP<\/i>) 4683\u20134686.","DOI":"10.1109\/ICASSP.2016.7472565"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Dryden, I. L. and Mardia, K. V. (2016). <i>Statistical Shape Analysis with Applications in R<\/i>, 2nd ed. <i>Wiley Series in Probability and Statistics<\/i>. Wiley, Chichester.","DOI":"10.1002\/9781119072492"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Eldar, Y. C. and Kutyniok, G. (2012). <i>Compressed Sensing<\/i>: <i>Theory and Applications<\/i>. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/CBO9780511794308"},{"key":"18","unstructured":"[18] Eldridge, J., Belkin, M. and Wang, Y. (2018). Unperturbed: Spectral analysis beyond Davis-Kahan. In: <i>Proceedings of Algorithmic Learning Theory. Proceedings of Machine Learning Research<\/i> 83, PMLR 321\u2013358."},{"key":"25","unstructured":"[25] Horn, R. A. and Johnson, C. R. (2012). <i>Matrix Analysis<\/i>. Cambridge Univ. Press, Cambridge."},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Jolliffe, I. T. (1986). <i>Principal Component Analysis. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4757-1904-8"},{"key":"48","unstructured":"[48] Stewart, G. W. and Sun, J. G. (1990). <i>Matrix Perturbation Theory. Computer Science and Scientific Computing<\/i>. Academic Press, Boston, MA."},{"key":"55","doi-asserted-by":"crossref","unstructured":"[55] Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science. Online version 2018-02-09.","DOI":"10.1017\/9781108231596"}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1564797852","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T16:27:47Z","timestamp":1791476867000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-47\/issue-5\/The-two-to-infinity-norm-and-singular-subspace-geometry-with\/10.1214\/18-AOS1752.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,1]]},"references-count":61,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,10,1]]}},"URL":"https:\/\/doi.org\/10.1214\/18-aos1752","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,1]]}}}