Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
Not on the map. Why?
Abstract (arXiv)
Low-rank matrix estimation plays a central role in various applications across science and engineering. Recently, nonconvex formulations based on matrix factorization are provably solved by simple gradient descent algorithms with strong computational and statistical guarantees. However, when the low-rank matrices are asymmetric, existing approaches rely on adding a regularization term to balance the scale of the two matrix factors which in practice can be removed safely without hurting the performance when initialized via the spectral method. In this paper, we provide a theoretical justification to this for the matrix sensing problem, which aims to recover a low-rank matrix from a small number of linear measurements. As long as the measurement ensemble satisfies the restricted isometry property, gradient descent -- in conjunction with spectral initialization -- converges linearly without the need of explicitly promoting balancedness of the factors; in fact, the factors stay balanced automatically throughout the execution of the algorithm. Our analysis is based on analyzing the evolution of a new distance metric that directly accounts for the ambiguity due to invertible transforms, and might be of independent interest.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 28 of its 47 references that are in the map. First posted on arXiv 13 Jan 2021.
Builds on
28 of 47 references.
References · 28
- 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
- 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
- 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
- 2016Matrix Completion has No Spurious Local Minimumcited by 124
- 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
- 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
- 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
- 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
- 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
- 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
- 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
- 2016The non-convex Burer-Monteiro approach works on smooth semidefinite programscited by 44
16 more
- 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
- 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
- 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
- 2017Global Optimality in Low-rank Matrix Optimizationcited by 35
- 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
- 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
- 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
- 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
- 2016Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provablycited by 22
- 2013Robust Spectral Compressed Sensing via Structured Matrix Completioncited by 13
- 2018Nonconvex Matrix Factorization from Rank-One Measurementscited by 13
- 2018The Global Optimization Geometry of Shallow Linear Neural Networkscited by 11
- 2017Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descentcited by 10
- 2015Sharp Time--Data Tradeoffs for Linear Inverse Problemscited by 8
- 2018Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flowcited by 8
- 2020The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularizationcited by 7
Built on by
Citing papers per year: 2022: 1; 2023: 1.
2 papers.