Subspace Clustering using Ensembles of $K$-Subspaces

In modern computer vision problems such as facial recognition [1] and object tracking [2], researchers have found success applying the union of subspaces (UoS) model, in which data vectors lie near one of several subspaces. Under this model, the goal is to simultaneously identify these underlying subspaces and cluster the points according to their nearest subspace. Algorithms designed to solve this problem fall under the category of subspace clustering, a topic that has received a great deal of attention in recent years [3] due to its efficacy on real-world datasets such as the Extended Yale Face Database B [4] and the MNIST handwritten digit database [5]. One of the earliest approaches to solving the subspace clustering problem involves an iterative method in the spirit of K-means, known as K-subspaces (KSS) [6], [7], [8], which alternates between assigning points to clusters and estimating the subspace basis associated with each cluster. As this algorithm is only guaranteed to converge to a local minimum, in practice one runs many instances of the algorithm and chooses the final clustering as the one that produces the minimum cost. Although its empirical performance is limited, KSS continues to serve as a benchmark for subspace clustering algorithms, in part due to its computational efficiency and simplicity. Therefore, a deeper understanding of this method is an important contribution in the area of subspace clustering and a contribution of this paper. While the KSS cost function and alternating algorithm are perhaps the most natural approach for the subspace clustering problem, it is known that there is a set of initializations of nonzero measure from which the algorithm will convergence to a point other than the global minimizer.