Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
arXiv:1511.01562
Abstract
We establish theoretical recovery guarantees of a family of Riemannian optimization algorithms for low rank matrix recovery, which is about recovering an rank matrix from number of linear measurements. The algorithms are first interpreted as iterative hard thresholding algorithms with subspace projections. Based on this connection, we show that provided the restricted isometry constant of the sensing operator is less than , the Riemannian gradient descent algorithm and a restarted variant of the Riemannian conjugate gradient algorithm are guaranteed to converge linearly to the underlying rank matrix if they are initialized by one step hard thresholding. Empirical evaluation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements necessary.
References in corpus (10)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- A Simpler Approach to Matrix Completion
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- A Riemannian geometry for low-rank matrix completion
- The local convexity of solving systems of quadratic equations
- Guarantees of Riemannian Optimization for Low Rank Matrix Completion
- Low-rank Matrix Completion using Alternating Minimization
- R3MC: A Riemannian three-factor algorithm for low-rank matrix completion
Cited by in corpus (6)
- Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
- Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
- Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
- Guarantees of Riemannian Optimization for Low Rank Matrix Completion
- Convolutional Phase Retrieval via Gradient Descent
- Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion