{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T20:59:38Z","timestamp":1778619578852,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T00:00:00Z","timestamp":1600992000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T00:00:00Z","timestamp":1600992000000},"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,8]]},"DOI":"10.1007\/s10208-020-09471-y","type":"journal-article","created":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T14:03:01Z","timestamp":1601042581000},"page":"891-940","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Stable Rank-One Matrix Completion is Solved by the Level 2 Lasserre Relaxation"],"prefix":"10.1007","volume":"21","author":[{"given":"Augustin","family":"Cosse","sequence":"first","affiliation":[]},{"given":"Laurent","family":"Demanet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,25]]},"reference":[{"key":"9471_CR1","doi-asserted-by":"crossref","unstructured":"A.\u00a0A. Ahmadi, G.\u00a0Hall, A.\u00a0Papachristodoulou, J.\u00a0Saunderson, and Y.\u00a0Zheng. Improving efficiency and scalability of sum of squares optimization: Recent advances and limitations. arXiv:1710.01358, 2017.","DOI":"10.1109\/CDC.2017.8263706"},{"key":"9471_CR2","unstructured":"A.\u00a0S. Bandeira. Convex relaxations for certain inverse problems on graphs. 2015."},{"key":"9471_CR3","unstructured":"B.\u00a0Barak and A.\u00a0Moitra. Tensor prediction, Rademacher complexity and random 3-XOR. arXiv:1501.06521, 2015."},{"key":"9471_CR4","doi-asserted-by":"crossref","unstructured":"R.\u00a0Berke and M.\u00a0Onsj\u00f6. Propagation connectivity of random hypergraphs. In Stochastic Algorithms: Foundations and Applications, pages 117\u2013126. Springer, 2009.","DOI":"10.1007\/978-3-642-04944-6_10"},{"issue":"2","key":"9471_CR5","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"S.\u00a0Burer and R.\u00a0Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329\u2013357, 2003.","journal-title":"Mathematical Programming"},{"issue":"3","key":"9471_CR6","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-004-0564-1","volume":"103","author":"S Burer","year":"2005","unstructured":"S.\u00a0Burer and R.\u00a0D. Monteiro. Local minima and convergence in low-rank semidefinite programming. Mathematical Programming, 103(3):427\u2013444, 2005.","journal-title":"Mathematical Programming"},{"issue":"2","key":"9471_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/151005099","volume":"57","author":"EJ Cand\u00e8s","year":"2015","unstructured":"E.\u00a0J. Cand\u00e8s, Y.\u00a0C. Eldar, T.\u00a0Strohmer, and V.\u00a0Voroninski. Phase retrieval via matrix completion. SIAM review, 57(2):225\u2013251, 2015.","journal-title":"SIAM review"},{"issue":"6","key":"9471_CR8","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1002\/cpa.21455","volume":"67","author":"EJ Cand\u00e8s","year":"2014","unstructured":"E.\u00a0J. Cand\u00e8s and C.\u00a0Fernandez-Granda. Towards a mathematical theory of super-resolution. Communications on Pure and Applied Mathematics, 67(6):906\u2013956, 2014.","journal-title":"Communications on Pure and Applied Mathematics"},{"issue":"6","key":"9471_CR9","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","volume":"98","author":"EJ Cand\u00e8s","year":"2010","unstructured":"E.\u00a0J. Cand\u00e8s and Y.\u00a0Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):925\u2013936, 2010.","journal-title":"Proceedings of the IEEE"},{"issue":"6","key":"9471_CR10","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e8s","year":"2009","unstructured":"E.\u00a0J. Cand\u00e8s and B.\u00a0Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717\u2013772, 2009.","journal-title":"Foundations of Computational mathematics"},{"issue":"8","key":"9471_CR11","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1002\/cpa.21432","volume":"66","author":"EJ Cand\u00e8s","year":"2013","unstructured":"E.\u00a0J. Cand\u00e8s, T.\u00a0Strohmer, and V.\u00a0Voroninski. 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":"Communications on Pure and Applied Mathematics"},{"issue":"5","key":"9471_CR12","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"EJ Cand\u00e8s","year":"2010","unstructured":"E.\u00a0J. Cand\u00e8s and T.\u00a0Tao. The power of convex relaxation: Near-optimal matrix completion. Information Theory, IEEE Transactions on, 56(5):2053\u20132080, 2010.","journal-title":"Information Theory, IEEE Transactions on"},{"key":"9471_CR13","doi-asserted-by":"crossref","unstructured":"A.\u00a0Cosse and L.\u00a0Demanet. Rank-one matrix completion is solved by the sum-of-squares relaxation of order two. In Proceedings of the 6th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP\u201915). IEEE, 2015.","DOI":"10.1109\/CAMSAP.2015.7383723"},{"issue":"4","key":"9471_CR14","doi-asserted-by":"publisher","first-page":"1582","DOI":"10.1137\/140962292","volume":"35","author":"C-F Cui","year":"2014","unstructured":"C.-F. Cui, Y.-H. Dai, and J.\u00a0Nie. All real eigenvalues of symmetric tensors. SIAM Journal on Matrix Analysis and Applications, 35(4):1582\u20131601, 2014.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9471_CR15","unstructured":"L.\u00a0Demanet and V.\u00a0Jugnon. Convex recovery from interferometric measurements. arXiv:1307.6864, 2013."},{"key":"9471_CR16","unstructured":"M.\u00a0Fazel. Matrix rank minimization with applications. PhD thesis, Stanford University, March 2002."},{"issue":"6","key":"9471_CR17","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"M.\u00a0X. Goemans and D.\u00a0P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115\u20131145, 1995.","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"9471_CR18","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1137\/090746525","volume":"20","author":"J Gouveia","year":"2010","unstructured":"J.\u00a0Gouveia, P.\u00a0A. Parrilo, and R.\u00a0R. Thomas. Theta bodies for polynomial ideals. SIAM Journal on Optimization, 20(4):2097\u20132118, 2010.","journal-title":"SIAM Journal on Optimization"},{"key":"9471_CR19","first-page":"5180","volume-title":"Interferometric inversion: a robust approach to linear inverse problems","author":"V Jugnon","year":"2013","unstructured":"V.\u00a0Jugnon and L.\u00a0Demanet. Interferometric inversion: a robust approach to linear inverse problems. In Proceedings of SEG Annual Meeting, Houston, pages 5180\u20135184, 2013."},{"key":"9471_CR20","doi-asserted-by":"crossref","unstructured":"R.\u00a0Keshavan, A.\u00a0Montanari, and S.\u00a0Oh. Matrix completion from noisy entries. In Advances in Neural Information Processing Systems, pages 952\u2013960, 2009.","DOI":"10.1109\/ISIT.2009.5205567"},{"key":"9471_CR21","doi-asserted-by":"crossref","unstructured":"R.\u00a0H. Keshavan, A.\u00a0Montanari, and S.\u00a0Oh. Learning low rank matrices from $$O(n)$$ entries. In Communication, Control, and Computing, 2008 46th Annual Allerton Conference on, pages 1365\u20131372. IEEE, 2008.","DOI":"10.1109\/ALLERTON.2008.4797720"},{"issue":"6","key":"9471_CR22","doi-asserted-by":"publisher","first-page":"2980","DOI":"10.1109\/TIT.2010.2046205","volume":"56","author":"RH Keshavan","year":"2010","unstructured":"R.\u00a0H. Keshavan, A.\u00a0Montanari, and S.\u00a0Oh. Matrix completion from a few entries. Information Theory, IEEE Transactions on, 56(6):2980\u20132998, 2010.","journal-title":"Information Theory, IEEE Transactions on"},{"key":"9471_CR23","unstructured":"F.\u00a0Kiraly and L.\u00a0Theran. Error-minimizing estimates and universal entry-wise error bounds for low-rank matrix completion. In Advances in Neural Information Processing Systems, pages 2364\u20132372, 2013."},{"key":"9471_CR24","unstructured":"F.\u00a0Kir\u00e1ly and R.\u00a0Tomioka. A combinatorial algebraic approach for the identifiability of low-rank matrix completion. arXiv:1206.6470, 2012."},{"key":"9471_CR25","first-page":"1391","volume":"16","author":"FJ Kir\u00e1ly","year":"2015","unstructured":"F.\u00a0J. Kir\u00e1ly, L.\u00a0Theran, and R.\u00a0Tomioka. The algebraic combinatorial approach for low-rank matrix completion. Journal of Machine Learning Research, 16:1391\u20131436, 2015.","journal-title":"Journal of Machine Learning Research"},{"issue":"3","key":"9471_CR26","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"J.\u00a0B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796\u2013817, 2001.","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"9471_CR27","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/05064504X","volume":"17","author":"JB Lasserre","year":"2006","unstructured":"J.\u00a0B. Lasserre. Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM Journal on Optimization, 17(3):822\u2013843, 2006.","journal-title":"SIAM Journal on Optimization"},{"key":"9471_CR28","doi-asserted-by":"crossref","unstructured":"M.\u00a0Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, pages 157\u2013270. Springer, 2009.","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"9471_CR29","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Nesterov. Squared functional systems and optimization problems. In High performance optimization, pages 405\u2013440. Springer, 2000.","DOI":"10.1007\/978-1-4757-3216-0_17"},{"issue":"1\u20132","key":"9471_CR30","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-011-0489-4","volume":"137","author":"J Nie","year":"2013","unstructured":"J.\u00a0Nie. An exact jacobian SDP relaxation for polynomial optimization. Mathematical Programming, 137(1-2):225\u2013255, 2013.","journal-title":"Mathematical Programming"},{"issue":"4","key":"9471_CR31","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1137\/060668791","volume":"19","author":"J Nie","year":"2008","unstructured":"J.\u00a0Nie and J.\u00a0Demmel. Sparse SoS relaxations for minimizing functions that are summations of small polynomials. SIAM Journal on Optimization, 19(4):1534\u20131558, 2008.","journal-title":"SIAM Journal on Optimization"},{"key":"9471_CR32","unstructured":"P.\u00a0A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, Citeseer, 2000."},{"issue":"2","key":"9471_CR33","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"P.\u00a0A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96(2):293\u2013320, 2003.","journal-title":"Mathematical programming"},{"key":"9471_CR34","first-page":"3413","volume":"12","author":"B Recht","year":"2011","unstructured":"B.\u00a0Recht. A simpler approach to matrix completion. The Journal of Machine Learning Research, 12:3413\u20133430, 2011.","journal-title":"The Journal of Machine Learning Research"},{"issue":"3","key":"9471_CR35","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"B.\u00a0Recht, M.\u00a0Fazel, and P.\u00a0Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471\u2013501, 2010.","journal-title":"SIAM Review"},{"key":"9471_CR36","doi-asserted-by":"crossref","unstructured":"R.\u00a0T. Rockafellar. Convex analysis. Number\u00a028. Princeton university press, 1970.","DOI":"10.1515\/9781400873173"},{"issue":"6","key":"9471_CR37","first-page":"731","volume":"23","author":"N Shor","year":"1987","unstructured":"N.\u00a0Shor. Class of global minimum bounds of polynomial functions. Cybernetics and Systems Analysis, 23(6):731\u2013734, 1987.","journal-title":"Cybernetics and Systems Analysis"},{"issue":"6","key":"9471_CR38","first-page":"1","volume":"25","author":"NZ Shor","year":"1987","unstructured":"N.\u00a0Z. Shor. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 25(6):1\u201311, 1987.","journal-title":"Soviet Journal of Computer and Systems Sciences"},{"issue":"5","key":"9471_CR39","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1007\/BF01074929","volume":"23","author":"NZ Shor","year":"1988","unstructured":"N.\u00a0Z. Shor. An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics, 23(5):695\u2013700, 1988.","journal-title":"Cybernetics"},{"issue":"4","key":"9471_CR40","doi-asserted-by":"publisher","first-page":"1621","DOI":"10.1137\/090750688","volume":"31","author":"A Singer","year":"2010","unstructured":"A.\u00a0Singer and M.\u00a0Cucuringu. Uniqueness of low-rank matrix completion by rigidity theory. SIAM Journal on Matrix Analysis and Applications, 31(4):1621\u20131641, 2010.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9471_CR41","unstructured":"G.\u00a0Tang and P.\u00a0Shah. Guaranteed tensor decomposition: A moment approach. In Proceedings of The 32nd International Conference on Machine Learning, pages 1491\u20131500, 2015."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09471-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-020-09471-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09471-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,25]],"date-time":"2021-09-25T00:39:18Z","timestamp":1632530358000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-020-09471-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,25]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["9471"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09471-y","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,25]]},"assertion":[{"value":"22 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}