Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

Abstract

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$.

Added new results for general rectangular matrices

References in corpus (5)

• An overview of low-rank matrix recovery from incomplete observations
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Guaranteed Rank Minimization via Singular Value Projection
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Dropping Convexity for Faster Semi-definite Optimization

Cited by in corpus (61)

• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• 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
• Matrix Completion has No Spurious Local Minimum
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• When Are Nonconvex Problems Not Scary?
• The Non-convex Geometry of Low-rank Matrix Optimization
• Low Rank Phase Retrieval
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Dropping Convexity for Faster Semi-definite Optimization
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Convolutional Phase Retrieval via Gradient Descent
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Solving Complex Quadratic Systems with Full-Rank Random Matrices
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Alternating minimization and alternating descent over nonconvex sets
• Matrix Completion and Related Problems via Strong Duality
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization
• Bilinear Compressed Sensing under known Signs via Convex Programming
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation
• Fast Convergence for Langevin Diffusion with Manifold Structure
• Sparse GCA and Thresholded Gradient Descent
• Spectral Compressed Sensing via Projected Gradient Descent
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Phaseless Subspace Tracking
• Provable Low Rank Phase Retrieval
• On the analysis of optimization with fixed-rank matrices: a quotient geometric view
• Online Tensor Inference