High-Rank Matrix Completion and Subspace Clustering with Missing Data

Abstract

This paper considers the problem of completing a matrix with many missing entries under the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. This generalizes the standard low-rank matrix completion problem to situations in which the matrix rank can be quite high or even full rank. Since the columns belong to a union of subspaces, this problem may also be viewed as a missing-data version of the subspace clustering problem. Let X be an n x N matrix whose (complete) columns lie in a union of at most k subspaces, each of rank <= r < n, and assume N >> kn. The main result of the paper shows that under mild assumptions each column of X can be perfectly recovered with high probability from an incomplete version so long as at least CrNlog^2(n) entries of X are observed uniformly at random, with C>1 a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces. The result is illustrated with numerical experiments and an application to Internet distance matrix completion and topology identification.

Cited by in corpus (14)

• Robust subspace clustering
• Guess Who Rated This Movie: Identifying Users Through Subspace Clustering
• Noisy Matrix Completion under Sparse Factor Models
• CUR Algorithm for Partially Observed Matrices
• Guess Who Rated This Movie: Identifying Users Through Subspace Clustering
• Active Feature Acquisition with Supervised Matrix Completion
• Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• Recommendation via matrix completion using Kolmogorov complexity
• On deterministic conditions for subspace clustering under missing data
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Ranking Recovery from Limited Comparisons using Low-Rank Matrix Completion
• To lie or not to lie in a subspace
• Tensor Matched Subspace Detection