Optimal tuning-free convex relaxation for noisy matrix completion

Abstract

This paper is concerned with noisy matrix completion--the problem of recovering a low-rank matrix from partial and noisy entries. Under uniform sampling and incoherence assumptions, we prove that a tuning-free square-root matrix completion estimator (square-root MC) achieves optimal statistical performance for solving the noisy matrix completion problem. Similar to the square-root Lasso estimator in high-dimensional linear regression, square-root MC does not rely on the knowledge of the size of the noise. While solving square-root MC is a convex program, our statistical analysis of square-root MC hinges on its intimate connections to a nonconvex rank-constrained estimator.

arXiv commentAccepted to IEEE Transactions on Information Theory

References in corpus (18)

• A Simpler Approach to Matrix Completion
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• Recovering low-rank matrices from few coefficients in any basis
• Matrix Completion Methods for Causal Panel Data Models
• 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
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Matrix Completion from Noisy Entries
• Incoherence-Optimal Matrix Completion
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Noisy low-rank matrix completion with general sampling distribution
• Spectral Methods for Data Science: A Statistical Perspective
• Near-optimal bounds for phase synchronization
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Inference for Heteroskedastic PCA with Missing Data
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
• Robust Matrix Completion with Heavy-tailed Noise