Self-Representation Based Unsupervised Exemplar Selection in a Union of Subspaces
This addresses dataset summarization and information extraction for applications where data are not clustered but lie in subspaces, offering an incremental improvement over classical methods like k-medoids.
The paper tackles the problem of selecting a small set of representatives from unlabeled data lying in a union of subspaces, proposing a new model that uses ℓ1 norm reconstruction and a farthest first search algorithm, which enables selection from each subspace and supports robust subspace clustering and classification.
Finding a small set of representatives from an unlabeled dataset is a core problem in a broad range of applications such as dataset summarization and information extraction. Classical exemplar selection methods such as $k$-medoids work under the assumption that the data points are close to a few cluster centroids, and cannot handle the case where data lie close to a union of subspaces. This paper proposes a new exemplar selection model that searches for a subset that best reconstructs all data points as measured by the $\ell_1$ norm of the representation coefficients. Geometrically, this subset best covers all the data points as measured by the Minkowski functional of the subset. To solve our model efficiently, we introduce a farthest first search algorithm that iteratively selects the worst represented point as an exemplar. When the dataset is drawn from a union of independent subspaces, our method is able to select sufficiently many representatives from each subspace. We further develop an exemplar based subspace clustering method that is robust to imbalanced data and efficient for large scale data. Moreover, we show that a classifier trained on the selected exemplars (when they are labeled) can correctly classify the rest of the data points.