{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T12:40:49Z","timestamp":1790253649008,"version":"4.1.0"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1704458"],"award-info":[{"award-number":["1704458"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["CUHK 14210617"],"award-info":[{"award-number":["CUHK 14210617"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["CUHK 14208117"],"award-info":[{"award-number":["CUHK 14208117"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>In this paper, we study the problem of recovering a low-rank matrix from a number of random linear measurements that are corrupted by outliers taking arbitrary values. We consider a nonsmooth nonconvex formulation of the problem, in which we explicitly enforce the low-rank property of the solution by using a factored representation of the matrix variable and employ an $\\ell_1$-loss function to robustify the solution against outliers. We show that even when a constant fraction (which can be up to almost half) of the measurements are arbitrarily corrupted, as long as certain measurement operators arising from the measurement model satisfy the so-called $\\ell_1\/\\ell_2$-restricted isometry property, the ground-truth matrix can be exactly recovered from any global minimum of the resulting optimization problem. Furthermore, we show that the objective function of the optimization problem is sharp and weakly convex. Consequently, a subgradient method (SubGM) with geometrically diminishing step sizes will converge linearly to the ground-truth matrix when suitably initialized. We demonstrate the efficacy of the SubGM for the nonconvex robust low-rank matrix recovery problem with various numerical experiments.<\/jats:p>","DOI":"10.1137\/18m1224738","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T15:17:48Z","timestamp":1582643868000},"page":"660-686","source":"Crossref","is-referenced-by-count":57,"title":["Nonconvex Robust Low-Rank Matrix Recovery"],"prefix":"10.1137","volume":"30","author":[{"given":"Xiao","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihui","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony","family":"Man-Cho So","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ren\u00e9","family":"Vidal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"atypb2","unstructured":"Y. Bai, Q. Jiang, and J. Sun,\n                      Subgradient descent learns orthogonal dictionaries\n                      , in Proceedings of the International Conference on Learning Representations (ICLR), 2019."},{"key":"atypb3","first-page":"85","author":"Bertsekas D. P.","year":"2012","journal-title":"MA"},{"key":"atypb4","first-page":"3873","author":"Bhojanapalli S.","year":"2016","journal-title":"MA"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0564-1"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0331063"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2111771"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2429594"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2019.2937282"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2016.2539100"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-018-1372-8"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"D. Davis, D. Drusvyatskiy, and C. Paquette,\n                      The nonsmooth landscape of phase retrieval\n                      , IMA J. Numer. Anal. (2020),https:\/\/doi.org\/10.1093\/imanum\/drz031.","DOI":"10.1093\/imanum\/drz031"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023709501986"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iay015"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. Fazel, H. Hindi, and S. Boyd,\n                      Rank minimization and applications in system theory\n                      , in Proceedings of the 2004 IEEE American Control Conference, Vol. 4, 2004, pp. 3273-3278.","DOI":"10.23919\/ACC.2004.1384521"},{"key":"atypb19","first-page":"2973","author":"Ge R.","year":"2016","journal-title":"MA"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584346"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104999"},{"key":"atypb22","unstructured":"Q. Gu, Z. W. Wang, and H. Liu,\n                      Low-rank and sparse structure pursuit via alternating minimization\n                      , in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016), 2016, pp. 600-609."},{"key":"atypb23","unstructured":"B. Haeffele, E. Young, and R. Vidal,\n                      Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing\n                      , in Proceedings of the 31st International Conference on Machine Learning (ICML 2014), 2014, pp. 2007-2015."},{"key":"atypb24","unstructured":"C. Josz, Y. Ouyang, R. Zhang, J. Lavaei, and S. Sojoudi,\n                      A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization\n                      , in Advances in Neural Information Processing Systems, Vol. 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., MIT Press, Cambridge, MA, 2018, pp. 2441-2449."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Q. Ke and T. Kanade,\n                      Robust $L_1$ norm factorization in the presence of outliers and missing data by alternative convex programming\n                      , in Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), Vol. 1, 2005, pp. 739-746.","DOI":"10.1109\/CVPR.2005.309"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2004.836169"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iay003"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2898663"},{"key":"atypb29","unstructured":"X. Li, Z. Zhu, A. M.C. So, and R. Vidal,\n                      Nonconvex Robust Low-Rank Matrix Recovery\n                      , companion technical report of this paper; available online fromhttps:\/\/arxiv.org\/abs\/1809.09237, 2018."},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"Y. Li, Y. Chi, H. Zhang, and Y. Liang,\n                      Nonconvex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent\n                      , Inf. Inference, (2019),https:\/\/doi.org\/10.1093\/imaiai\/iaz009.","DOI":"10.1093\/imaiai\/iaz009"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2016.2620109"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"A. Nedi\u0107 and D. Bertsekas,\n                      Convergence rate of incremental subgradient algorithms\n                      , in Stochastic Optimization: Algorithms and Applications, Appl. Optim. 54, S. Uryasev and P. M. Pardalos, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001.","DOI":"10.1007\/978-1-4757-6594-6_11"},{"key":"atypb33","first-page":"1107","author":"Netrapalli P.","year":"2014","journal-title":"MA"},{"key":"atypb34","unstructured":"J. Nocedal and S. Wright,\n                      Numerical Optimization\n                      , Springer, New York, 2006."},{"key":"atypb35","unstructured":"D. Park, A. Kyrillidis, C. Caramanis, and S. Sanghavi,\n                      Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach\n                      , in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS 2017), 2017, pp. 65-74."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(69)90061-5"},{"key":"atypb37","unstructured":"R. T. Rockafellar and R. J.B. Wets,\n                      Variational Analysis\n                      , 2nd ed., Grundlehren Math. Wiss. 317, Springer-Verlag, Berlin, Heidelberg, 2004."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"N. Z. Shor,\n                      Minimization Methods for Non-differentiable Functions\n                      , Springer Ser. Comput. Math. 3, Springer-Verlag, Berlin, Heidelberg, 1985.","DOI":"10.1007\/978-3-642-82118-9"},{"key":"atypb39","first-page":"56","volume":"4","author":"Shor N. Z.","year":"1968","journal-title":"Kibernetika"},{"key":"atypb40","first-page":"1329","author":"Srebro N.","year":"2004","journal-title":"MA"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2598574"},{"key":"atypb42","unstructured":"S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht,\n                      Low-rank solutions of linear matrix equations via Procrustes flow\n                      , in Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), 2016, pp. 964-973."},{"key":"atypb43","first-page":"210","author":"Vershynin R.","year":"2012","journal-title":"New York"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.2.231"},{"key":"atypb45","first-page":"4152","author":"Yi X.","year":"2016","journal-title":"MA"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2015.06.006"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/18M1167498"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2250577"},{"key":"atypb49","unstructured":"X. Zhang, L. Wang, and Q. Gu,\n                      A unified framework for nonconvex low-rank plus sparse matrix recovery\n                      , in Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018), 2018, pp. 1097-1107."},{"key":"atypb50","unstructured":"Q. Zheng and J. Lafferty,\n                      A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements\n                      , in Advances in Neural Information Processing Systems, Vol. 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, eds., MIT Press, Cambridge, MA, 2015, pp. 109-117."},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"Z. Zhu, Q. Li, G. Tang, and M. B. Wakin,\n                      The Global Optimization Geometry of Low-Rank Matrix Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1703.01256, 2017.","DOI":"10.1109\/GlobalSIP.2017.8309166"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2835403"},{"key":"atypb53","doi-asserted-by":"crossref","unstructured":"Z. Zhu, A. M.C. So, and Y. Ye,\n                      Fast and near-optimal matrix completion via randomized basis pursuit\n                      , in Fifth International Congress of Chinese Mathematicians, L. Ji, Y. S. Poon, L. Yang, and S.T. Yau, eds., AMS\/IP Stud. Adv. Math. 51, Part 2, American Mathematical Society\/International Press, Providence, RI, 2012, pp. 859-882.","DOI":"10.1090\/amsip\/051.2\/22"},{"key":"atypb54","first-page":"2171","author":"Zhu Z.","year":"2018","journal-title":"MA"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1224738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:58:08Z","timestamp":1787338688000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1224738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1224738"],"URL":"https:\/\/doi.org\/10.1137\/18m1224738","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}