A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

Abstract

We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With $O(r^3{\kappa }^{2}n\log n)$ random measurements of a positive semidefinite $n\times n$ matrix of rank $r$ and condition number $\kappa$, our method is guaranteed to converge linearly to the global optimum.

Fix a minor error in Appendix E

References in corpus (1)

• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

Cited by in corpus (15)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Low Rank Phase Retrieval
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Dropping Convexity for Faster Semi-definite Optimization
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Convolutional Phase Retrieval via Gradient Descent
• Orthogonal Inductive Matrix Completion
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Phase diagram of matrix compressed sensing
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization