  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.
