Low-rank optimization for semidefinite convex problems

Abstract

We propose an algorithm for solving nonlinear convex programs defined in terms of a symmetric positive semidefinite matrix variable $X$. This algorithm rests on the factorization $X=Y{Y}^T$, where the number of columns of Y fixes the rank of $X$. It is thus very effective for solving programs that have a low rank solution. The factorization $X=Y{Y}^T$ evokes a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second order optimization method. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. The efficiency of the proposed algorithm is illustrated on two applications: the maximal cut of a graph and the sparse principal component analysis problem.

submitted

References in corpus (1)

• A geometric Newton method for Oja's vector field

Cited by in corpus (54)

• Manopt, a Matlab toolbox for optimization on manifolds
• Stochastic gradient descent on Riemannian manifolds
• Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Large-scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications
• Low-rank optimization for distance matrix completion
• Riemannian preconditioning
• Regression on fixed-rank positive semidefinite matrices: a Riemannian approach
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Adaptive regularization with cubics on manifolds
• A Convex Relaxation for Weakly Supervised Classifiers
• QGOpt: Riemannian optimization for quantum technologies
• Convex relaxations of structured matrix factorizations
• Manifold-regression to predict from MEG/EEG brain signals without source modeling
• Understanding symmetries in deep networks
• Natural evolution strategies and variational Monte Carlo
• Modified Interior-Point Method for Large-and-Sparse Low-Rank Semidefinite Programs
• The effect of smooth parametrizations on nonconvex optimization landscapes
• Conic Optimization Theory: Convexification Techniques and Numerical Algorithms
• SGD Learns One-Layer Networks in WGANs
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Symmetry-invariant optimization in deep networks
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
• Manifold Optimization for Gaussian Mixture Models
• Riemannian Optimization for Distance-Geometric Inverse Kinematics
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
• Fenchel Duality and a Separation Theorem on Hadamard Manifolds
• Extreme MRI: Large-Scale Volumetric Dynamic Imaging from Continuous Non-Gated Acquisitions
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Accelerating Certifiable Estimation with Preconditioned Eigensolvers
• Time-Varying Semidefinite Programming: Path Following a Burer-Monteiro Factorization
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples
• Minimal Sample Subspace Learning: Theory and Algorithms
• An Intelligent Prediction System for Mobile Source Localization Using Time Delay Measurements
• Which constraints of a numerical problem cause ill-conditioning?
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming
• Low-Rank Matrix Optimization Over Affine Set
• Operator-valued formulas for Riemannian Gradient and Hessian and families of tractable metrics
• Scalable Incremental Nonconvex Optimization Approach for Phase Retrieval
• Semidefinite and Spectral Relaxations for Multi-Label Classification
• Provable Exactness for Asymmetric Low-Rank SDP Learning
• Manifold Optimization Assisted Gaussian Variational Approximation
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization
• On Riemannian Approach for Constrained Optimization Model in Extreme Classification Problems
• Memory-Efficient Approximation Algorithms for Max-k-Cut and Correlation Clustering