Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements

2017/01/02 by Xiao Zhang, Lingxiao Wang, Zhang, Xiao +3 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (stat.ML) #Medical Image Segmentation Techniques #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1701.00481

openalex publication_date 2017/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization. We propose an efficient stochastic variance reduced gradient descent algorithm to solve a nonconvex optimization problem of matrix sensing. Our algorithm is applicable to both noisy and noiseless settings. In the case with noisy observations, we prove that our algorithm converges to the unknown low-rank matrix at a linear rate up to the minimax optimal statistical error. And in the noiseless setting, our algorithm is guaranteed to linearly converge to the unknown low-rank matrix and achieves exact recovery with optimal sample complexity. Most notably, the overall computational complexity of our proposed algorithm, which is defined as the iteration complexity times per iteration time complexity, is lower than the state-of-the-art algorithms based on gradient descent. Experiments on synthetic data corroborate the superiority of the proposed algorithm over the state-of-the-art algorithms.

Citations

• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Fast and Simple PCA via Convex Optimization
• Stochastic Variance Reduction for Nonconvex Optimization
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Nuclear norm penalization and optimal rates for noisy low rank matrix completion

Cited by

• On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization

Related

• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Robust Sensing of Low-Rank Matrices with Non-Orthogonal Sparse Decomposition
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent