Sparse Subspace Clustering (SSC)ΒΆ
Sparse representations using overcomplete dictionaries have become a popular approach to solve a number of signal and image processing problems in last couple of decades [Ela10]. The dictionary [Tro04][RBE10] consists of a set of prototype signals called atoms which are representative of the particular class of signals of interest. Signals are then approximated by a sparse linear combination of these atoms (i.e. linear combinations of as few atoms as possible). A wide range of sparse recovery algorithms have been developed to decompose a given signal in terms of the atoms from the dictionary in order to obtain the sparsest possible representation [TW10]. Essentially, it is expected that the signals reside in low dimensional subspaces of the ambient signal space and a good dictionary contains well chosen elementary signals called atoms such that a small set of those atoms can span (or approximate) any of the low dimensional subspaces in the class of signals under consideration. Two typical approaches for computing the sparse representation (a.k.a. sparse coding or recovery) of a given signal in a given dictionary are convex relaxation (\(\ell_1\)-minimization) [CDS98][TRO04][CT05][DET06][Don06] and greedy pursuits [MZ93][PRK93][TG07][NT09].
Sparse Subspace Clustering (SSC), introduced in [EV09][EV13] is a method which utilizes the idea of sparse representations for solving the subspace clustering problem. It treats the dataset \(Y\) itself as an (unstructured) dictionary and suggests that a sparse representation of each point in a union of subspaces may be constructed from other data points in the dataset.
A dataset where each point can be expressed as a linear combination of other points in the dataset is said to satisfy self-expressiveness property. The self-expressive representation of a point \(y_s\) in \(Y\) is given by
where \(C = \begin{bmatrix}c_1, \dots, c_S \end{bmatrix} \in \RR^{S \times S}\) is the matrix of representation coefficients.
In general, the representation \(c_s\) for vector \(y_s\) need not be unique. Now, let \(y_s\) belong to \(k\)-th subspace \(\UUU_k\). Let \(Y^{-s}\) denote the dataset \(Y\) excluding the point \(y_s\) and \(Y_k^{-s}\) denote the set of points in \(Y_k\) excluding \(y_s\). If \(Y_k^{-s}\) spans the subspace \(\UUU_k\), then a representation of \(y_s\) can be constructed entirely from the points in \(Y_k^{-s}\). A representation is called subspace preserving if it consists of points within the same subspace. Now if \(c_i\) is a subspace preserving representation of \(y_i\) and \(y_j\) belongs to a different subspace, then \(c_{ij} = 0\). Thus, if \(C\) consists entirely of subspace preserving representations, then \(C_{ij} = 0\) whenever \(y_i\) and \(y_j\) belong to different subspaces.
Note that, \(C\) may not be symmetric. i.e. even if \(y_j\) participates in the representation of \(y_i\), \(y_i\) may not participate in the representation of \(y_j\) or the representation coefficients \(C_{ij}\) and \(C_{ji}\) may be different. But we can construct a symmetric matrix \(W = | C | + |C|^T\), where \(|C|\) denotes taking absolute value of each entry in \(C\). The matrix \(W\) can be used as an affinity matrix for the points from the union of subspaces such that the affinity of points from different subspaces is 0. \(W\) can be used to partition \(Y\) into \(Y_k\) via spectral clustering footnote{See here for a review of spectral clustering.} [VL07].
The remaining issue is constructing a subspace preserving representation \(C\) of \(Y\). This is where the sparse recovery methods developed in sparse representations literature come to our rescue. [EV09][EV13] initially proposed the use of using \(\ell_1\)-minimization by solving
They proved theoretically that, if the subspaces \(\{\UUU_k\}\) are independent, then \(\ell_1\) minimization can recover subspace preserving representations. They also showed that if the subspaces are disjoint, then under certain conditions, subspace preserving representations can be obtained.
Subsequently, [DSB13][YV15] showed that Orthogonal Matching Pursuit (OMP) [PRK93][TG07] can also be used for obtaining subspace preserving representations under appropriate conditions. We will call these two variants of SSC as SSC-\(\ell_1\) and SSC-OMP respectively. The essential SSC method is described below.
