Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization

Abstract

This paper studies noisy low-rank matrix completion: given partial and noisy entries of a large low-rank matrix, the goal is to estimate the underlying matrix faithfully and efficiently. Arguably one of the most popular paradigms to tackle this problem is convex relaxation, which achieves remarkable efficacy in practice. However, the theoretical support of this approach is still far from optimal in the noisy setting, falling short of explaining its empirical success. We make progress towards demystifying the practical efficacy of convex relaxation vis-à-vis random noise. When the rank and the condition number of the unknown matrix are bounded by a constant, we demonstrate that the convex programming approach achieves near-optimal estimation errors --- in terms of the Euclidean loss, the entrywise loss, and the spectral norm loss --- for a wide range of noise levels. All of this is enabled by bridging convex relaxation with the nonconvex Burer-Monteiro approach, a seemingly distinct algorithmic paradigm that is provably robust against noise. More specifically, we show that an approximate critical point of the nonconvex formulation serves as an extremely tight approximation of the convex solution, thus allowing us to transfer the desired statistical guarantees of the nonconvex approach to its convex counterpart.

References in corpus (19)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Self-Calibration and Biconvex Compressive Sensing
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Incoherence-Optimal Matrix Completion
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• "Pre-conditioning" for feature selection and regression in high-dimensional problems
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Matrix Completion via Max-Norm Constrained Optimization
• Poisson Matrix Recovery and Completion
• Factor models and variable selection in high-dimensional regression analysis
• Matrix completion with deterministic pattern - a geometric perspective
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization

Cited by in corpus (11)

• Inference and Uncertainty Quantification for Noisy Matrix Completion
• A Selective Overview of Deep Learning
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Learning Treatment Effects in Panels with General Intervention Patterns
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules
• NoisyCUR: An algorithm for two-cost budgeted matrix completion