A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
arXiv:1506.00575
Abstract
We propose a new algorithm to solve optimization problems of the form for a smooth function under the constraints that is positive semidefinite and the diagonal blocks of are small identity matrices. Such problems often arise as the result of relaxing a rank constraint (lifting). In particular, many estimation tasks involving phases, rotations, orthonormal bases or permutations fit in this framework, and so do certain relaxations of combinatorial problems such as Max-Cut. The proposed algorithm exploits the facts that (1) such formulations admit low-rank solutions, and (2) their rank-restricted versions are smooth optimization problems on a Riemannian manifold. Combining insights from both the Riemannian and the convex geometries of the problem, we characterize when second-order critical points of the smooth problem reveal KKT points of the semidefinite problem. We compare against state of the art, mature software and find that, on certain interesting problem instances, what we call the staircase method is orders of magnitude faster, is more accurate and scales better. Code is available.
arXiv comment37 pages, 3 figures
References in corpus (12)
- Manopt, a Matlab toolbox for optimization on manifolds
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Near-Optimal Joint Object Matching via Convex Relaxation
- Semidefinite descriptions of the convex hull of rotation matrices
- Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
- Convex recovery from interferometric measurements
- Complete Dictionary Recovery over the Sphere
- Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
- Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
- MADMM: a generic algorithm for non-smooth optimization on manifolds
- Pose Graph Optimization in the Complex Domain: Lagrangian Duality, Conditions For Zero Duality Gap, and Optimal Solutions
- Disentangling Orthogonal Matrices
Cited by in corpus (22)
- Global rates of convergence for nonconvex optimization on manifolds
- Nonconvex phase synchronization
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Near-optimal bounds for phase synchronization
- Bispectrum Inversion with Application to Multireference Alignment
- On the low-rank approach for semidefinite programs arising in synchronization and community detection
- Asynchronous and Parallel Distributed Pose Graph Optimization
- Dropping Convexity for Faster Semi-definite Optimization
- Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
- The non-convex Burer-Monteiro approach works on smooth semidefinite programs
- Distributed methods for synchronization of orthogonal matrices over graphs
- Certifiably Correct Range-Aided SLAM
- A Cubic Regularized Newton's Method over Riemannian Manifolds
- Toward Globally Optimal State Estimation Using Automatically Tightened Semidefinite Relaxations
- Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach
- Accelerating Certifiable Estimation with Preconditioned Eigensolvers
- Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
- Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
- Lecture notes on non-convex algorithms for low-rank matrix recovery
- CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation
- Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
- Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs