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

2016/10/17 by Lingxiao Wang, Xiao Zhang, Wang, Lingxiao +3 · 12 citations
Computer Science · Engineering · Mathematics · #Advanced Image Processing Techniques #Direction-of-Arrival Estimation Techniques #Sparse and Compressive Sensing Techniques #stat.ML

paper · pdf · doi:10.48550/arxiv.1610.05275

33 pages, 3 figures

arxiv created 2016/10/17 · arxiv updated 2016/10/18

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.

Cited by

• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• High-dimensional low-rank matrix regression with unknown latent structures
• Robust PCA by Manifold Optimization
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• A Scalable Factorization Approach for High-Order Structured Tensor Recovery
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ℓ_2,∞ Regularization
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• A Deterministic Theory for Exact Non-Convex Phase Retrieval

Related

• Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Nonconvex Matrix Factorization from Rank-One Measurements
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle