Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems

Abstract

We study the projected gradient descent method on low-rank matrix problems with a strongly convex objective. We use the Burer-Monteiro factorization approach to implicitly enforce low-rankness; such factorization introduces non-convexity in the objective. We focus on constraint sets that include both positive semi-definite (PSD) constraints and specific matrix norm-constraints. Such criteria appear in quantum state tomography and phase retrieval applications. We show that non-convex projected gradient descent favors local linear convergence in the factored space. We build our theory on a novel descent lemma, that non-trivially extends recent results on the unconstrained problem. The resulting algorithm is Projected Factored Gradient Descent, abbreviated as ProjFGD, and shows superior performance compared to state of the art on quantum state tomography and sparse phase retrieval applications.

28 pages

Cited by in corpus (14)

• The Non-convex Geometry of Low-rank Matrix Optimization
• A Survey of Optimization Methods from a Machine Learning Perspective
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Robust PCA by Manifold Optimization
• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Provable quantum state tomography via non-convex methods
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing