A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints

Abstract

We propose a new algorithm to solve optimization problems of the form $\min f(X)$ for a smooth function $f$ under the constraints that $X$ is positive semidefinite and the diagonal blocks of $X$ 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.

37 pages, 3 figures

References in corpus (7)

• Semidefinite descriptions of the convex hull of rotation matrices
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Complete Dictionary Recovery over the Sphere
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• 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 (21)

• Global rates of convergence for nonconvex optimization on manifolds
• Nonconvex phase 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
• Accelerating Certifiable Estimation with Preconditioned Eigensolvers
• Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach
• 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
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation
• Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs