Sparse Subspace Clustering with Missing Entries

We consider the problem of clustering incom-plete data drawn from a union of subspaces. Classical subspace clustering methods are not ap-plicable to this problem because the data are in-complete, while classical low-rank matrix com-pletion methods may not be applicable because data in multiple subspaces may not be low rank. This paper proposes and evaluates two new ap-proaches for subspace clustering and completion. The first one generalizes the sparse subspace clustering algorithm so that it can obtain a sparse representation of the data using only the observed entries. The second one estimates a suitable ker-nel matrix by assuming a random model for the missing entries and obtains the sparse represen-tation from this kernel. Experiments on synthetic and real data show the advantages and disadvan-tages of the proposed methods, which all outper-form the natural approach (low-rank matrix com-pletion followed by sparse subspace clustering) when the data matrix is high-rank or the percent-age of missing entries is large. 1