Greedy Subspace Clustering
We consider the problem of subspace clustering: given points that lie on or near the union of many low-dimensional linear subspaces, recover the subspaces. To this end, one first identifies sets of points close to the same subspace and uses the sets to estimate the subspaces. As the geometric structure of the clusters (linear subspaces) forbids proper performance of general distance based approaches such as K-means, many model-specific methods have been proposed. In this paper, we provide new simple and efficient algorithms for this problem. Our statistical analysis shows that the algorithms are guaranteed exact (perfect) clustering performance under certain conditions on the number of points and the affinity between subspaces. These conditions are weaker than those considered in the standard statistical literature. Experimental results on synthetic data generated from the standard unions of subspaces model demonstrate our theory. We also show that our algorithm performs competitively against state-of-the-art algorithms on realworld applications such as motion segmentation and face clustering, with much simpler implementation and lower computational cost.
The paper considers the problem of subspace clustering where the goal is to jointly find the spaces and the subset of points belonging to each. As pointed out in the related work, this area has seen very interesting progress recently starting with the SSC algorithm Elhamifar and Vidal using l1 minimization.Most of these methods are done in two steps, first one finds a neighborhood matrix indicating which points belong in the same subspace, and then performing some sort of clustering to find the subspaces.Here the authors propose a greedy approach for both steps. To find the neighborhood of a point i, the point j closest to i is added first, followed by the point closest to the span of i and j etc. Once the neighborhood matrix is constructed, one can either perform spectral clustering or use another greedy procedure the authors describe to find the subspaces.Interestingly this procedure has very nice theoretical properties (analogous in some sense to how orthogonal matching pursuit often performs just as well as lasso under certain conditions). Compared to most methods which just prove the correctness of the first step (picking neighborhoods) here the authors prove the correctness of both steps (i.e. exact clustering). They allow the subspaces to intersect (controlled by some max affinity). Interestingly, they show that as the number of points grows a higher max affinity is allowed for their approach (as one would like). This is different from another greedy approach TSC.The experiments compare the authors approach to SSC (l1 minimization) and two greedy approaches GFS and TSC. The new approach performs better than the other greedy approaches while being comparable to SSC. (Of course being greedy it is much faster than SSC).Quality: Paper is thorough, authors provide a novel algorithm, theory and experiments.Clarity: I found the work to be very well written and easy to understand.Originality: Good, not incremental but also not revolutionarySignificance: Moderate, again not incremental, but also not revolutionary.