On the simplicity and conditioning of low rank semidefinite programs
From MaRDI portal
(Redirected from On the simplicity and conditioning of low rank semidefinite programs)
Abstract: Low rank matrix recovery problems appear widely in statistics, combinatorics, and imaging. One celebrated method for solving these problems is to formulate and solve a semidefinite program (SDP). It is often known that the exact solution to the SDP with perfect data recovers the solution to the original low rank matrix recovery problem. It is more challenging to show that an approximate solution to the SDP formulated with noisy problem data acceptably solves the original problem; arguments are usually ad hoc for each problem setting, and can be complex. In this note, we identify a set of conditions that we call simplicity that limit the error due to noisy problem data or incomplete convergence. In this sense, simple SDPs are robust: simple SDPs can be (approximately) solved efficiently at scale; and the resulting approximate solutions, even with noisy data, can be trusted. Moreover, we show that simplicity holds generically, and also for many structured low rank matrix recovery problems, including the stochastic block model, synchronization, and matrix completion. Formally, we call an SDP simple if it has a surjective constraint map, admits a unique primal and dual solution pair, and satisfies strong duality and strict complementarity. However, simplicity is not a panacea: we show the Burer-Monteiro formulation of the SDP may have spurious second-order critical points, even for a simple SDP with a rank 1 solution.
Recommendations
- s-semigoodness for low-rank semidefinite matrix recovery
- Rank optimality for the Burer-Monteiro factorization
- Local minima and convergence in low-rank semidefinite programming
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
Cites work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A simpler approach to matrix completion
- A unified approach to error bounds for structured convex optimization problems
- Array imaging using intensity-only measurements
- Complementarity and nondegeneracy in semidefinite programming
- Conditioning of semidefinite programs
- Constraint Nondegeneracy in Variational Analysis
- Constraint Nondegeneracy, Strong Regularity, and Nonsingularity in Semidefinite Programming
- Convex optimization theory.
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Error Bounds for Linear Matrix Inequalities
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Exact matrix completion via convex optimization
- Faster subgradient methods for functions with Hölderian growth
- Generic minimizing behavior in semialgebraic optimization
- Generic nondegeneracy in convex optimization
- Global rates of convergence for nonconvex optimization on manifolds
- scientific article; zbMATH DE number 3121284 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Incoherence-Optimal Matrix Completion
- Learning Theory
- Lectures on convex optimization
- On the Convergence of the Central Path in Semidefinite Optimization
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Phase recovery, MaxCut and complex semidefinite programming
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- Problems of distance geometry and convex properties of quadratic maps
- Random Laplacian matrices and convex relaxations
- Rank optimality for the Burer-Monteiro factorization
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Strongly Regular Generalized Equations
- Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Why Are Big Data Matrices Approximately Low Rank?
Cited in
(11)- Local minima and convergence in low-rank semidefinite programming
- The problem of semidefinite least squares with low rank
- Conditions for existence of dual certificates in rank-one semidefinite problems
- s-semigoodness for low-rank semidefinite matrix recovery
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- A strict complementarity approach to error bound and sensitivity of solution of conic programs
- Accelerated first-order methods for a class of semidefinite programs
- An overview and comparison of spectral bundle methods for primal and dual semidefinite programs
- Low-rank extragradient methods for scalable semidefinite optimization
- Scalable approximate optimal diagonal preconditioning
This page was built for publication: On the simplicity and conditioning of low rank semidefinite programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162653)
