Universal Matrix Completion

Abstract

The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so, these methods make assumptions that can be quite restrictive in practice. More specifically, the methods assume that: a) the observed indices are sampled uniformly at random, and b) for every new matrix, the observed indices are sampled afresh. In this work, we address these issues by providing a universal recovery guarantee for matrix completion that works for a variety of sampling schemes. In particular, we show that if the set of sampled indices come from the edges of a bipartite graph with large spectral gap (i.e. gap between the first and the second singular value), then the nuclear norm minimization based method exactly recovers all low-rank matrices that satisfy certain incoherence properties. Moreover, we also show that under certain stricter incoherence conditions, $O(n{r}^2)$ uniformly sampled entries are enough to recover any rank-$r$ $n\times n$ matrix, in contrast to the $O(nr\log n)$ sample complexity required by other matrix completion algorithms as well as existing analyses of the nuclear norm method.

22 pages, 2 figures

References in corpus (2)

• Graph spectra and the detectability of community structure in networks
• Low-rank Matrix Completion using Alternating Minimization

Cited by in corpus (18)

• Optimum Design for Coexistence Between Matrix Completion Based MIMO Radars and a MIMO Communication System
• Non-convex Optimization for Machine Learning
• Guaranteed Matrix Completion via Non-convex Factorization
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• CUR Algorithm for Partially Observed Matrices
• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Network cross-validation by edge sampling
• 1-Bit Matrix Completion under Exact Low-Rank Constraint
• Recovery guarantee of weighted low-rank approximation via alternating minimization
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Learning from Comparisons and Choices
• Matrix Completion from $O(n)$ Samples in Linear Time
• Active Feature Acquisition with Supervised Matrix Completion
• HOSVD-Based Algorithm for Weighted Tensor Completion
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
• Efficient Map Prediction via Low-Rank Matrix Completion