Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation

DOI10.1007/s10208-020-09471-yzbMath1478.90076arXiv1801.00368OpenAlexW3088458178MaRDI QIDQ2231643

Augustin Cosse, Laurent Demanet

Publication date: 30 September 2021

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.00368

zbMATH Keywords

convex optimizationsemidefinite programmingmatrix completionsum-of-squares polynomialsduality in optimizationsemidefinite programming hierarchies

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Efficient Identification of Butterfly Sparse Matrix Factorizations

Uses Software

• SDPLR
• PhaseLift

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Semidefinite programming relaxations for semialgebraic problems
• An exact Jacobian SDP relaxation for polynomial optimization
• Local minima and convergence in low-rank semidefinite programming
• Exact matrix completion via convex optimization
• Global Optimization with Polynomials and the Problem of Moments
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
• Theta Bodies for Polynomial Ideals
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Class of global minimum bounds of polynomial functions
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• All Real Eigenvalues of Symmetric Tensors
• Matrix Completion From a Few Entries
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Simpler Approach to Matrix Completion
• Towards a Mathematical Theory of Super‐resolution
• The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• Phase Retrieval via Matrix Completion
• Propagation Connectivity of Random Hypergraphs