A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
This addresses optimization bottlenecks in fields like signal processing and combinatorial relaxations, though it is an incremental improvement combining existing Riemannian and convex insights.
The paper tackles optimization problems over semidefinite matrices with block-diagonal constraints, common in estimation tasks like phases and rotations, by proposing a Riemannian low-rank algorithm that is orders of magnitude faster and more accurate than state-of-the-art methods on specific instances.
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.