{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T20:53:31Z","timestamp":1791406411164,"version":"4.3.3"},"reference-count":80,"publisher":"Institute of Mathematical Statistics","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2021,10,1]]},"abstract":"<jats:p>This paper delivers improved theoretical guarantees for the convex programming approach in low-rank matrix estimation, in the presence of (1) random noise, (2) gross sparse outliers and (3) missing data. This problem, often dubbed as robust principal component analysis (robust PCA), finds applications in various domains. Despite the wide applicability of convex relaxation, the available statistical support (particularly the stability analysis in the presence of random noise) remains highly suboptimal, which we strengthen in this paper. When the unknown matrix is well conditioned, incoherent and of constant rank, we demonstrate that a principled convex program achieves near-optimal statistical accuracy, in terms of both the Euclidean loss and the \u2113\u221e loss. All of this happens even when nearly a constant fraction of observations are corrupted by outliers with arbitrary magnitudes. The key analysis idea lies in bridging the convex program in use and an auxiliary nonconvex optimization algorithm, and hence the title of this paper.<\/jats:p>","DOI":"10.1214\/21-aos2066","type":"journal-article","created":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T11:02:12Z","timestamp":1636714932000},"page":"2948-2971","source":"Crossref","is-referenced-by-count":43,"title":["Bridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data"],"prefix":"10.1214","volume":"49","author":[{"given":"Yuxin","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianqing","family":"Fan","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Financial Engineering, Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cong","family":"Ma","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuling","family":"Yan","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Financial Engineering, Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"47","doi-asserted-by":"publisher","unstructured":"<small>Jain, P.<\/small>, <small>Netrapalli, P.<\/small> and <small>Sanghavi, S.<\/small> (2013). Low-rank matrix completion using alternating minimization (extended abstract). In <i>STOC\u2019<\/i>13<i>\u2014Proceedings of the<\/i> 2013 <i>ACM Symposium on Theory of Computing<\/i> 665\u2013674. ACM, New York.","DOI":"10.1145\/2488608.2488693"},{"key":"1","doi-asserted-by":"publisher","unstructured":"<small>Agarwal, A.<\/small>, <small>Negahban, S.<\/small> and <small>Wainwright, M. J.<\/small> (2012). Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions. <i>Ann. Statist.<\/i> <b>40<\/b> 1171\u20131197.","DOI":"10.1214\/12-AOS1000"},{"key":"2","doi-asserted-by":"publisher","unstructured":"<small>Ahmed, A.<\/small>, <small>Recht, B.<\/small> and <small>Romberg, J.<\/small> (2014). Blind deconvolution using convex programming. <i>IEEE Trans. Inf. Theory<\/i> <b>60<\/b> 1711\u20131732.","DOI":"10.1109\/TIT.2013.2294644"},{"key":"3","unstructured":"<small>Cai, H.<\/small>, <small>Cai, J.-F.<\/small> and <small>Wei, K.<\/small> (2019). Accelerated alternating projections for robust principal component analysis. <i>J. Mach. Learn. Res.<\/i> <b>20<\/b> Paper No. 20, 33."},{"key":"5","unstructured":"<small>Cai, J.-F.<\/small> and <small>Wei, K.<\/small> (2018). Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity. Preprint. <a href=\"https:\/\/arxiv.org\/abs\/arXiv:1809.02773\">arXiv:1809.02773<\/a>."},{"key":"6","doi-asserted-by":"publisher","unstructured":"<small>Cand\u00e8s, E. J.<\/small>, <small>Li, X.<\/small> and <small>Soltanolkotabi, M.<\/small> (2015). Phase retrieval via Wirtinger flow: Theory and algorithms. <i>IEEE Trans. Inf. Theory<\/i> <b>61<\/b> 1985\u20132007.","DOI":"10.1109\/TIT.2015.2399924"},{"key":"7","doi-asserted-by":"crossref","unstructured":"<small>Cand\u00e8s, E.<\/small> and <small>Plan, Y.<\/small> (2010). Matrix completion with noise. <i>Proc. IEEE<\/i> <b>98<\/b> 925\u2013936.","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"11","doi-asserted-by":"publisher","unstructured":"<small>Chandrasekaran, V.<\/small>, <small>Parrilo, P. A.<\/small> and <small>Willsky, A. S.<\/small> (2012). Latent variable graphical model selection via convex optimization. <i>Ann. Statist.<\/i> <b>40<\/b> 1935\u20131967.","DOI":"10.1214\/11-AOS949"},{"key":"12","doi-asserted-by":"publisher","unstructured":"<small>Chandrasekaran, V.<\/small>, <small>Sanghavi, S.<\/small>, <small>Parrilo, P. A.<\/small> and <small>Willsky, A. S.<\/small> (2011). Rank-sparsity incoherence for matrix decomposition. <i>SIAM J. Optim.<\/i> <b>21<\/b> 572\u2013596.","DOI":"10.1137\/090761793"},{"key":"13","unstructured":"<small>Charisopoulos, V.<\/small>, <small>Davis, D.<\/small>, <small>D\u00edaz, M.<\/small> and <small>Drusvyatskiy, D.<\/small> (2019). Composite optimization for robust blind deconvolution. Preprint. <a href=\"https:\/\/arxiv.org\/abs\/arXiv::1901.01624\">arXiv::1901.01624<\/a>."},{"key":"14","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small> (2015). Incoherence-optimal matrix completion. <i>IEEE Trans. Inf. Theory<\/i> <b>61<\/b> 2909\u20132923.","DOI":"10.1109\/TIT.2015.2415195"},{"key":"15","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small> and <small>Cand\u00e8s, E. J.<\/small> (2017). Solving random quadratic systems of equations is nearly as easy as solving linear systems. <i>Comm. Pure Appl. Math.<\/i> <b>70<\/b> 822\u2013883.","DOI":"10.1002\/cpa.21638"},{"key":"17","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small> and <small>Chi, Y.<\/small> (2014). Robust spectral compressed sensing via structured matrix completion. <i>IEEE Trans. Inf. Theory<\/i> <b>60<\/b> 6576\u20136601.","DOI":"10.1109\/TIT.2014.2343623"},{"key":"18","unstructured":"<small>Chen, Y.<\/small>, <small>Guibas, L. J.<\/small> and <small>Huang, Q.<\/small> (2014). Near-optimal joint optimal matching via convex relaxation. In <i>International Conference on Machine Learning<\/i> (<i>ICML<\/i>) 100\u2013108."},{"key":"19","doi-asserted-by":"publisher","unstructured":"<small>Chen, J.<\/small>, <small>Liu, D.<\/small> and <small>Li, X.<\/small> (2020). Nonconvex rectangular matrix completion via gradient descent without <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\" alttext=\"${\\ell _{2,\\infty }}$\"><msub><mrow><mi>\u2113<\/mi><\/mrow><mrow><mn>2<\/mn><mo>,<\/mo><mi>\u221e<\/mi><\/mrow><\/msub><\/math> regularization. <i>IEEE Trans. Inform. Theory<\/i> <b>66<\/b> 5806\u20135841.","DOI":"10.1109\/TIT.2020.2992234"},{"key":"20","unstructured":"<small>Chen, Y.<\/small> and <small>Wainwright, M. J.<\/small> (2015). Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. <a href=\"https:\/\/arxiv.org\/abs\/arXiv:1509.03025\">arXiv:1509.03025<\/a>."},{"key":"21","doi-asserted-by":"crossref","unstructured":"<small>Chen, Y.<\/small>, <small>Jalali, A.<\/small>, <small>Sanghavi, S.<\/small> and <small>Caramanis, C.<\/small> (2013). Low-rank matrix recovery from errors and erasures. <i>IEEE Transactions on Information Theory<\/i> <b>59<\/b> 4324\u20134337.","DOI":"10.1109\/TIT.2013.2249572"},{"key":"22","unstructured":"<small>Chen, Y.<\/small>, <small>Jalali, A.<\/small>, <small>Sanghavi, S.<\/small> and <small>Xu, H.<\/small> (2014). Clustering partially observed graphs via convex optimization. <i>J. Mach. Learn. Res.<\/i> <b>15<\/b> 2213\u20132238."},{"key":"24","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small>, <small>Fan, J.<\/small>, <small>Ma, C.<\/small> and <small>Yan, Y.<\/small> (2019b). Inference and uncertainty quantification for noisy matrix completion. <i>Proc. Natl. Acad. Sci. USA<\/i> <b>116<\/b> 22931\u201322937.","DOI":"10.1073\/pnas.1910053116"},{"key":"25","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small>, <small>Chi, Y.<\/small>, <small>Fan, J.<\/small>, <small>Ma, C.<\/small> and <small>Yan, Y.<\/small> (2020a). Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. <i>SIAM J. Optim.<\/i> <b>30<\/b> 3098\u20133121.","DOI":"10.1137\/19M1290000"},{"key":"26","unstructured":"<small>Chen, Y.<\/small>, <small>Chi, Y.<\/small>, <small>Fan, J.<\/small> and <small>Ma, C.<\/small> (2020b). Spectral methods for data science: A statistical perspective. Preprint. <a href=\"https:\/\/arxiv.org\/abs\/arXiv::2012.08496\">arXiv::2012.08496<\/a>."},{"key":"27","unstructured":"<small>Chen, Y.<\/small>, <small>Fan, J.<\/small>, <small>Wang, B.<\/small> and <small>Yan, Y.<\/small> (2020c). Convex and nonconvex optimization are both minimax-optimal for noisy blind deconvolution. Preprint. <a href=\"https:\/\/arxiv.org\/abs\/arXiv::2008.01724\">arXiv::2008.01724<\/a>."},{"key":"28","doi-asserted-by":"crossref","unstructured":"<small>Chen, Y.<\/small>, <small>Fan, J.<\/small>, <small>Ma, C.<\/small> and <small>Yan, Y.<\/small> (2021). Supplement to \u201cBridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data.\u201d <a href=\"https:\/\/doi.org\/10.1214\/21-AOS2066SUPP\">https:\/\/doi.org\/10.1214\/21-AOS2066SUPP<\/a>","DOI":"10.1214\/21-AOS2066SUPP"},{"key":"29","unstructured":"<small>Cherapanamjeri, Y.<\/small>, <small>Gupta, K.<\/small> and <small>Jain, P.<\/small> (2017). Nearly optimal robust matrix completion. In <i>Proceedings of the<\/i> 34<i>th International Conference on Machine Learning<\/i> <b>70<\/b> 797\u2013805. JMLR.org."},{"key":"31","doi-asserted-by":"crossref","unstructured":"<small>Davenport, M. A.<\/small> and <small>Romberg, J.<\/small> (2016). An overview of low-rank matrix recovery from incomplete observations. <i>IEEE Journal of Selected Topics in Signal Processing<\/i> <b>10<\/b> 608\u2013622.","DOI":"10.1109\/JSTSP.2016.2539100"},{"key":"32","doi-asserted-by":"publisher","unstructured":"<small>Donoho, D.<\/small> and <small>Gavish, M.<\/small> (2014). Minimax risk of matrix denoising by singular value thresholding. <i>Ann. Statist.<\/i> <b>42<\/b> 2413\u20132440.","DOI":"10.1214\/14-AOS1257"},{"key":"33","doi-asserted-by":"publisher","unstructured":"<small>Drusvyatskiy, D.<\/small>, <small>Ioffe, A. D.<\/small> and <small>Lewis, A. S.<\/small> (2021). Nonsmooth optimization using Taylor-like models: Error bounds, convergence, and termination criteria. <i>Math. Program.<\/i> <b>185<\/b> 357\u2013383.","DOI":"10.1007\/s10107-019-01432-w"},{"key":"37","doi-asserted-by":"publisher","unstructured":"<small>Fan, J.<\/small>, <small>Wang, W.<\/small> and <small>Zhong, Y.<\/small> (2019). Robust covariance estimation for approximate factor models. <i>J. Econometrics<\/i> <b>208<\/b> 5\u201322.","DOI":"10.1016\/j.jeconom.2018.09.003"},{"key":"38","unstructured":"<small>Fan, J.<\/small>, <small>Sun, Q.<\/small>, <small>Zhou, W.-X.<\/small> and <small>Zhu, Z.<\/small> (2018). Principal component analysis for big data. Preprint. <a href=\"https:\/\/arxiv.org\/abs\/arXiv::1801.01602\">arXiv::1801.01602<\/a>."},{"key":"39","unstructured":"<small>Feng, J.<\/small>, <small>Xu, H.<\/small> and <small>Yan, S.<\/small> (2013). Online robust PCA via stochastic optimization. In <i>Advances in Neural Information Processing Systems<\/i> 404\u2013412."},{"key":"40","doi-asserted-by":"crossref","unstructured":"<small>Ganesh, A.<\/small>, <small>Wright, J.<\/small>, <small>Li, X.<\/small>, <small>Candes, E. J.<\/small> and <small>Ma, Y.<\/small> (2010). Dense error correction for low-rank matrices via principal component pursuit. In 2010 <i>IEEE International Symposium on Information Theory<\/i> 1513\u20131517. IEEE.","DOI":"10.1109\/ISIT.2010.5513538"},{"key":"41","doi-asserted-by":"publisher","unstructured":"<small>Goldfarb, D.<\/small>, <small>Ma, S.<\/small> and <small>Scheinberg, K.<\/small> (2013). Fast alternating linearization methods for minimizing the sum of two convex functions. <i>Math. Program.<\/i> <b>141<\/b> 349\u2013382.","DOI":"10.1007\/s10107-012-0530-2"},{"key":"42","doi-asserted-by":"publisher","unstructured":"<small>Gross, D.<\/small> (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":"43","unstructured":"<small>Gu, Q.<\/small>, <small>Wang, Z. W.<\/small> and <small>Liu, H.<\/small> (2016). Low-rank and sparse structure pursuit via alternating minimization. In <i>Artificial Intelligence and Statistics<\/i> 600\u2013609."},{"key":"44","doi-asserted-by":"publisher","unstructured":"<small>Guo, H.<\/small>, <small>Qiu, C.<\/small> and <small>Vaswani, N.<\/small> (2014). An online algorithm for separating sparse and low-dimensional signal sequences from their sum. <i>IEEE Trans. Signal Process.<\/i> <b>62<\/b> 4284\u20134297.","DOI":"10.1109\/TSP.2014.2331612"},{"key":"45","doi-asserted-by":"publisher","unstructured":"<small>Hsu, D.<\/small>, <small>Kakade, S. M.<\/small> and <small>Zhang, T.<\/small> (2011). Robust matrix decomposition with sparse corruptions. <i>IEEE Trans. Inform. Theory<\/i> <b>57<\/b> 7221\u20137234.","DOI":"10.1109\/TIT.2011.2158250"},{"key":"46","doi-asserted-by":"crossref","unstructured":"<small>Huang, Q.<\/small> and <small>Guibas, L.<\/small> (2013). Consistent shape maps via semidefinite programming. <i>Computer Graphics Forum<\/i> <b>32<\/b> 177\u2013186.","DOI":"10.1111\/cgf.12184"},{"key":"49","doi-asserted-by":"publisher","unstructured":"<small>Keshavan, R. H.<\/small>, <small>Montanari, A.<\/small> and <small>Oh, S.<\/small> (2010). Matrix completion from a few entries. <i>IEEE Trans. Inform. Theory<\/i> <b>56<\/b> 2980\u20132998.","DOI":"10.1109\/TIT.2010.2046205"},{"key":"50","doi-asserted-by":"publisher","unstructured":"<small>Klopp, O.<\/small> (2014). Noisy low-rank matrix completion with general sampling distribution. <i>Bernoulli<\/i> <b>20<\/b> 282\u2013303.","DOI":"10.3150\/12-BEJ486"},{"key":"51","doi-asserted-by":"publisher","unstructured":"<small>Klopp, O.<\/small>, <small>Lounici, K.<\/small> and <small>Tsybakov, A. B.<\/small> (2017). Robust matrix completion. <i>Probab. Theory Related Fields<\/i> <b>169<\/b> 523\u2013564.","DOI":"10.1007\/s00440-016-0736-y"},{"key":"53","doi-asserted-by":"crossref","unstructured":"<small>Krahmer, F.<\/small> and <small>St\u00f6ger, D.<\/small> (2021). On the convex geometry of blind deconvolution and matrix completion. <i>Comm. Pure Appl. Math.<\/i> <b>74<\/b> 790\u2013832.","DOI":"10.1002\/cpa.21957"},{"key":"54","doi-asserted-by":"publisher","unstructured":"<small>Li, X.<\/small> (2013). Compressed sensing and matrix completion with constant proportion of corruptions. <i>Constr. Approx.<\/i> <b>37<\/b> 73\u201399.","DOI":"10.1007\/s00365-012-9176-9"},{"key":"55","unstructured":"<small>Li, Y.<\/small>, <small>Ma, C.<\/small>, <small>Chen, Y.<\/small> and <small>Chi, Y.<\/small> (2019). Nonconvex matrix factorization from rank-one measurements. In <i>The<\/i> 22<i>nd International Conference on Artificial Intelligence and Statistics<\/i> 1496\u20131505."},{"key":"56","doi-asserted-by":"crossref","unstructured":"<small>Ma, S.<\/small> and <small>Aybat, N. S.<\/small> (2018). Efficient optimization algorithms for robust principal component analysis and its variants. <i>Proceedings of the IEEE<\/i> <b>106<\/b> 1411\u20131426.","DOI":"10.1109\/JPROC.2018.2846606"},{"key":"58","unstructured":"<small>Mazumder, R.<\/small>, <small>Hastie, T.<\/small> and <small>Tibshirani, R.<\/small> (2010). Spectral regularization algorithms for learning large incomplete matrices. <i>J. Mach. Learn. Res.<\/i> <b>11<\/b> 2287\u20132322."},{"key":"60","doi-asserted-by":"publisher","unstructured":"<small>Netrapalli, P.<\/small>, <small>Jain, P.<\/small> and <small>Sanghavi, S.<\/small> (2015). Phase retrieval using alternating minimization. <i>IEEE Trans. Signal Process.<\/i> <b>63<\/b> 4814\u20134826.","DOI":"10.1109\/TSP.2015.2448516"},{"key":"61","unstructured":"<small>Netrapalli, P.<\/small>, <small>Niranjan, U.<\/small>, <small>Sanghavi, S.<\/small>, <small>Anandkumar, A.<\/small> and <small>Jain, P.<\/small> (2014). Non-convex robust PCA. In <i>Advances in Neural Information Processing Systems<\/i> 1107\u20131115."},{"key":"62","doi-asserted-by":"crossref","unstructured":"<small>Pearson, K.<\/small> (1901). LIII. On lines and planes of closest fit to systems of points in space. <i>The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science<\/i> <b>2<\/b> 559\u2013572.","DOI":"10.1080\/14786440109462720"},{"key":"63","doi-asserted-by":"crossref","unstructured":"<small>Qiu, C.<\/small> and <small>Vaswani, N.<\/small> (2010). Real-time robust principal components\u2019 pursuit. In 2010 48<i>th Annual Allerton Conference on Communication, Control, and Computing<\/i> (<i>Allerton<\/i>) 591\u2013598. IEEE.","DOI":"10.1109\/ALLERTON.2010.5706961"},{"key":"64","doi-asserted-by":"publisher","unstructured":"<small>Qiu, C.<\/small>, <small>Vaswani, N.<\/small>, <small>Lois, B.<\/small> and <small>Hogben, L.<\/small> (2014). Recursive robust PCA or recursive sparse recovery in large but structured noise. <i>IEEE Trans. Inform. Theory<\/i> <b>60<\/b> 5007\u20135039.","DOI":"10.1109\/TIT.2014.2331344"},{"key":"65","doi-asserted-by":"publisher","unstructured":"<small>Shen, Y.<\/small>, <small>Wen, Z.<\/small> and <small>Zhang, Y.<\/small> (2014). Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. <i>Optim. Methods Softw.<\/i> <b>29<\/b> 239\u2013263.","DOI":"10.1080\/10556788.2012.700713"},{"key":"67","doi-asserted-by":"publisher","unstructured":"<small>Srebro, N.<\/small> and <small>Shraibman, A.<\/small> (2005). Rank, trace-norm and max-norm. In <i>Learning Theory<\/i>. <i>Lecture Notes in Computer Science<\/i> <b>3559<\/b> 545\u2013560. Springer, Berlin.","DOI":"10.1007\/11503415_37"},{"key":"68","doi-asserted-by":"publisher","unstructured":"<small>Sun, R.<\/small> and <small>Luo, Z.-Q.<\/small> (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":"69","doi-asserted-by":"publisher","unstructured":"<small>Tao, M.<\/small> and <small>Yuan, X.<\/small> (2011). Recovering low-rank and sparse components of matrices from incomplete and noisy observations. <i>SIAM J. Optim.<\/i> <b>21<\/b> 57\u201381.","DOI":"10.1137\/100781894"},{"key":"70","doi-asserted-by":"crossref","unstructured":"<small>Vaswani, N.<\/small> and <small>Narayanamurthy, P.<\/small> (2018). Static and dynamic robust PCA and matrix completion: A review. <i>Proceedings of the IEEE<\/i> <b>106<\/b> 1359\u20131379.","DOI":"10.1109\/JPROC.2018.2844126"},{"key":"72","doi-asserted-by":"publisher","unstructured":"<small>Wang, G.<\/small>, <small>Giannakis, G. B.<\/small> and <small>Eldar, Y. C.<\/small> (2018). Solving systems of random quadratic equations via truncated amplitude flow. <i>IEEE Trans. Inform. Theory<\/i> <b>64<\/b> 773\u2013794.","DOI":"10.1109\/TIT.2017.2756858"},{"key":"73","doi-asserted-by":"publisher","unstructured":"<small>Wei, K.<\/small>, <small>Cai, J.-F.<\/small>, <small>Chan, T. F.<\/small> and <small>Leung, S.<\/small> (2016). Guarantees of Riemannian optimization for low rank matrix recovery. <i>SIAM J. Matrix Anal. Appl.<\/i> <b>37<\/b> 1198\u20131222.","DOI":"10.1137\/15M1050525"},{"key":"74","unstructured":"<small>Wong, R. K. W.<\/small> and <small>Lee, T. C. M.<\/small> (2017). Matrix completion with noisy entries and outliers. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> Paper No. 147, 25."},{"key":"75","unstructured":"<small>Yi, X.<\/small>, <small>Park, D.<\/small>, <small>Chen, Y.<\/small> and <small>Caramanis, C.<\/small> (2016). Fast algorithms for robust PCA via gradient descent. In <i>NIPS<\/i> 4152\u20134160."},{"key":"76","unstructured":"<small>Zhan, J.<\/small>, <small>Lois, B.<\/small>, <small>Guo, H.<\/small> and <small>Vaswani, N.<\/small> (2016). Online (and offline) robust PCA: Novel algorithms and performance guarantees. In <i>Artificial Intelligence and Statistics<\/i> 1488\u20131496."},{"key":"77","unstructured":"<small>Zhang, H.<\/small>, <small>Chi, Y.<\/small> and <small>Liang, Y.<\/small> (2016). Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow. In <i>International Conference on Machine Learning<\/i> 1022\u20131031."},{"key":"78","unstructured":"<small>Zhang, X.<\/small>, <small>Wang, L. W.<\/small> and <small>Gu, Q.<\/small> (2018). A unified framework for nonconvex low-rank plus sparse matrix recovery. In <i>International Conference on Artificial Intelligence and Statistics<\/i>."},{"key":"79","unstructured":"<small>Zheng, Q.<\/small> and <small>Lafferty, J.<\/small> (2016). Convergence analysis for rectangular matrix completion using Burer\u2013Monteiro factorization and gradient descent. <a href=\"https:\/\/arxiv.org\/abs\/arXiv:1605.07051\">arXiv:1605.07051<\/a>."},{"key":"80","unstructured":"<small>Zhou, Z.<\/small>, <small>Li, X.<\/small>, <small>Wright, J.<\/small>, <small>Cand\u00e8s, E.<\/small> and <small>Ma, Y.<\/small> (2010). Stable principal component pursuit. In <i>International Symposium on Information Theory<\/i> 1518\u20131522."},{"key":"9","doi-asserted-by":"publisher","unstructured":"<small>Cand\u00e8s, E. J.<\/small> and <small>Tao, T.<\/small> (2010). The power of convex relaxation: Near-optimal matrix completion. <i>IEEE Trans. Inf. Theory<\/i> <b>56<\/b> 2053\u20132080.","DOI":"10.1109\/TIT.2010.2044061"},{"key":"23","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small>, <small>Chi, Y.<\/small>, <small>Fan, J.<\/small> and <small>Ma, C.<\/small> (2019a). Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. <i>Math. Program.<\/i> <b>176<\/b> 5\u201337.","DOI":"10.1007\/s10107-019-01363-6"},{"key":"8","doi-asserted-by":"publisher","unstructured":"<small>Cand\u00e8s, E. J.<\/small> and <small>Recht, B.<\/small> (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":"<small>Cand\u00e8s, E. J.<\/small>, <small>Li, X.<\/small>, <small>Ma, Y.<\/small> and <small>Wright, J.<\/small> (2011). Robust principal component analysis? <i>J. ACM<\/i> <b>58<\/b> Art. 11, 37.","DOI":"10.1145\/1970392.1970395"},{"key":"34","doi-asserted-by":"publisher","unstructured":"<small>Fan, J.<\/small>, <small>Fan, Y.<\/small> and <small>Lv, J.<\/small> (2008). High dimensional covariance matrix estimation using a factor model. <i>J. Econometrics<\/i> <b>147<\/b> 186\u2013197.","DOI":"10.1016\/j.jeconom.2008.09.017"},{"key":"35","doi-asserted-by":"publisher","unstructured":"<small>Fan, J.<\/small>, <small>Liao, Y.<\/small> and <small>Mincheva, M.<\/small> (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":"36","unstructured":"<small>Fan, J.<\/small>, <small>Wang, W.<\/small> and <small>Zhong, Y.<\/small> (2017). An <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" overflow=\"scroll\" alttext=\"${\\ell _{\\infty }}$\"><msub><mrow><mi>\u2113<\/mi><\/mrow><mrow><mi>\u221e<\/mi><\/mrow><\/msub><\/math> eigenvector perturbation bound and its application to robust covariance estimation. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> Paper No. 207, 42."},{"key":"48","doi-asserted-by":"publisher","unstructured":"<small>Jolliffe, I. T.<\/small> (1986). <i>Principal Component Analysis<\/i>. <i>Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4757-1904-8"},{"key":"4","doi-asserted-by":"publisher","unstructured":"<small>Cai, T. T.<\/small>, <small>Ma, Z.<\/small> and <small>Wu, Y.<\/small> (2013). Sparse PCA: Optimal rates and adaptive estimation. <i>Ann. Statist.<\/i> <b>41<\/b> 3074\u20133110.","DOI":"10.1214\/13-AOS1178"},{"key":"16","doi-asserted-by":"publisher","unstructured":"<small>Chen, Y.<\/small> and <small>Cand\u00e8s, E. J.<\/small> (2018). The projected power method: An efficient algorithm for joint alignment from pairwise differences. <i>Comm. Pure Appl. Math.<\/i> <b>71<\/b> 1648\u20131714.","DOI":"10.1002\/cpa.21760"},{"key":"30","doi-asserted-by":"publisher","unstructured":"<small>Chi, Y.<\/small>, <small>Lu, Y. M.<\/small> and <small>Chen, Y.<\/small> (2019). Nonconvex optimization meets low-rank matrix factorization: An overview. <i>IEEE Trans. Signal Process.<\/i> <b>67<\/b> 5239\u20135269.","DOI":"10.1109\/TSP.2019.2937282"},{"key":"57","doi-asserted-by":"publisher","unstructured":"<small>Ma, C.<\/small>, <small>Wang, K.<\/small>, <small>Chi, Y.<\/small> and <small>Chen, Y.<\/small> (2020). Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. <i>Found. Comput. Math.<\/i> <b>20<\/b> 451\u2013632.","DOI":"10.1007\/s10208-019-09429-9"},{"key":"66","doi-asserted-by":"publisher","unstructured":"<small>Singer, A.<\/small> (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":"71","doi-asserted-by":"crossref","unstructured":"<small>Vershynin, R.<\/small> (2012). Introduction to the non-asymptotic analysis of random matrices. In <i>Compressed Sensing<\/i> 210\u2013268. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/CBO9780511794308.006"},{"key":"52","doi-asserted-by":"publisher","unstructured":"<small>Koltchinskii, V.<\/small>, <small>Lounici, K.<\/small> and <small>Tsybakov, A. B.<\/small> (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":"59","unstructured":"<small>Negahban, S.<\/small> and <small>Wainwright, M. J.<\/small> (2012). Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. <i>J. Mach. Learn. Res.<\/i> <b>13<\/b> 1665\u20131697."}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T20:13:43Z","timestamp":1791404023000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-49\/issue-5\/Bridging-convex-and-nonconvex-optimization-in-robust-PCA--Noise\/10.1214\/21-AOS2066.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,1]]},"references-count":80,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,10,1]]}},"URL":"https:\/\/doi.org\/10.1214\/21-aos2066","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,1]]}}}