{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T18:58:47Z","timestamp":1776884327271,"version":"3.51.2"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s10208-020-09490-9","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T18:03:27Z","timestamp":1611857007000},"page":"1505-1593","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence"],"prefix":"10.1007","volume":"21","author":[{"given":"Vasileios","family":"Charisopoulos","sequence":"first","affiliation":[]},{"given":"Yudong","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Damek","family":"Davis","sequence":"additional","affiliation":[]},{"given":"Mateo","family":"D\u00edaz","sequence":"additional","affiliation":[]},{"given":"Lijun","family":"Ding","sequence":"additional","affiliation":[]},{"given":"Dmitriy","family":"Drusvyatskiy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"issue":"3","key":"9490_CR1","doi-asserted-by":"publisher","first-page":"1711","DOI":"10.1109\/TIT.2013.2294644","volume":"60","author":"A Ahmed","year":"2014","unstructured":"Ahmed, A., Recht, B., Romberg, J.: Blind deconvolution using convex programming. IEEE Transactions on Information Theory 60(3), 1711\u20131732 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9490_CR2","doi-asserted-by":"crossref","unstructured":"Albano, P., Cannarsa, P.: Singularities of semiconcave functions in Banach spaces. In: Stochastic analysis, control, optimization and applications, Systems Control Found. Appl., pp. 171\u2013190. Birkh\u00e4user Boston, Boston, MA (1999)","DOI":"10.1007\/978-1-4612-1784-8_10"},{"issue":"102","key":"9490_CR3","first-page":"1","volume":"20","author":"MF Balcan","year":"2019","unstructured":"Balcan, M.F., Liang, Y., Song, Z., Woodruff, D.P., Zhang, H.: Non-convex matrix completion and related problems via strong duality. Journal of Machine Learning Research 20(102), 1\u201356 (2019)","journal-title":"J. Mach. Learn. Res."},{"key":"9490_CR4","doi-asserted-by":"crossref","unstructured":"Bauch, J., Nadler, B.: Rank $$2r$$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries. arXiv preprint arXiv:2002.01849 (2020)","DOI":"10.1137\/20M1315294"},{"key":"9490_CR5","unstructured":"Bhojanapalli, S., Neyshabur, B., Srebro, N.: Global optimality of local search for low rank matrix recovery. In: Advances in Neural Information Processing Systems, pp. 3873\u20133881 (2016)"},{"key":"9490_CR6","unstructured":"Borwein, J., Lewis, A.: Convex analysis and nonlinear optimization. CMS Books in Mathematics\/Ouvrages de Math\u00e9matiques de la SMC, 3. Springer-Verlag, New York (2000). Theory and examples"},{"key":"9490_CR7","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001","volume-title":"Concentration inequalities: A nonasymptotic theory of independence","author":"S Boucheron","year":"2013","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press (2013)"},{"issue":"3","key":"9490_CR8","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/BF01584377","volume":"33","author":"J Burke","year":"1985","unstructured":"Burke, J.: Descent methods for composite nondifferentiable optimization problems. Math. Programming 33(3), 260\u2013279 (1985). 10.1007\/BF01584377.","journal-title":"Math. Programming"},{"key":"9490_CR9","doi-asserted-by":"publisher","unstructured":"Burke, J., Ferris, M.: A Gauss-Newton method for convex composite optimization. Math. Programming 71(2, Ser. A), 179\u2013194 (1995). https:\/\/doi.org\/10.1007\/BF01585997.","DOI":"10.1007\/BF01585997"},{"issue":"1","key":"9490_CR10","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1214\/14-AOS1267","volume":"43","author":"T Cai","year":"2015","unstructured":"Cai, T., Zhang, A.: ROP: matrix recovery via rank-one projections. Ann. Stat. 43(1), 102\u2013138 (2015). 10.1214\/14-AOS1267.","journal-title":"Ann. Stat."},{"issue":"1","key":"9490_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/110848074","volume":"6","author":"E Cand\u00e8s","year":"2013","unstructured":"Cand\u00e8s, E., Eldar, Y., Strohmer, T., Voroninski, V.: Phase retrieval via matrix completion. SIAM J. Imaging Sci. 6(1), 199\u2013225 (2013). 10.1137\/110848074","journal-title":"SIAM J. Imag. Sci."},{"issue":"4","key":"9490_CR12","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1109\/TIT.2015.2399924","volume":"61","author":"E Cand\u00e8s","year":"2015","unstructured":"Cand\u00e8s, E., Li, X., Soltanolkotabi, M.: Phase retrieval via Wirtinger flow: theory and algorithms. IEEE Trans. Inform. Theory 61(4), 1985\u20132007 (2015). 10.1109\/TIT.2015.2399924","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"4","key":"9490_CR13","doi-asserted-by":"publisher","first-page":"2342","DOI":"10.1109\/TIT.2011.2111771","volume":"57","author":"E Candes","year":"2011","unstructured":"Candes, E., Plan, Y.: Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Transactions on Information Theory 57(4), 2342\u20132359 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"8","key":"9490_CR14","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1002\/cpa.21432","volume":"66","author":"E Candes","year":"2013","unstructured":"Candes, E., Strohmer, T., Voroninski, V.: Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics 66(8), 1241\u20131274 (2013)","journal-title":"Commun. Pure Appl. Math."},{"issue":"3","key":"9490_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1970392.1970395","volume":"58","author":"EJ Cand\u00e8s","year":"2011","unstructured":"Cand\u00e8s, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? Journal of the ACM (JACM) 58(3), 1\u201337 (2011)","journal-title":"J. ACM (JACM)"},{"issue":"6","key":"9490_CR16","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e9s","year":"2009","unstructured":"Cand\u00e9s, E.J., Recht, B.: Exact matrix completion via convex optimization. Foundations of Computational Mathematics 9(6), 717 (2009). 10.1007\/s10208-009-9045-5","journal-title":"Found. Comput. Math."},{"issue":"5","key":"9490_CR17","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"EJ Cand\u00e8s","year":"2010","unstructured":"Cand\u00e8s, E.J., Tao, T.: The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory 56(5), 2053\u20132080 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"9490_CR18","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/090761793","volume":"21","author":"V Chandrasekaran","year":"2011","unstructured":"Chandrasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization 21(2), 572\u2013596 (2011). 10.1137\/090761793","journal-title":"SIAM J. Optim."},{"key":"9490_CR19","unstructured":"Charisopoulos, V., Davis, D., D\u00edaz, M., Drusvyatskiy, D.: Composite optimization for robust blind deconvolution. arXiv:1901.01624 (2019)"},{"issue":"5","key":"9490_CR20","doi-asserted-by":"publisher","first-page":"2909","DOI":"10.1109\/TIT.2015.2415195","volume":"61","author":"Y Chen","year":"2015","unstructured":"Chen, Y.: Incoherence-optimal matrix completion. IEEE Transactions on Information Theory 61(5), 2909\u20132923 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"9490_CR21","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1002\/cpa.21638","volume":"70","author":"Y Chen","year":"2017","unstructured":"Chen, Y., Cand\u00e8s, E.: Solving random quadratic systems of equations is nearly as easy as solving linear systems. Comm. Pure Appl. Math. 70(5), 822\u2013883 (2017)","journal-title":"Comm. Pure Appl. Math."},{"issue":"4","key":"9490_CR22","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/MSP.2018.2821706","volume":"35","author":"Y Chen","year":"2018","unstructured":"Chen, Y., Chi, Y.: Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization. IEEE Signal Processing Magazine 35(4), 14\u201331 (2018)","journal-title":"IEEE Signal Process. Mag."},{"key":"9490_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01363-6","author":"Y Chen","year":"2019","unstructured":"Chen, Y., Chi, Y., Fan, J., Ma, C.: Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval. Mathematical Programming (2019). https:\/\/doi.org\/10.1007\/s10107-019-01363-6","journal-title":"Math. Program."},{"issue":"7","key":"9490_CR24","doi-asserted-by":"publisher","first-page":"4034","DOI":"10.1109\/TIT.2015.2429594","volume":"61","author":"Y Chen","year":"2015","unstructured":"Chen, Y., Chi, Y., Goldsmith, A.: Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Trans. Inform. Theory 61(7), 4034\u20134059 (2015). 10.1109\/TIT.2015.2429594","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9490_CR25","doi-asserted-by":"crossref","unstructured":"Chen, Y., Fan, J., Ma, C., Yan, Y.: Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data. arXiv e-prints arXiv:2001.05484 (2020)","DOI":"10.1214\/21-AOS2066"},{"issue":"7","key":"9490_CR26","doi-asserted-by":"publisher","first-page":"4324","DOI":"10.1109\/TIT.2013.2249572","volume":"59","author":"Y Chen","year":"2013","unstructured":"Chen, Y., Jalali, A., Sanghavi, S., Caramanis, C.: Low-rank matrix recovery from errors and erasures. IEEE Transactions on Information Theory 59(7), 4324\u20134337 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9490_CR27","unstructured":"Chen, Y., Wainwright, M.J.: Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv:1509.03025 (2015)"},{"key":"9490_CR28","doi-asserted-by":"crossref","unstructured":"Chi, Y., Lu, Y., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: An overview. arXiv:1809.09573 (2018)","DOI":"10.1109\/TSP.2019.2937282"},{"issue":"4","key":"9490_CR29","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1109\/JSTSP.2016.2539100","volume":"10","author":"M Davenport","year":"2016","unstructured":"Davenport, M., Romberg, J.: An overview of low-rank matrix recovery from incomplete observations. IEEE J. Selected Top. Signal Process. 10(4), 608\u2013622 (2016). 10.1109\/JSTSP.2016.2539100","journal-title":"IEEE J. Sel. Top. Signal Process."},{"issue":"1","key":"9490_CR30","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/18M1178244","volume":"29","author":"D Davis","year":"2019","unstructured":"Davis, D., Drusvyatskiy, D.: Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization 29(1), 207\u2013239 (2019)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"9490_CR31","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1007\/s10957-018-1372-8","volume":"179","author":"D Davis","year":"2018","unstructured":"Davis, D., Drusvyatskiy, D., MacPhee, K., Paquette, C.: Subgradient methods for sharp weakly convex functions. J. Optim. Theory Appl. 179(3), 962\u2013982 (2018). 10.1007\/s10957-018-1372-8","journal-title":"J. Optim. Theory Appl."},{"key":"9490_CR32","unstructured":"Davis, D., Drusvyatskiy, D., Paquette, C.: The nonsmooth landscape of phase retrieval. To appear in IMA J. Numer. Anal., arXiv:1711.03247 (2017)"},{"key":"9490_CR33","unstructured":"D\u00edaz, M.: The nonsmooth landscape of blind deconvolution. arXiv preprint arXiv:1911.08526 (2019)"},{"key":"9490_CR34","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2992769","author":"L Ding","year":"2020","unstructured":"Ding, L., Chen, Y.: Leave-one-out approach for matrix completion: Primal and dual analysis. IEEE Trans. Inf. Theory (2020). https:\/\/doi.org\/10.1109\/TIT.2020.2992769","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9490_CR35","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1287\/moor.2017.0889","volume":"43","author":"D Drusvyatskiy","year":"2018","unstructured":"Drusvyatskiy, D., Lewis, A.: Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3), 919\u2013948 (2018). 10.1287\/moor.2017.0889","journal-title":"Math. Oper. Res."},{"key":"9490_CR36","doi-asserted-by":"crossref","unstructured":"Drusvyatskiy, D., Paquette, C.: Efficiency of minimizing compositions of convex functions and smooth maps. Math. Prog. pp. 1\u201356 (2018)","DOI":"10.1007\/s10107-018-1311-3"},{"key":"9490_CR37","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iay015","author":"J Duchi","year":"2018","unstructured":"Duchi, J., Ruan, F.: Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval. IMA J. Inf. Inference (2018). https:\/\/doi.org\/10.1093\/imaiai\/iay015","journal-title":"IMA J. Inf. Inference"},{"issue":"4","key":"9490_CR38","doi-asserted-by":"publisher","first-page":"3229","DOI":"10.1137\/17M1135086","volume":"28","author":"J Duchi","year":"2018","unstructured":"Duchi, J., Ruan, F.: Stochastic methods for composite and weakly convex optimization problems. SIAM J. Optim. 28(4), 3229\u20133259 (2018)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"9490_CR39","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.acha.2013.08.003","volume":"36","author":"Y Eldar","year":"2014","unstructured":"Eldar, Y., Mendelson, S.: Phase retrieval: stability and recovery guarantees. Appl. Comput. Harmon. Anal. 36(3), 473\u2013494 (2014). 10.1016\/j.acha.2013.08.003","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9490_CR40","unstructured":"Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Stanford University (2002)"},{"key":"9490_CR41","doi-asserted-by":"publisher","unstructured":"Fletcher, R.: A model algorithm for composite nondifferentiable optimization problems. Math. Programming Stud. (17), 67\u201376 (1982). https:\/\/doi.org\/10.1007\/bfb0120959. Nondifferential and variational techniques in optimization (Lexington, Ky., 1980)","DOI":"10.1007\/bfb0120959"},{"key":"9490_CR42","unstructured":"Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In: D. Precup, Y.W. Teh (eds.) Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 70, pp. 1233\u20131242. PMLR, International Convention Centre, Sydney, Australia (2017)"},{"key":"9490_CR43","unstructured":"Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. In: D.D. Lee, M. Sugiyama, U.V. Luxburg, I. Guyon, R. Garnett (eds.) Advances in Neural Information Processing Systems 29, pp. 2973\u20132981. Curran Associates, Inc. (2016)"},{"issue":"3","key":"9490_CR44","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01584346","volume":"13","author":"J Goffin","year":"1977","unstructured":"Goffin, J.: On convergence rates of subgradient optimization methods. Math. Programming 13(3), 329\u2013347 (1977). 10.1007\/BF01584346","journal-title":"Math. Program."},{"issue":"4","key":"9490_CR45","doi-asserted-by":"publisher","first-page":"2675","DOI":"10.1109\/TIT.2018.2800768","volume":"64","author":"T Goldstein","year":"2018","unstructured":"Goldstein, T., Studer, C.: Phasemax: Convex phase retrieval via basis pursuit. IEEE Transactions on Information Theory 64(4), 2675\u20132689 (2018). 10.1109\/TIT.2018.2800768","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9490_CR46","doi-asserted-by":"publisher","first-page":"1548","DOI":"10.1109\/TIT.2011.2104999","volume":"57","author":"D Gross","year":"2011","unstructured":"Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory 57(3), 1548\u20131566 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9490_CR47","doi-asserted-by":"publisher","unstructured":"Hardt, M.: Understanding alternating minimization for matrix completion. In: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS \u201914, p. 651\u2013660. IEEE Computer Society, USA (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.75","DOI":"10.1109\/FOCS.2014.75"},{"key":"9490_CR48","unstructured":"Hardt, M., Wootters, M.: Fast matrix completion without the condition number. In: M.F. Balcan, V. Feldman, C. Szepesv\u00e1ri (eds.) Proceedings of The 27th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 35, pp. 638\u2013678. PMLR, Barcelona, Spain (2014)"},{"issue":"11","key":"9490_CR49","doi-asserted-by":"publisher","first-page":"7221","DOI":"10.1109\/TIT.2011.2158250","volume":"57","author":"D Hsu","year":"2011","unstructured":"Hsu, D., Kakade, S.M., Zhang, T.: Robust matrix decomposition with sparse corruptions. IEEE Transactions on Information Theory 57(11), 7221\u20137234 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9490_CR50","doi-asserted-by":"publisher","unstructured":"Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC \u201913, p. 665\u2013674. Association for Computing Machinery, New York, NY, USA (2013). https:\/\/doi.org\/10.1145\/2488608.2488693","DOI":"10.1145\/2488608.2488693"},{"key":"9490_CR51","doi-asserted-by":"crossref","unstructured":"Keshavan, R., Montanari, A., Oh, S.: Matrix completion from noisy entries. In: Y. Bengio, D. Schuurmans, J.D. Lafferty, C.K.I. Williams, A. Culotta (eds.) Advances in Neural Information Processing Systems 22, pp. 952\u2013960. Curran Associates, Inc. (2009)","DOI":"10.1109\/ISIT.2009.5205567"},{"issue":"6","key":"9490_CR52","doi-asserted-by":"publisher","first-page":"2980","DOI":"10.1109\/TIT.2010.2046205","volume":"56","author":"RH Keshavan","year":"2010","unstructured":"Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Transactions on Information Theory 56(6), 2980\u20132998 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9490_CR53","doi-asserted-by":"publisher","first-page":"1060","DOI":"10.1214\/009117905000000044","volume":"33","author":"T Klein","year":"2005","unstructured":"Klein, T., Rio, E.: Concentration around the mean for maxima of empirical processes. The Annals of Probability 33(3), 1060\u20131077 (2005)","journal-title":"Ann. Probab."},{"key":"9490_CR54","doi-asserted-by":"publisher","unstructured":"Lewis, A., Wright, S.: A proximal method for composite minimization. Math. Program. 158(1-2, Ser. A), 501\u2013546 (2016). https:\/\/doi.org\/10.1007\/s10107-015-0943-9","DOI":"10.1007\/s10107-015-0943-9"},{"issue":"1","key":"9490_CR55","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00365-012-9176-9","volume":"37","author":"X Li","year":"2013","unstructured":"Li, X.: Compressed sensing and matrix completion with constant proportion of corruptions. Constr. Approximation 37(1), 73\u201399 (2013)","journal-title":"Constr. Approx."},{"key":"9490_CR56","unstructured":"Li, X., Ling, S., Strohmer, T., Wei, K.: Rapid, robust, and reliable blind deconvolution via nonconvex optimization. arXiv:1606.04933 (2016)"},{"key":"9490_CR57","unstructured":"Li, X., Zhu, Z., So, A.C., Vidal, R.: Nonconvex robust low-rank matrix recovery. arXiv:1809.09237 (2018)"},{"key":"9490_CR58","unstructured":"Li, Y., Ma, C., Chen, Y., Chi, Y.: Nonconvex matrix factorization from rank-one measurements. arXiv:1802.06286 (2018)"},{"issue":"2","key":"9490_CR59","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/TSP.2016.2620109","volume":"65","author":"Y Li","year":"2016","unstructured":"Li, Y., Sun, Y., Chi, Y.: Low-rank positive semidefinite matrix recovery from corrupted rank-one measurements. IEEE Transactions on Signal Processing 65(2), 397\u2013408 (2016)","journal-title":"IEEE Trans. Signal Process."},{"key":"9490_CR60","doi-asserted-by":"publisher","unstructured":"Ling, S., Strohmer, T.: Self-calibration and biconvex compressive sensing. Inverse Probl. 31(11), 115002, 31 (2015). https:\/\/doi.org\/10.1088\/0266-5611\/31\/11\/115002","DOI":"10.1088\/0266-5611\/31\/11\/115002"},{"key":"9490_CR61","unstructured":"Ma, C., Wang, K., Chi, Y., Chen, Y.: Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In: J. Dy, A. Krause (eds.) Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 80, pp. 3345\u20133354. PMLR, Stockholmsm\u00e4ssan, Stockholm Sweden (2018)"},{"key":"9490_CR62","doi-asserted-by":"publisher","unstructured":"Mendelson, S.: A remark on the diameter of random sections of convex bodies. In: Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2116, pp. 395\u2013404. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09477-9_25","DOI":"10.1007\/978-3-319-09477-9_25"},{"key":"9490_CR63","doi-asserted-by":"publisher","unstructured":"Mendelson, S.: Learning without concentration. J. ACM 62(3), Art. 21, 25 (2015). https:\/\/doi.org\/10.1145\/2699439","DOI":"10.1145\/2699439"},{"key":"9490_CR64","doi-asserted-by":"crossref","unstructured":"Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I: Basic Theory. Grundlehren der mathematischen Wissenschaften, Vol 330, Springer, Berlin (2006)","DOI":"10.1007\/3-540-31247-1"},{"issue":"4","key":"9490_CR65","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1214\/12-STS400","volume":"27","author":"S Negahban","year":"2012","unstructured":"Negahban, S., Ravikumar, P., Wainwright, M., Yu, B.: A unified framework for high-dimensional analysis of $$M$$-estimators with decomposable regularizers. Statist. Sci. 27(4), 538\u2013557 (2012). 10.1214\/12-STS400","journal-title":"Stat. Sci."},{"key":"9490_CR66","unstructured":"Netrapalli, P., Niranjan, U., Sanghavi, S., Anandkumar, A., Jain, P.: Non-convex robust PCA. In: Advances in Neural Information Processing Systems, pp. 1107\u20131115 (2014)"},{"issue":"1","key":"9490_CR67","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF01068677","volume":"9","author":"E Nurminskii","year":"1973","unstructured":"Nurminskii, E.: The quasigradient method for the solving of the nonlinear programming problems. Cybernetics 9(1), 145\u2013150 (1973). 10.1007\/BF01068677","journal-title":"Cybernetics"},{"issue":"1","key":"9490_CR68","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s12532-013-0061-8","volume":"6","author":"N Parikh","year":"2014","unstructured":"Parikh, N., Boyd, S.: Block splitting for distributed optimization. Mathematical Programming Computation 6(1), 77\u2013102 (2014)","journal-title":"Math. Program. Comput."},{"key":"9490_CR69","doi-asserted-by":"publisher","first-page":"1805","DOI":"10.1090\/S0002-9947-96-01544-9","volume":"348","author":"R Poliquin","year":"1996","unstructured":"Poliquin, R., Rockafellar, R.: Prox-regular functions in variational analysis. Trans. Amer. Math. Soc. 348, 1805\u20131838 (1996)","journal-title":"Trans. Am. Math. Soc."},{"issue":"104","key":"9490_CR70","first-page":"3413","volume":"12","author":"B Recht","year":"2011","unstructured":"Recht, B.: A simpler approach to matrix completion. Journal of Machine Learning Research 12(104), 3413\u20133430 (2011)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"9490_CR71","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471\u2013501 (2010). 10.1137\/070697835","journal-title":"SIAM Rev."},{"key":"9490_CR72","unstructured":"Rockafellar, R.: Favorable classes of Lipschitz-continuous functions in subgradient optimization. In: Progress in nondifferentiable optimization, IIASA Collaborative Proc. Ser. CP-82, vol. 8, pp. 125\u2013143. Int. Inst. Appl. Sys. Anal., Laxenburg (1982)"},{"key":"9490_CR73","doi-asserted-by":"crossref","unstructured":"Rockafellar, R., Wets, R.B.: Variational Analysis. Grundlehren der mathematischen Wissenschaften, Vol 317, Springer, Berlin (1998)","DOI":"10.1007\/978-3-642-02431-3"},{"key":"9490_CR74","unstructured":"Rolewicz, S.: On paraconvex multifunctions. In: Third Symposium on Operations Research (Univ. Mannheim, Mannheim, 1978), Section I, Operations Res. Verfahren, vol. 31, pp. 539\u2013546. Hain, K\u00f6nigstein\/Ts. (1979)"},{"issue":"19","key":"9490_CR75","doi-asserted-by":"publisher","first-page":"9594","DOI":"10.1093\/imrn\/rnu243","volume":"2015","author":"M Rudelson","year":"2014","unstructured":"Rudelson, M., Vershynin, R.: Small ball probabilities for linear images of high-dimensional distributions. International Mathematics Research Notices 2015(19), 9594\u20139617 (2014)","journal-title":"Int. Math. Res. Not."},{"issue":"3","key":"9490_CR76","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1109\/MSP.2014.2352673","volume":"32","author":"Y Shechtman","year":"2015","unstructured":"Shechtman, Y., Eldar, Y., Cohen, O., Chapman, H., Miao, J., Segev, M.: Phase retrieval with application to optical imaging: A contemporary overview. IEEE Signal Processing Magazine 32(3), 87\u2013109 (2015). 10.1109\/MSP.2014.2352673","journal-title":"IEEE Signal Process. Mag."},{"issue":"11","key":"9490_CR77","doi-asserted-by":"publisher","first-page":"6535","DOI":"10.1109\/TIT.2016.2598574","volume":"62","author":"R Sun","year":"2016","unstructured":"Sun, R., Luo, Z.Q.: Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory 62(11), 6535\u20136579 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9490_CR78","unstructured":"Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., Recht, B.: Low-rank solutions of linear matrix equations via Procrustes flow. In: Proceedings of the 33rd International Conference on International Conference on Machine Learning, Volume 48, ICML\u201916, pp. 964\u2013973. JMLR.org (2016)"},{"key":"9490_CR79","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press (2018)"},{"key":"9490_CR80","unstructured":"Yi, X., Park, D., Chen, Y., Caramanis, C.: Fast algorithms for robust pca via gradient descent. In: Advances in neural information processing systems, pp. 4152\u20134160 (2016)"},{"key":"9490_CR81","unstructured":"Zheng, Q., Lafferty, J.: Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent. arXiv e-prints arXiv:1605.07051 (2016)"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09490-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-020-09490-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09490-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T17:05:48Z","timestamp":1637600748000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-020-09490-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,28]]},"references-count":81,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["9490"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09490-9","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,28]]},"assertion":[{"value":"5 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}