{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:00:24Z","timestamp":1757311224692,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,20]],"date-time":"2020-11-20T00:00:00Z","timestamp":1605830400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,20]],"date-time":"2020-11-20T00:00:00Z","timestamp":1605830400000},"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":["Math. Program."],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s10107-020-01590-2","type":"journal-article","created":{"date-parts":[[2020,11,20]],"date-time":"2020-11-20T14:06:13Z","timestamp":1605881173000},"page":"75-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Role of sparsity and structure in the optimization landscape of non-convex matrix sensing"],"prefix":"10.1007","volume":"193","author":[{"given":"Igor","family":"Molybog","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Somayeh","family":"Sojoudi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4294-1338","authenticated-orcid":false,"given":"Javad","family":"Lavaei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,20]]},"reference":[{"issue":"4","key":"1590_CR1","doi-asserted-by":"publisher","first-page":"2775","DOI":"10.1137\/140979861","volume":"26","author":"A Agarwal","year":"2016","unstructured":"Agarwal, A., et al.: Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM J. Optim. 26(4), 2775\u20132799 (2016)","journal-title":"SIAM J. Optim."},{"key":"1590_CR2","unstructured":"Bhojanapalli, S., Behnam, N., Srebro, N.: Global optimality of local search for low rank matrix recovery. In: Advances in Neural Information Processing Systems, pp. 3873\u20133881 (2016)"},{"key":"1590_CR3","unstructured":"Bottou, L., Bousquet, O.: The tradeoffs of large scale learning. In: Advances in Neural Information Processing Systems,pp. 161\u2013168 (2008)"},{"issue":"4","key":"1590_CR4","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1109\/TIT.2015.2399924","volume":"61","author":"EJ Candes","year":"2015","unstructured":"Candes, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval via Wirtinger flow: theory and algorithms. IEEE Trans. Inf. Theory 61(4), 1985\u20132007 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1590_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., et al.: Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval. Math. Program. 176, 5\u201337 (2019)","DOI":"10.1007\/s10107-019-01363-6"},{"key":"1590_CR6","unstructured":"Chen, Y., et al.: Noisy matrix completion: understanding statistical guarantees for convex relaxation vianonconvex optimization. arXiv preprint arXiv:1902.07698 (2019)"},{"key":"1590_CR7","doi-asserted-by":"crossref","unstructured":"Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: an overview. arXiv preprint arXiv:1809.09573 (2018)","DOI":"10.1109\/TSP.2019.2937282"},{"key":"1590_CR8","unstructured":"Daneshmand, H., et al.: Escaping saddles with stochastic gradients. arXiv\u00a0preprint arXiv:1803.05999 (2018)"},{"key":"1590_CR9","unstructured":"Frazier, P.I.: A tutorial on bayesian optimization. arXiv\u00a0preprint arXiv:1807.02811 (2018)"},{"key":"1590_CR10","unstructured":"Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: a unified geometric analysis. In: Proceedings of the 34th International Conference on Machine Learning, vol. 70, pp. 1233\u20131242. JMLR. org (2017)"},{"key":"1590_CR11","unstructured":"Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. In: Advances in Neural Information Processing Systems, p. 29732981 (2016)"},{"key":"1590_CR12","unstructured":"Ge, R., et al.: Escaping from saddle points: online stochastic gradient for tensor decomposition. arXiv:1503.02101 [cs.LG] (2015)"},{"issue":"1","key":"1590_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/050645452","volume":"50","author":"A Ghosh","year":"2008","unstructured":"Ghosh, A., Boyd, S., Saberi, A.: Minimizing effective resistance of a graph. SIAM Rev. 50(1), 37\u201366 (2008)","journal-title":"SIAM Rev."},{"key":"1590_CR14","unstructured":"Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. (2014)"},{"key":"1590_CR15","unstructured":"Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Recent Advances in Learning and Control. Lecture Notes in Control and Information Sciences, p. 95110. Springer-Verlag Limited (2008)"},{"key":"1590_CR16","doi-asserted-by":"crossref","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, pp. 665\u2013674. ACM (2013)","DOI":"10.1145\/2488608.2488693"},{"key":"1590_CR17","unstructured":"Josz, C., et al.: A theory on the absence of spurious solutions for noncon-vex and nonsmooth optimization. In: Advances in Neural Information Processing Systems, pp. 2441\u20132449 (2018)"},{"issue":"6","key":"1590_CR18","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 Trans. Inf. Theory 56(6), 2980\u20132998 (2010a)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"jul","key":"1590_CR19","first-page":"2057","volume":"11","author":"RH Keshavan","year":"2010","unstructured":"Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from noisy entries. J. Mach. Learn. Res. 11(jul), 2057\u20132078 (2010b)","journal-title":"J. Mach. Learn. Res."},{"key":"1590_CR20","unstructured":"Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems, pp. 1097\u20131105 (2012)"},{"key":"1590_CR21","unstructured":"Lee, J.D., et al.: Gradient descent only converges to minimizers. In: Conference on Learning Theory, pp. 1246\u20131257 (2016)"},{"key":"1590_CR22","unstructured":"Li, D., Ding, T., Sun, R.: Over-parameterized deep neural networks have no strict local minima for any continuous activations. arXiv\u00a0preprint arXiv:1812.11039 (2018)"},{"key":"1590_CR23","unstructured":"Li, Q., Zhu, Z., Tang, G.: Alternating minimizations converge to second-order optimal solutions. In: International Conference on Machine Learning, pp. 3935\u20133943 (2019)"},{"key":"1590_CR24","doi-asserted-by":"crossref","unstructured":"Li, Xingguo, et al.: Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Trans. Inf. Theory 65(6), 3489\u20133514 (2019)","DOI":"10.1109\/TIT.2019.2898663"},{"key":"1590_CR25","unstructured":"Mei, S., Bai, Y., Montanari, A.: The landscape of empirical risk for non-convex losses. arXiv\u00a0preprint arXiv.1607.06534 (2016)"},{"key":"1590_CR26","unstructured":"Nouiehed, M. Razaviyayn, M.: Learning deep models: critical points and local openness. arXiv\u00a0preprint arXiv:1803.02968 (2018)"},{"issue":"1","key":"1590_CR27","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"PM Pardalos","year":"1991","unstructured":"Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1(1), 15\u201322 (1991). https:\/\/doi.org\/10.1007\/BF00120662","journal-title":"J. Glob. Optim."},{"key":"1590_CR28","unstructured":"Park, D., et al.: Non-square matrix sensing without spurious local minima via the Burer\u2013Monteiro approach. arXiv\u00a0preprint arXiv:1609.03240 (2016)"},{"issue":"1","key":"1590_CR29","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1137\/17M1150116","volume":"29","author":"S Paternain","year":"2019","unstructured":"Paternain, S., Mokhtari, A., Ribeiro, A.: A newton-based method for nonconvex optimization with fast evasion of saddle points. SIAM J. Optim. 29(1), 343\u2013368 (2019)","journal-title":"SIAM J. Optim."},{"key":"1590_CR30","unstructured":"Soltanolkotabi, M.: Learning relus via gradient descent. In: Advances in Neural Information Processing Systems, 2007\u20132017 (2017)"},{"issue":"5","key":"1590_CR31","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1007\/s10208-017-9365-9","volume":"18","author":"J Sun","year":"2018","unstructured":"Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. Found. Comput. Math. 18(5), 1131\u20131198 (2018)","journal-title":"Found. Comput. Math."},{"key":"1590_CR32","doi-asserted-by":"crossref","unstructured":"Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery using nonconvex optimization. In: International Conference on Machine Learning, pp. 2351\u20132360 (2015)","DOI":"10.1109\/SAMPTA.2015.7148922"},{"issue":"11","key":"1590_CR33","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 Trans. Inf. Theory 62(11), 6535\u20136579 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20134","key":"1590_CR34","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1080\/10556789908805762","volume":"11","author":"K-C Toh","year":"1999","unstructured":"Toh, K.-C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3: a MAT-LAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1\u20134), 545\u2013581 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"1590_CR35","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.-C., Todd, M.J.: Solving semidefinite\u2013quadratic\u2013linear programs using SDPT3. Math. Program. 95(2), 189\u2013217 (2003)","journal-title":"Math. Program."},{"issue":"15","key":"1590_CR36","doi-asserted-by":"publisher","first-page":"4059","DOI":"10.1109\/TSP.2017.2684758","volume":"65","author":"N Vaswani","year":"2017","unstructured":"Vaswani, N., Nayer, S., Eldar, Yonina C.: Low-rank phase retrieval. IEEE Trans. Signal Process. 65(15), 4059\u20134074 (2017)","journal-title":"IEEE Trans. Signal Process."},{"key":"1590_CR37","unstructured":"Yun, C., Sra, S., Jadbabaie, A.: Global optimality conditions for deep neural networks. In: International Conference on Learning Representations (2018)"},{"issue":"114","key":"1590_CR38","first-page":"1","volume":"20","author":"RY Zhang","year":"2019","unstructured":"Zhang, R.Y., Sojoudi, S., Lavaei, J.: Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery. J. Mach. Learn. Res. 20(114), 1\u201334 (2019)","journal-title":"J. Mach. Learn. Res."},{"key":"1590_CR39","unstructured":"Zhang, R., et al.: How much restricted isometry is needed in nonconvex matrix recovery? In: Advances in Neural Information Processing Systems, p. 55915602 (2018)"},{"issue":"3","key":"1590_CR40","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1109\/TCNS.2017.2691473","volume":"5","author":"Y Zhang","year":"2018","unstructured":"Zhang, Y., Madani, R., Lavaei, J.: Conic relaxations for power system state estimation with line measurements. IEEE Trans. Control Netw. Syst. 5(3), 1193\u20131205 (2018)","journal-title":"IEEE Trans. Control Netw. Syst."},{"key":"1590_CR41","unstructured":"Zhao, T., Wang, Z., Liu, H.: A nonconvex optimization framework for low rank matrix estimation. In: Advances in Neural Information Processing Systems, pp. 559\u2013567 (2015)"},{"key":"1590_CR42","unstructured":"Zheng, Q., Lafferty, J.: A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. In: Advances in Neural Information Processing Systems, pp. 109\u2013117 (2015)"},{"issue":"13","key":"1590_CR43","doi-asserted-by":"publisher","first-page":"3614","DOI":"10.1109\/TSP.2018.2835403","volume":"66","author":"Zhihui Zhu","year":"2018","unstructured":"Zhu, Zhihui, et al.: Global optimality in low-rank matrix optimization. IEEE Transactions on Signal Processing 66(13), 3614\u20133628 (2018)","journal-title":"IEEE Transactions on Signal Processing"},{"issue":"1","key":"1590_CR44","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/TPWRS.2010.2051168","volume":"26","author":"RD Zimmerman","year":"2011","unstructured":"Zimmerman, R.D., Murillo-Sanchez, C.E., Thomas, R.J.: MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education. IEEE Trans. Power Syst. 26(1), 12\u201319 (2011)","journal-title":"IEEE Trans. Power Syst."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01590-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01590-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01590-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T18:10:51Z","timestamp":1650910251000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01590-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,20]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["1590"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01590-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,11,20]]},"assertion":[{"value":"4 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}