Greedy Feature Selection for Subspace Clustering
  Unions of subspaces provide a powerful generalization to linear subspace
models for collections of high-dimensional data. To learn a union of subspaces
from a collection of data, sets of signals in the collection that belong to the
same subspace must be identified in order to obtain accurate estimates of the
subspace structures present in the data. Recently, sparse recovery methods have
been shown to provide a provable and robust strategy for exact feature
selection (EFS)--recovering subsets of points from the ensemble that live in
the same subspace. In parallel with recent studies of EFS with L1-minimization,
in this paper, we develop sufficient conditions for EFS with a greedy method
for sparse signal recovery known as orthogonal matching pursuit (OMP).
Following our analysis, we provide an empirical study of feature selection
strategies for signals living on unions of subspaces and characterize the gap
between sparse recovery methods and nearest neighbor (NN)-based approaches. In
particular, we demonstrate that sparse recovery methods provide significant
advantages over NN methods and the gap between the two approaches is
particularly pronounced when the sampling of subspaces in the dataset is
sparse. Our results suggest that OMP may be employed to reliably recover exact
feature sets in a number of regimes where NN approaches fail to reveal the
subspace membership of points in the ensemble.
