See all by looking at a few: Sparse modeling for finding representative objects

E. Elhamifar, Guillermo Sapiro, René Vidal

2012 · 411 citations · 41 references

Concepts

TL;DR

The paper addresses selecting a small subset of data points that represent the entire dataset without assuming low‑rank or cluster structure. The authors aim to extend their representative selection framework to detect and reject outliers and to efficiently handle new observations and large datasets. They formulate representative selection as a sparse multiple‑measurement‑vector problem, solve a convex optimization that selects representatives from the data matrix, analyze the geometry linking representatives to convex‑hull vertices, and illustrate the framework on video summarization and image classification. The method automatically selects representatives from each low‑rank model and can detect and reject outliers while handling new observations and large datasets.

Abstract

We consider the problem of finding a few representatives for a dataset, i.e., a subset of data points that efficiently describes the entire dataset. We assume that each data point can be expressed as a linear combination of the representatives and formulate the problem of finding the representatives as a sparse multiple measurement vector problem. In our formulation, both the dictionary and the measurements are given by the data matrix, and the unknown sparse codes select the representatives via convex optimization. In general, we do not assume that the data are low-rank or distributed around cluster centers. When the data do come from a collection of low-rank models, we show that our method automatically selects a few representatives from each low-rank model. We also analyze the geometry of the representatives and discuss their relationship to the vertices of the convex hull of the data. We show that our framework can be extended to detect and reject outliers in datasets, and to efficiently deal with new observations and large datasets. The proposed framework and theoretical foundations are illustrated with examples in video summarization and image classification using representatives.

References

41