8. Sparse and Low-Rank Methods

The previous chapter studies a family of subspace clustering methods based on spectral clustering. In particular, we have studied both local and global methods for defining a subspace clustering affinity, and have noticed that we seem to be facing an important dilemma. On the one hand, local methods compute an affinity that depends only on the data points in a local neighborhood of each data point. Local methods can be rather efficient and somewhat robust to outliers, but they cannot deal well with intersecting subspaces. On the other hand, global methods utilize geometric information derived from the entire data set (or a large portion of it) to construct the affinity. Global methods might be immune to local mistakes, but they come with a big price: their computational complexity is often exponential in the dimension and number of subspaces. Moreover, none of the methods comes with a theoretical analysis that guarantees the correctness of clustering. Therefore, a natural question that arises is whether we can construct a subspace clustering affinity that utilizes global geometric relationships among all the data points, is computationally tractable when the dimension and number of subspaces are large, and is guaranteed to provide the correct clustering under certain conditions.