Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

2015/07/13 by Stephen Tu, Tu, Stephen, Ross Boczar +7 · 16 citations
Engineering · Mathematics · #FOS: Mathematics #Microwave Imaging and Scattering Analysis #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1507.03566

openalex publication_date 2015/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁ × n₂ matrix of rank r when the number of measurements exceeds a constant times (n₁+n₂)r.

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

Cited by

• Two Datasets Are Better Than One: Method of Double Moments for 3-D Reconstruction in Cryo-EM
• Two-Layer Linear Auto-Regressive Models Estimate Latent States
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Gradient descent with nonconvex constraints: local concavity determines convergence
• High-dimensional low-rank matrix regression with unknown latent structures
• On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functions
• Spectral Compressed Sensing via Projected Gradient Descent
• When Embedding Models Meet: Procrustes Bounds and Applications
• Simple and practical algorithms for ℓ_p-norm low-rank approximation
• A Simple Adaptive Proximal Gradient Method for Nonconvex Optimization
• Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Generalized Bayesian Inference for Dynamic Random Dot Product Graphs
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers\n are Automatically Balanced
• Fast Convergence for Langevin Diffusion with Manifold Structure
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization

Related

• Nonconvex Robust Low-rank Matrix Recovery
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Low-rank matrix recovery with composite optimization: good conditioning\n and rapid convergence
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery