A Structured Sparse Plus Structured Low Rank Framework for Subspace Clustering and Completion
Recent advances in a low rank matrix completion have enabled the exact recovery of incomplete data drawn from a low dimensional subspace of a high dimensional observation space. However, in many applications, the data are drawn from multiple low dimensional subspaces without knowing which point belongs to which subspace. In such cases, using a single low dimensional subspace to complete the data may lead to erroneous results, because the complete data matrix need not be low rank. In this paper, we propose a structured sparse plus structured low rank (S3LR) optimization framework for clustering and completing data drawn from a union of low dimensional subspaces. The proposed S3LR framework exploits the fact that each point in a union of subspaces can be expressed as a sparse linear combination of all other points and that the matrix of the points within each subspace is low rank. This framework leads to a nonconvex optimization problem, which we solve efficiently by using a combination of a linearized alternating direction method of multipliers and spectral clustering. In addition, we discuss the conditions that guarantee the exact matrix completion in a union of subspaces. Experiments on synthetic data, motion segmentation data, and cancer gene data validate the effectiveness of the proposed approach.
IEEE Transactions on Signal Processing