Inference and Uncertainty Quantification for Noisy Matrix Completion

Abstract

Noisy matrix completion aims at estimating a low-rank matrix given only partial and corrupted entries. Despite substantial progress in designing efficient estimation algorithms, it remains largely unclear how to assess the uncertainty of the obtained estimates and how to perform statistical inference on the unknown matrix (e.g.~constructing a valid and short confidence interval for an unseen entry). This paper takes a step towards inference and uncertainty quantification for noisy matrix completion. We develop a simple procedure to compensate for the bias of the widely used convex and nonconvex estimators. The resulting de-biased estimators admit nearly precise non-asymptotic distributional characterizations, which in turn enable optimal construction of confidence intervals\,/\,regions for, say, the missing entries and the low-rank factors. Our inferential procedures do not rely on sample splitting, thus avoiding unnecessary loss of data efficiency. As a byproduct, we obtain a sharp characterization of the estimation accuracy of our de-biased estimators, which, to the best of our knowledge, are the first tractable algorithms that provably achieve full statistical efficiency (including the preconstant). The analysis herein is built upon the intimate link between convex and nonconvex optimization --- an appealing feature recently discovered by \cite{chen2019noisy}.

published at Proceedings of the National Academy of Sciences Nov 2019, 116 (46) 22931-22937

References in corpus (45)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• On asymptotically optimal confidence regions and tests for high-dimensional models
• A Simpler Approach to Matrix Completion
• Confidence Intervals and Hypothesis Testing for High-Dimensional Regression
• Recovering low-rank matrices from few coefficients in any basis
• A significance test for the lasso
• 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
• Estimation of high-dimensional low-rank matrices
• Guaranteed Matrix Completion via Non-convex Factorization
• Sparse PCA: Optimal rates and adaptive estimation
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• 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
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Confidence intervals for high-dimensional inverse covariance estimation
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Matrix Completion via Max-Norm Constrained Optimization
• Guaranteed Rank Minimization via Singular Value Projection
• Poisson Matrix Recovery and Completion
• Inference for High-Dimensional Sparse Econometric Models
• Factor models and variable selection in high-dimensional regression analysis
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• P-values for high-dimensional regression
• Optimal Estimation of Low Rank Density Matrices
• Matrix completion with deterministic pattern - a geometric perspective
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Composite optimization for robust blind deconvolution
• Calibrated Elastic Regularization in Matrix Completion
• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Inter-Subject Analysis: Inferring Sparse Interactions with Dense Intra-Graphs
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Information-Guided Sampling for Low-Rank Matrix Completion
• How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?

Cited by in corpus (35)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Recent Developments on Factor Models and its Applications in Econometric Learning
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• A Note on Exploratory Item Factor Analysis by Singular Value Decomposition
• Matrix Completion with Quantified Uncertainty through Low Rank Gaussian Copula
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Using Interpretable Machine Learning to Massively Increase the Number of Antibody-Virus Interactions Across Studies
• Supervised tensor decomposition with features on multiple modes
• Inference for Heteroskedastic PCA with Missing Data
• Concentration properties of fractional posterior in 1-bit matrix completion
• A Closed-Form Uncertainty Propagation in Non-Rigid Structure from Motion
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Optimal tuning-free convex relaxation for noisy matrix completion
• Learning Treatment Effects in Panels with General Intervention Patterns
• Tensor Completion with Nearly Linear Samples Given Weak Side Information
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Unfolding-Model-Based Visualization: Theory, Method and Applications
• AutoGFI: Streamlined Generalized Fiducial Inference for Modern Inference Problems in Models with Additive Errors
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• A Time-Varying Network for Cryptocurrencies
• Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information
• Time-Series Imputation with Wasserstein Interpolation for Optimal Look-Ahead-Bias and Variance Tradeoff
• Uncertainty Quantification for Hyperspectral Image Denoising Frameworks based on Low-rank Matrix Approximation
• Matrix Completion for Survey Data Prediction with Multivariate Missingness
• Online Tensor Inference
• Misclassification excess risk bounds for 1-bit matrix completion
• Bayesian Singular Value Regularization via a Cumulative Shrinkage Process
• Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise
• Learning Mixtures of Low-Rank Models
• Simulation comparisons between Bayesian and de-biased estimators in low-rank matrix completion