Incoherence-Optimal Matrix Completion

Abstract

This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence parameter (as well as to the rank $r$ and the matrix dimension $n$ up to a log factor). As a consequence, we improve the sample complexity of recovering a semidefinite matrix from $O(n{r}^2{\log }^{2}n)$ to $O(nr{\log }^{2}n)$, and the highest allowable rank from $\Theta (\sqrt{n}/\log n)$ to $\Theta (n/{\log }^{2}n)$. The key step in proof is to obtain new bounds on the ${\ell }_{\infty ,2}$-norm, defined as the maximum of the row and column norms of a matrix. To illustrate the applicability of our techniques, we discuss extensions to SVD projection, structured matrix completion and semi-supervised clustering, for which we provide order-wise improvements over existing results. Finally, we turn to the closely-related problem of low-rank-plus-sparse matrix decomposition. We show that the joint incoherence condition is unavoidable here for polynomial-time algorithms conditioned on the Planted Clique conjecture. This means it is intractable in general to separate a rank-$\omega (\sqrt{n})$ positive semidefinite matrix and a sparse matrix. Interestingly, our results show that the standard and joint incoherence conditions are associated respectively with the information (statistical) and computational aspects of the matrix decomposition problem.

Fixed a minor error in Theorem 3 for matrix decomposition. To appear in the IEEE Transactions on Information Theory

References in corpus (5)

• Incoherence-Optimal Matrix Completion
• Computational barriers in minimax submatrix detection
• Spectral Compressed Sensing via Structured Matrix Completion
• Completing Any Low-rank Matrix, Provably
• Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs

Cited by in corpus (64)

• An overview of low-rank matrix recovery from incomplete observations
• 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
• Incoherence-Optimal Matrix Completion
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Non-convex Robust PCA
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Computational Barriers to Estimation from Low-Degree Polynomials
• Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm
• Recovery of Future Data via Convolution Nuclear Norm Minimization
• Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization
• On the Power of Adaptivity in Matrix Completion and Approximation
• Matrix completion with deterministic pattern - a geometric perspective
• Matrix Completion with Deterministic Sampling: Theories and Methods
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Completing Any Low-rank Matrix, Provably
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• An ${\ell }_{\infty }$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• Exact Tensor Completion from Sparsely Corrupted Observations via Convex Optimization
• Exact tensor completion using t-SVD
• Universality of Computational Lower Bounds for Submatrix Detection
• Matrix Completion from $O(n)$ Samples in Linear Time
• Robust Tensor Completion Using Transformed Tensor SVD
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Rapid characterisation of linear-optical networks via PhaseLift
• Fast and Accurate Tensor Completion with Total Variation Regularized Tensor Trains
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Exact Recovery of Tensor Robust Principal Component Analysis under Linear Transforms
• Optimal link prediction with matrix logistic regression
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Matrix Completion and Related Problems via Strong Duality
• Optimal tuning-free convex relaxation for noisy matrix completion
• Informative core identification in complex networks
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• What to Expect When You Are Expecting on the Grassmannian
• Streaming Principal Component Analysis From Incomplete Data
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• On the simplicity and conditioning of low rank semidefinite programs
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Efficient Map Prediction via Low-Rank Matrix Completion
• Multi-Tensor Network Representation for High-Order Tensor Completion
• Detection of Planted Solutions for Flat Satisfiability Problems
• Resource Allocation for Statistical Estimation
• MiSC: Mixed Strategies Crowdsourcing
• Online Tensor Inference