Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

By Stephen Tu, Ross Boczar, Max Simchowitz, M. Soltanolkotabi, B. Recht. International Conference on Machine Learning, 2015

420 citations recorded by the source corpus.

In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a $n_1 \times n_2$ matrix of rank $r$ when the number of measurements exceeds a constant times $(n_1+n_2)r$.

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/1eb94de6649346765f920d88b7de0ff05d16718d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

1. Samet Oymak
2. Yuanzhi Li
3. M. Soltanolkotabi
4. Yonina C. Eldar
5. Yuejie Chi
6. Yuxin Chen
7. Rong Ge
8. Tengyu Ma

In Computational Mechanics

1. Jason D. Lee
2. Yuejie Chi
3. Yuxin Chen
4. Tengyu Ma
5. Yue M. Lu
6. Simon Shaolei Du
7. Yuanzhi Li
8. Wei Hu

In Mathematical Physics

1. Tengyu Ma
2. Jason D. Lee
3. Samet Oymak
4. Yuanzhi Li
5. Yuxin Chen
6. Rong Ge
7. Hongyang Zhang
8. M. Soltanolkotabi

Citations in the corpus

• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, result): “Specified to the noiseless setting with = 0, Corollary 2 is similar to the results for nonconvex gradient descent in [58, 66].”
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, positive): “In [Tu et al., 2015, Ge et al., 2017a], a regularization term for balancing the two layers is added to (1): min UPRd1ˆr,V PRd2ˆr 1 2 › ›UV J ´M › › 2 F ` 1 8 › ›UJU ´ V JV › › 2 F .”
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “For instance, Low-rank regression and generalized linear models have been considered by various works including (Bhojanapalli et al., 2016; Chen et al., 2018; Josz et al., 2018; Sun et al., 2018; Tu et al., 2015) in such an overdetermined setting.”
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “…first uses spectral initialization to find a near-optimal solution, then starting from there, gradient descent converges to an optimum with a linear rate [Tu et al., 2016, Zheng and Lafferty, 2016, Zhao et al., 2015, Bhojanapalli et al., 2016], though in practice random initialization often suffices.”
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “For specific problems such as phase retrieval [11], low-rank estimation [16, 72], and dictionary learning [1, 64], many algorithms are developed by leveraging the particular structure of the problems, and the either use a smart initialization [11, 65] or initialize randomly [18, 14].”
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “There is a growing list of statistical estimation problems for which nonconvex approaches are guaranteed to find global optimal solutions, including but not limited to phase retrieval [18,25,90], low-rank matrix sensing and completion [7,32,48,115,130], blind deconvolution and self-calibration [72,7”
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[68] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht.”
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, methodology): “First, in parallel with spectral initialization methods, t he proposed orthogonality-promoting initialization can be applied for semidefinite optimization [38], [39], mat rix completion [63], [42] as well as blind deconvolution [40], [41].”
• An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “This reformulation is driven by the fact that the nuclear norm is equal to the minimum Frobenius norm factorization [116]: We can then replace (7) with minimize and if the solution to (7) does indeed have rank at most R , it will also be the solution to (10).”
• Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, neutral): “For example, see Tu et al. [2016].”
• Learning Compact Neural Networks with Regularization (2018, methodology): “[57] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht.”
• Implicit Regularization in Deep Matrix Factorization (2019, background): “Notable works proving successful recovery of a low-rank matrix through matrix factorization trained by gradient descent with no explicit regularization are [48, 35, 32].”
• Global Optimality of Local Search for Low Rank Matrix Recovery (2016, background): “[26], Chen and Wainwright [8], Bhojanapalli et al.”
• Exploiting Shared Representations for Personalized Federated Learning (2021, methodology): “Both the iterates of FedRep and GD-GD were initialized with the SVD of the result of 10 rounds of projected gradient descent on the unfactorized matrix sensing objective as in Algorithm 1 in Tu et al. [2016]. We would like to note that FedRep exhibited the same convergence trajectories regardless of”
• The non-convex geometry of low-rank matrix optimization (2016, methodology): “Therefore, in addition to low-rank matrix recovery problems [24, 25, 36, 53, 58], it is also applicable to many other low-rank matrix optimization problems with non-quadratic objective functions, including 1-bit matrix recovery, robust PCA [24], and low-rank matrix recovery with non-Gaussian noise [”