Rank Optimality for the Burer--Monteiro Factorization

DOI10.1137/19M1255318zbMath1451.90114arXiv1812.03046MaRDI QIDQ4971016

Alden Waters, Irène Waldspurger

Publication date: 8 October 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingBurer-Monteiro factorization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Numerical optimization and variational techniques (65K10)

Related Items (10)

Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method ⋮ Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis ⋮ Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization ⋮ Low-Rank Univariate Sum of Squares Has No Spurious Local Minima ⋮ Linear Programming on the Stiefel Manifold ⋮ Memory-Efficient Structured Convex Optimization via Extreme Point Sampling ⋮ On the Simplicity and Conditioning of Low Rank Semidefinite Programs ⋮ An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity ⋮ Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs ⋮ Scalable Semidefinite Programming

Uses Software

• Unnamed Item
• SDPLR
• SE-Sync

Cites Work

• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• Laplacian eigenvalues and the maximum cut problem
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A geometric analysis of phase retrieval
• Implementation of a primal-dual method for SDP on a shared memory parallel architecture
• Local minima and convergence in low-rank semidefinite programming
• Phase recovery, MaxCut and complex semidefinite programming
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• Exact Recovery in the Stochastic Block Model
• Low-Rank Optimization on the Cone of Positive Semidefinite Matrices
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Global rates of convergence for nonconvex optimization on manifolds
• Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
• The non-convex geometry of low-rank matrix optimization
• Handbook of semidefinite programming. Theory, algorithms, and applications

This page was built for publication: Rank Optimality for the Burer--Monteiro Factorization