A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation

Abstract

We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observations. In the general case with noisy observations, we show that our algorithm is guaranteed to linearly converge to the unknown low-rank matrix up to minimax optimal statistical error, provided an appropriate initial estimator. While in the generic noiseless setting, our algorithm converges to the unknown low-rank matrix at a linear rate and enables exact recovery with optimal sample complexity. In addition, we develop a new initialization algorithm to provide a desired initial estimator, which outperforms existing initialization algorithms for nonconvex low-rank matrix estimation. We illustrate the superiority of our framework through three examples: matrix regression, matrix completion, and one-bit matrix completion. We also corroborate our theory through extensive experiments on synthetic data.

arXiv comment33 pages, 3 figures

References in corpus (15)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Matrix Completion has No Spurious Local Minimum
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Exponential Family Matrix Completion under Structural Constraints
• Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
• Completing Any Low-rank Matrix, Provably
• 1-Bit Matrix Completion under Exact Low-Rank Constraint

Cited by in corpus (3)

• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements