Local Minima and Convergence in Low-Rank Semidefinite Programming

2004/12/29 by Samuel Burer, Renato D.C. Monteiro, Renato D. C. Monteiro · 34 citations
Mathematics · Engineering · Computer Science · #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs

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

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\n 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