Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees. (English) Zbl 1471.62371
This paper is concerned with estimating the column space of an unknown low-rank matrix \(A^\ast \in \mathbb R^{d_1\times d_2}\) , given noisy and partial observations of its entries. The authors investigate an efficient spectral method, which operates upon the sample Gram matrix with diagonal deletion. The definition of Gram matrix and the algorithm of spectral method on the diagonal-deleted Gram matrix are given. While this algorithmic idea has been studied before, they establish new statistical guarantees for this method in terms of both \(\ell_2\) and \(\ell_{2,\infty}\) estimation accuracy, which improve upon prior results if \(d_2\) is substantially larger than \(d_1\). The consequences of general theory for three applications of practical importance are established: (1) tensor completion from noisy data, (2) covariance estimation/principal component analysis with missing data and (3) community recovery in bipartite graphs.
Reviewer: Rózsa Horváth-Bokor (Budakalász)
MSC:
| 62H12 | Estimation in multivariate analysis |
| 62H25 | Factor analysis and principal components; correspondence analysis |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62D10 | Missing data |
Keywords:
covariance estimation; leave-one-out analysis; missing data; principal component analysis; spectral clustering; spectral method; tensor completionReferences:
| [1] | Abbe, E. (2017). Community detection and stochastic block models: Recent developments. J. Mach. Learn. Res. 18 6446-6531. · Zbl 1403.62110 |
| [2] | Abbe, E., Bandeira, A. S. and Hall, G. (2016). Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory 62 471-487. · Zbl 1359.94047 · doi:10.1109/TIT.2015.2490670 |
| [3] | Abbe, E., Fan, J. and Wang, K. (2020). An \[{\ell_p}\] theory of PCA and spectral clustering. Preprint. Available at arXiv:2006.14062. |
| [4] | Abbe, E., Fan, J., Wang, K. and Zhong, Y. (2017). Entrywise eigenvector analysis of random matrices with low expected rank. Preprint. Available at arXiv:1709.09565. · Zbl 1450.62066 |
| [5] | Agarwal, A., Shah, D., Shen, D. and Song, D. (2019). On robustness of principal component regression. In Advances in Neural Information Processing Systems 9893-9903. |
| [6] | 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. |
| [7] | Alzahrani, T. and Horadam, K. J. (2016). Community detection in bipartite networks: Algorithms and case studies. In Complex Systems and Networks. Underst. Complex Syst. 25-50. Springer, Heidelberg. |
| [8] | 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 |
| [9] | Bai, Z. and Yao, J. (2012). On sample eigenvalues in a generalized spiked population model. J. Multivariate Anal. 106 167-177. · Zbl 1301.62049 · doi:10.1016/j.jmva.2011.10.009 |
| [10] | 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 |
| [11] | Barak, B. and Moitra, A. (2016). Noisy tensor completion via the sum-of-squares hierarchy. In Proceedings of the Conference on Learning Theory 417-445. |
| [12] | Bickel, P. J. and Levina, E. (2008). Covariance regularization by thresholding. Ann. Statist. 36 2577-2604. · Zbl 1196.62062 · doi:10.1214/08-AOS600 |
| [13] | Cai, C., Li, G., Chi, Y., Poor, H. V. and Chen, Y. (2021). Supplement to “Subspace estimation from unbalanced and incomplete data matrices: \[{\ell_{2,\infty }}\] statistical guarantees.” https://doi.org/10.1214/20-AOS1986SUPP |
| [14] | Cai, C., Li, G., Poor, H. V. and Chen, Y. (2019). Nonconvex low-rank tensor completion from noisy data. In Advances in Neural Information Processing Systems 1861-1872. |
| [15] | Cai, C., Poor, H. V. and Chen, Y. (2020). Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality. In Proceedings of the International Conference on Machine Learning. To appear. Available at arXiv:2006.08580. |
| [16] | Cai, T., Ma, Z. and Wu, Y. (2015). Optimal estimation and rank detection for sparse spiked covariance matrices. Probab. Theory Related Fields 161 781-815. · Zbl 1314.62130 · doi:10.1007/s00440-014-0562-z |
| [17] | Cai, T. T. and Li, X. (2015). Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann. Statist. 43 1027-1059. · Zbl 1328.62381 · doi:10.1214/14-AOS1290 |
| [18] | Cai, T. T., Ma, Z. and Wu, Y. (2013). Sparse PCA: Optimal rates and adaptive estimation. Ann. Statist. 41 3074-3110. · Zbl 1288.62099 · doi:10.1214/13-AOS1178 |
| [19] | Cai, T. T. and Yuan, M. (2012). Adaptive covariance matrix estimation through block thresholding. Ann. Statist. 40 2014-2042. · Zbl 1257.62060 · doi:10.1214/12-AOS999 |
| [20] | Cai, T. T. and Zhang, A. (2016). Minimax rate-optimal estimation of high-dimensional covariance matrices with incomplete data. J. Multivariate Anal. 150 55-74. · Zbl 1347.62088 · doi:10.1016/j.jmva.2016.05.002 |
| [21] | 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 |
| [22] | Candès, E. J. and Tao, T. (2010). The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inf. Theory 56 2053-2080. · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061 |
| [23] | Cape, J., Tang, M. and Priebe, C. E. (2019). The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. Ann. Statist. 47 2405-2439. · Zbl 1470.62065 · doi:10.1214/18-AOS1752 |
| [24] | Cape, J., Tang, M. and Priebe, C. E. (2019). Signal-plus-noise matrix models: Eigenvector deviations and fluctuations. Biometrika 106 243-250. · Zbl 1506.62300 · doi:10.1093/biomet/asy070 |
| [25] | Chatterjee, S. (2015). Matrix estimation by universal singular value thresholding. Ann. Statist. 43 177-214. · Zbl 1308.62038 · doi:10.1214/14-AOS1272 |
| [26] | Chen, Y. and Candès, E. J. (2018). The projected power method: An efficient algorithm for joint alignment from pairwise differences. Comm. Pure Appl. Math. 71 1648-1714. · Zbl 1480.90199 · doi:10.1002/cpa.21760 |
| [27] | Chen, Y., Cheng, C. and Fan, J. (2020). Asymmetry helps: Eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices. Ann. Statist. To appear. Available at arXiv:1811.12804. · Zbl 1461.62085 |
| [28] | Chen, Y. and Chi, Y. (2018). Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization. IEEE Signal Process. Mag. 35 14-31. |
| [29] | Chen, Y., Chi, Y., Fan, J., Ma, C. and Yan, Y. (2019). Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. Preprint. Available at arXiv:1902.07698. · Zbl 1477.90060 |
| [30] | 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 |
| [31] | Chen, Y., Kamath, G., Suh, C. and Tse, D. (2016). Community recovery in graphs with locality. In Proceedings of the International Conference on Machine Learning 689-698. |
| [32] | Chen, Y., Li, X. and Xu, J. (2018). Convexified modularity maximization for degree-corrected stochastic block models. Ann. Statist. 46 1573-1602. · Zbl 1410.62105 · doi:10.1214/17-AOS1595 |
| [33] | Chen, Y., Suh, C. and Goldsmith, A. J. (2016). Information recovery from pairwise measurements. IEEE Trans. Inf. Theory 62 5881-5905. · Zbl 1359.94945 · doi:10.1109/TIT.2016.2600566 |
| [34] | Chen, Y. and Wainwright, M. J. (2015). Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. Available at arXiv:1509.03025. |
| [35] | Cheng, C., Wei, Y. and Chen, Y. (2020). Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise. Preprint. Available at arXiv:2001.04620. |
| [36] | Chi, Y., Lu, Y. M. and Chen, Y. (2019). Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Trans. Signal Process. 67 5239-5269. · Zbl 1543.90234 · doi:10.1109/TSP.2019.2937282 |
| [37] | 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 Proceedings of the Conference on Learning Theory 391-423. |
| [38] | Cho, J., Kim, D. and Rohe, K. (2017). Asymptotic theory for estimating the singular vectors and values of a partially-observed low rank matrix with noise. Statist. Sinica 27 1921-1948. · Zbl 1392.62150 |
| [39] | 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 |
| [40] | Coja-Oghlan, A. (2010). Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput. 19 227-284. · Zbl 1209.05178 · doi:10.1017/S0963548309990514 |
| [41] | Dhillon, I. S. (2001). Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 269-274. ACM, New York. |
| [42] | Eldridge, J., Belkin, M. and Wang, Y. (2018). Unperturbed: Spectral analysis beyond Davis-Kahan. In Proceedigs of the 29th Conference on Algorithmic Learning Theory 321-358. · Zbl 1406.60014 |
| [43] | Elsener, A. and van de Geer, S. (2019). Sparse spectral estimation with missing and corrupted measurements. Stat 8 e229, 11. · Zbl 1443.62148 · doi:10.1002/sta4.229 |
| [44] | Fan, J., Wang, K., Zhong, Y. and Zhu, Z. (2018). Robust high dimensional factor models with applications to statistical machine learning. Preprint. Available at arXiv:1808.03889. |
| [45] | Fan, J., Wang, W. and Zhong, Y. (2018). An \[{\ell_{\infty }}\] eigenvector perturbation bound and its application to robust covariance estimation. J. Mach. Learn. Res. 18 1-42. · Zbl 1473.15015 |
| [46] | Feldman, V., Perkins, W. and Vempala, S. (2015). Subsampled power iteration: A unified algorithm for block models and planted csp’s. In Advances in Neural Information Processing Systems 2836-2844. |
| [47] | Florescu, L. and Perkins, W. (2016). Spectral thresholds in the bipartite stochastic block model. In Proceedings of the Conference on Learning Theory 943-959. |
| [48] | Gandy, S., Recht, B. and Yamada, I. (2011). Tensor completion and low-\(n\)-rank tensor recovery via convex optimization. Inverse Probl. 27 025010, 19. · Zbl 1211.15036 · doi:10.1088/0266-5611/27/2/025010 |
| [49] | Gao, C., Lu, Y., Ma, Z. and Zhou, H. H. (2016). Optimal estimation and completion of matrices with biclustering structures. J. Mach. Learn. Res. 17 5602-5630. · Zbl 1392.62151 |
| [50] | 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 1980-2024. · Zbl 1440.62244 |
| [51] | Ghassemi, M., Shakeri, Z., Sarwate, A. D. and Bajwa, W. U. (2017). STARK: Structured dictionary learning through rank-one tensor recovery. In Proceedings of the 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing 1-5. IEEE, New York. |
| [52] | Gonen, A., Rosenbaum, D., Eldar, Y. and Shalev-Shwartz, S. (2016). Subspace learning with partial information. J. Mach. Learn. Res. 17 1821-1841. · Zbl 1360.68676 |
| [53] | Gross, D. (2011). Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57 1548-1566. · Zbl 1366.94103 · doi:10.1109/TIT.2011.2104999 |
| [54] | 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 |
| [55] | Hajek, B., Wu, Y. and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Trans. Inf. Theory 62 5918-5937. · Zbl 1359.94951 · doi:10.1109/TIT.2016.2594812 |
| [56] | Hao, B., Zhang, A. and Cheng, G. (2018). Sparse and low-rank tensor estimation via cubic sketchings. Preprint. Available at arXiv:1801.09326. · Zbl 1448.62072 |
| [57] | Hopkins, S. B., Shi, J., Schramm, T. and Steurer, D. (2016). Fast spectral algorithms from sum-of-squares proofs: Tensor decomposition and planted sparse vectors. In Proceedings of the 48th ACM Symposium on Theory of Computing 178-191. ACM, New York. · Zbl 1377.68199 · doi:10.1145/2897518.2897529 |
| [58] | Jain, P., Netrapalli, P. and Sanghavi, S. (2013). Low-rank matrix completion using alternating minimization (extended abstract). In Proceedings of the 45th ACM Symposium on Theory of Computing 665-674. ACM, New York. · Zbl 1293.65073 · doi:10.1145/2488608.2488693 |
| [59] | Jain, P. and Oh, S. (2014). Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems 1431-1439. |
| [60] | Jalali, A., Chen, Y., Sanghavi, S. and Xu, H. (2011). Clustering partially observed graphs via convex optimization. In Proceedings of the International Conference on Machine Learning 11 1001-1008. · Zbl 1319.62123 |
| [61] | 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 |
| [62] | Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist. 29 295-327. · Zbl 1016.62078 · doi:10.1214/aos/1009210544 |
| [63] | Johnstone, I. M. and Lu, A. Y. (2009). On consistency and sparsity for principal components analysis in high dimensions. J. Amer. Statist. Assoc. 104 682-693. · Zbl 1388.62174 · doi:10.1198/jasa.2009.0121 |
| [64] | Josse, J. and Husson, F. (2012). Handling missing values in exploratory multivariate data analysis methods. J. SFdS 153 79-99. · Zbl 1316.62006 |
| [65] | Keshavan, R. H., Montanari, A. and Oh, S. (2010). Matrix completion from a few entries. IEEE Trans. Inf. Theory 56 2980-2998. · Zbl 1366.62111 · doi:10.1109/TIT.2010.2046205 |
| [66] | Keshavan, R. H., Montanari, A. and Oh, S. (2010). Matrix completion from noisy entries. J. Mach. Learn. Res. 11 2057-2078. · Zbl 1242.62069 |
| [67] | Kiers, H. A. (1997). Weighted least squares fitting using ordinary least squares algorithms. Psychometrika 62 251-266. · Zbl 0873.62058 |
| [68] | Kim, H.-J., Ollila, E., Koivunen, V. and Croux, C. (2013). Robust and sparse estimation of tensor decompositions. In Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing 965-968. IEEE. |
| [69] | 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 |
| [70] | 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 · doi:10.1007/978-3-319-40519-3_18 |
| [71] | Larremore, D. B., Clauset, A. and Jacobs, A. Z. (2014). Efficiently inferring community structure in bipartite networks. Phys. Rev. E 90 012805. |
| [72] | Lawley, D. N. and Maxwell, A. E. (1962). Factor analysis as a statistical method. Journal of the Royal Statistical Society. Series D (The Statistician) 12 209-229. |
| [73] | 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 |
| [74] | Lei, L. (2019). Unified \[{\ell_{2\to \infty }}\] eigenspace perturbation theory for symmetric random matrices. Preprint. Available at arXiv:1909.04798. |
| [75] | Lelarge, M., Massoulié, L. and Xu, J. (2015). Reconstruction in the labelled stochastic block model. IEEE Trans. Netw. Sci. Eng. 2 152-163. · doi:10.1109/TNSE.2015.2490580 |
| [76] | Liu, J., Musialski, P., Wonka, P. and Ye, J. (2013). Tensor completion for estimating missing values in visual data. IEEE Trans. Pattern Anal. Mach. Intell. 35 208-220. |
| [77] | Loh, P.-L. and Wainwright, M. J. (2012). High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity. Ann. Statist. 40 1637-1664. · Zbl 1257.62063 · doi:10.1214/12-AOS1018 |
| [78] | Lounici, K. (2013). Sparse principal component analysis with missing observations. In High Dimensional Probability VI. Progress in Probability 66 327-356. Birkhäuser/Springer, Basel. · Zbl 1267.62073 |
| [79] | Lounici, K. (2014). High-dimensional covariance matrix estimation with missing observations. Bernoulli 20 1029-1058. · Zbl 1320.62124 · doi:10.3150/12-BEJ487 |
| [80] | Ma, C., Wang, K., Chi, Y. and Chen, Y. (2020). Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Found. Comput. Math. 20 451-632. · Zbl 1445.90089 · doi:10.1007/s10208-019-09429-9 |
| [81] | Ma, Z. (2013). Sparse principal component analysis and iterative thresholding. Ann. Statist. 41 772-801. · Zbl 1267.62074 · doi:10.1214/13-AOS1097 |
| [82] | Mao, X., Sarkar, P. and Chakrabarti, D. (2017). Estimating mixed memberships with sharp eigenvector deviations. Preprint. Available at arXiv:1709.00407. |
| [83] | Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. In Proceedings of the 46th ACM Symposium on Theory of Computing 694-703. ACM, New York. · Zbl 1315.68210 |
| [84] | Montanari, A. and Sun, N. (2018). Spectral algorithms for tensor completion. Comm. Pure Appl. Math. 71 2381-2425. · Zbl 1404.15023 · doi:10.1002/cpa.21748 |
| [85] | Mossel, E., Neeman, J. and Sly, A. (2014). Consistency thresholds for binary symmetric block models. Preprint. Available at arXiv:1407.1591. · Zbl 1321.05242 |
| [86] | Mossel, E., Neeman, J. and Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probab. Theory Related Fields 162 431-461. · Zbl 1320.05113 · doi:10.1007/s00440-014-0576-6 |
| [87] | Mu, C., Huang, B., Wright, J. and Goldfarb, D. (2014). Square deal: Lower bounds and improved relaxations for tensor recovery. In Proceedings of the International Conference on Machine Learning 73-81. |
| [88] | Nadler, B. (2008). Finite sample approximation results for principal component analysis: A matrix perturbation approach. Ann. Statist. 36 2791-2817. · Zbl 1168.62058 · doi:10.1214/08-AOS618 |
| [89] | 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 |
| [90] | Pananjady, A. and Wainwright, M. J. (2019). Value function estimation in Markov reward processes: Instance-dependent \[{\ell_{\infty }}\]-bounds for policy evaluation. Preprint. Available at arXiv:1909.08749. |
| [91] | Paul, D. (2007). Asymptotics of sample eigenstructure for a large dimensional spiked covariance model. Statist. Sinica 17 1617-1642. · Zbl 1134.62029 |
| [92] | Pavez, E. and Ortega, A. (2019). Covariance matrix estimation with non uniform and data dependent missing observations. Preprint. Available at arXiv:1910.00667. · Zbl 1465.62100 |
| [93] | Potechin, A. and Steurer, D. (2017). Exact tensor completion with sum-of-squares. In Proceedings of the Conference on Learning Theory 1619-1673. |
| [94] | Richard, E. and Montanari, A. (2014). A statistical model for tensor PCA. In Advances in Neural Information Processing Systems 2897-2905. |
| [95] | 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 |
| [96] | Romera-Paredes, B. and Pontil, M. (2013). A new convex relaxation for tensor completion. In Advances in Neural Information Processing Systems 2967-2975. |
| [97] | Rudelson, M. and Vershynin, R. (2015). Delocalization of eigenvectors of random matrices with independent entries. Duke Math. J. 164 2507-2538. · Zbl 1352.60007 · doi:10.1215/00127094-3129809 |
| [98] | Salmi, J., Richter, A. and Koivunen, V. (2009). Sequential unfolding SVD for tensors with applications in array signal processing. IEEE Trans. Signal Process. 57 4719-4733. · Zbl 1392.94433 · doi:10.1109/TSP.2009.2027740 |
| [99] | Semerci, O., Hao, N., Kilmer, M. E. and Miller, E. L. (2014). Tensor-based formulation and nuclear norm regularization for multienergy computed tomography. IEEE Trans. Image Process. 23 1678-1693. · Zbl 1374.94335 · doi:10.1109/TIP.2014.2305840 |
| [100] | Shen, Y., Huang, Q., Srebro, N. and Sanghavi, S. (2016). Normalized spectral map synchronization. In Advances in Neural Information Processing Systems 4925-4933. |
| [101] | 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 |
| [102] | Sun, R. and Luo, Z.-Q. (2016). Guaranteed matrix completion via non-convex factorization. IEEE Trans. Inf. Theory 62 6535-6579. · Zbl 1359.94179 · doi:10.1109/TIT.2016.2598574 |
| [103] | 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 |
| [104] | Vu, V. (2018). A simple SVD algorithm for finding hidden partitions. Combin. Probab. Comput. 27 124-140. · Zbl 1386.68110 · doi:10.1017/S0963548317000463 |
| [105] | Wedin, P. (1973). Perturbation theory for pseudo-inverses. Nordisk Tidskr. Informationsbehandling (BIT) 13 217-232. · Zbl 0263.65047 · doi:10.1007/bf01933494 |
| [106] | Xia, D. and Yuan, M. (2019). On polynomial time methods for exact low-rank tensor completion. Found. Comput. Math. 19 1265-1313. · Zbl 1436.15031 · doi:10.1007/s10208-018-09408-6 |
| [107] | Xia, D., Yuan, M. and Zhang, C.-H. (2017). Statistically optimal and computationally efficient low rank tensor completion from noisy entries. Preprint. Available at arXiv:1711.04934. · Zbl 1473.62184 |
| [108] | Xia, D. and Zhou, F. (2019). The sup-norm perturbation of HOSVD and low rank tensor denoising. J. Mach. Learn. Res. 20 61-1. · Zbl 1489.62169 |
| [109] | Yuan, M. and Zhang, C.-H. (2016). On tensor completion via nuclear norm minimization. Found. Comput. Math. 16 1031-1068. · Zbl 1378.90066 · doi:10.1007/s10208-015-9269-5 |
| [110] | Yuan, M. and Zhang, C.-H. (2017). Incoherent tensor norms and their applications in higher order tensor completion. IEEE Trans. Inf. Theory 63 6753-6766. · Zbl 1391.94469 · doi:10.1109/TIT.2017.2724549 |
| [111] | Yun, S.-Y. and Proutiere, A. (2014). Accurate community detection in the stochastic block model via spectral algorithms. Preprint. Available at arXiv:1412.7335. |
| [112] | Yun, S.-Y. and Proutiere, A. (2016). Optimal cluster recovery in the labeled stochastic block model. In Advances in Neural Information Processing Systems 965-973. |
| [113] | Zhang, A., Cai, T. T. and Wu, Y. (2018). Heteroskedastic PCA: Algorithm, optimality, and applications. Preprint. Available at arXiv:1810.08316v2. |
| [114] | Zhang, A. and Xia, D. (2018). Tensor SVD: Statistical and computational limits. IEEE Trans. Inf. Theory 64 7311-7338. · Zbl 1432.62176 · doi:10.1109/TIT.2018.2841377 |
| [115] | Zhong, Y. and Boumal, N. (2018). Near-optimal bounds for phase synchronization. SIAM J. Optim. 28 989-1016. · Zbl 1396.90068 · doi:10.1137/17M1122025 |
| [116] | Zhou, Z. and Amini, A. A. (2018). Optimal bipartite network clustering. Preprint. Available at arXiv:1803.06031. · Zbl 1498.68281 |
| [117] | Zhu, Z., Wang, T. and Samworth, R. J. (2019). High-dimensional principal component analysis with heterogeneous missingness. Preprint. Available at arXiv:1906.12125 |
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.
