  Subspace clustering is the unsupervised grouping of points lying near a union
of low-dimensional linear subspaces. Algorithms based directly on geometric
properties of such data tend to either provide poor empirical performance, lack
theoretical guarantees, or depend heavily on their initialization. We present a
novel geometric approach to the subspace clustering problem that leverages
ensembles of the K-subspaces (KSS) algorithm via the evidence accumulation
clustering framework. Our algorithm, referred to as ensemble K-subspaces
(EKSS), forms a co-association matrix whose (i,j)th entry is the number of
times points i and j are clustered together by several runs of KSS with random
initializations. We prove general recovery guarantees for any algorithm that
forms an affinity matrix with entries close to a monotonic transformation of
pairwise absolute inner products. We then show that a specific instance of EKSS
results in an affinity matrix with entries of this form, and hence our proposed
algorithm can provably recover subspaces under similar conditions to
state-of-the-art algorithms. The finding is, to the best of our knowledge, the
first recovery guarantee for evidence accumulation clustering and for KSS
variants. We show on synthetic data that our method performs well in the
traditionally challenging settings of subspaces with large intersection,
subspaces with small principal angles, and noisy data. Finally, we evaluate our
algorithm on six common benchmark datasets and show that unlike existing
methods, EKSS achieves excellent empirical performance when there are both a
small and large number of points per subspace.
