Completing Any Low-rank Matrix, Provably

Abstract

Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constraint---known as {\em incoherence}---on its row and column spaces. In these cases, the subset of elements is sampled uniformly at random. In this paper, we show that {\em any} rank-$r$ $n$-by-$n$ matrix can be exactly recovered from as few as $O(nr{\log }^{2}n)$ randomly chosen elements, provided this random choice is made according to a {\em specific biased distribution}: the probability of any element being sampled should be proportional to the sum of the leverage scores of the corresponding row, and column. Perhaps equally important, we show that this specific form of sampling is nearly necessary, in a natural precise sense; this implies that other perhaps more intuitive sampling schemes fail. We further establish three ways to use the above result for the setting when leverage scores are not known \textit{a priori}: (a) a sampling strategy for the case when only one of the row or column spaces are incoherent, (b) a two-phase sampling procedure for general matrices that first samples to estimate leverage scores followed by sampling for exact recovery, and (c) an analysis showing the advantages of weighted nuclear/trace-norm minimization over the vanilla un-weighted formulation for the case of non-uniform sampling.

Added a new necessary condition(Theorem 6) and a result on completion of row coherent matrices(Corollary 4). Partial results appeared in the International Conference on Machine Learning 2014, under the title 'Coherent Matrix Completion'. (34 pages, 4 figures)

References in corpus (5)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Incoherence-Optimal Matrix Completion
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
• Low-rank Matrix Completion using Alternating Minimization

Cited by in corpus (11)

• Incoherence-Optimal Matrix Completion
• Compressed sensing for longitudinal MRI: An adaptive-weighted approach
• Universal Matrix Completion
• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
• Relax, no need to round: integrality of clustering formulations
• Identifying Influential Entries in a Matrix
• Online Optimization for Large-Scale Max-Norm Regularization
• Log-Normal Matrix Completion for Large Scale Link Prediction
• Learning Parameters for Weighted Matrix Completion via Empirical Estimation