Local Minima and Convergence in Low-Rank Semidefinite Programming

2004/12/29 by Samuel Burer, Renato D.C. Monteiro, Renato D. C. Monteiro · 372 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Convergence (economics) #Mathematical optimization #Mathematics #Maxima and minima #Quadratic equation #Quadratic programming #Quadratically constrained quadratic program #Rank (graph theory) #Semidefinite embedding #Semidefinite programming #Set (abstract data type) #Sparse and Compressive Sensing Techniques

paper · doi:10.1007/s10107-004-0564-1

published in Mathematical Programming 103(3), 427-444 (Springer Science+Business Media)

openalex publication_date 2004/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Citations

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

Cited by

• Adaptive regularization with cubics on manifolds
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Nonconvex matrix factorization is geodesically convex: global landscape analysis for fixed-rank matrix optimization from a Riemannian perspective
• Using Negative Curvature in Solving Nonlinear Programs
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Social Trust Prediction via Max-norm Constrained 1-bit Matrix Completion
• A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal
• Semidefinite Relaxations for Best Rank-1 Tensor Approximations
• Graphical Model-based Inference on Persistent Homology
• Solving exact and noisy rank-one tensor completion with semidefinite programming
• Convex semidefinite tensor optimization and quantum entanglement
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• On the computational and statistical complexity of over-parameterized matrix sensing
• Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Data
• Optimization in Theory and Practice
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Tightness of SDP and Burer-Monteiro Factorization for Phase Synchronization in High-Noise Regime
• Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix Factorization
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Exact and Heuristic Algorithms for Constrained Biclustering
• The Minimum-Rank Gram Matrix Completion via Modified Fixed Point Continuation Method
• Sensor network localization has a benign landscape after low-dimensional relaxation
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• The Augmented Mixing Method: Computing High-Accuracy Primal-Dual Solutions to Large-Scale SDPs via Column Updates
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• A Fast Algorithm for Convolutional Structured Low-Rank Matrix Recovery
• A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• The Nonconvex Geometry of Linear Inverse Problems
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• A convex lifting approach for the Calderón problem
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• A Brief Introduction to Manifold Optimization
• Rigorous Maximum Likelihood Estimation for Quantum States
• Nonconvex Robust Low-rank Matrix Recovery
• A Graph Decomposition motivated by the Geometry of Randomized Rounding
• Cine cone beam CT reconstruction using low-rank matrix factorization: algorithm and a proof-of-princple study
• Identifiability Conditions for Multi-channel Blind Deconvolution with Short Filters
• An efficient nonconvex reformulation of stagewise convex optimization problems
• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
• Optimization for deep learning: theory and algorithms
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Solving ptychography with a convex relaxation
• Simultaneous Phase Retrieval and Blind Deconvolution via Convex Programming
• New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
• cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming
• On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• Inverse Kinematics as Low-Rank Euclidean Distance Matrix Completion
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• A novel variational form of the Schatten-p quasi-norm
• Burer-Monteiro factorizability of nuclear norm regularized optimization
• Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-Łojasiewicz Inequality
• Online Optimization for Large-Scale Max-Norm Regularization
• Fast Nonconvex SDP Solvers for Large-scale Power System State Estimation
• A Unified Framework for Sample Complexity of Structured Quantum State Tomography under Noisy Observations
• Multichannel myopic deconvolution in underwater acoustic channels via low-rank recovery. [europepmc]
• A Relaxed Interior Point Method for Low-Rank Semidefinite Programming Problems with Applications to Matrix Completion. [europepmc]
• Semidefinite programming for manipulating acoustic traps in real time (SMART). [europepmc]