Skip to main content

Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery

Publication ,  Journal Article
Elhamifar, E; Sapiro, G; Vidal, R
Published in: Advances in Neural Information Processing Systems
December 1, 2012

Given pairwise dissimilarities between data points, we consider the problem of finding a subset of data points, called representatives or exemplars, that can efficiently describe the data collection. We formulate the problem as a row-sparsity regularized trace minimization problem that can be solved efficiently using convex programming. The solution of the proposed optimization program finds the representatives and the probability that each data point is associated with each one of the representatives. We obtain the range of the regularization parameter for which the solution of the proposed optimization program changes from selecting one representative for all data points to selecting all data points as representatives. When data points are distributed around multiple clusters according to the dissimilarities, we show that the data points in each cluster select representatives only from that cluster. Unlike metric-based methods, our algorithm can be applied to dissimilarities that are asymmetric or violate the triangle inequality, i.e., it does not require that the pairwise dissimilarities come from a metric. We demonstrate the effectiveness of the proposed algorithm on synthetic data as well as real-world image and text data.

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

December 1, 2012

Volume

1

Start / End Page

19 / 27

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Elhamifar, E., Sapiro, G., & Vidal, R. (2012). Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery. Advances in Neural Information Processing Systems, 1, 19–27.
Elhamifar, E., G. Sapiro, and R. Vidal. “Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery.” Advances in Neural Information Processing Systems 1 (December 1, 2012): 19–27.
Elhamifar E, Sapiro G, Vidal R. Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery. Advances in Neural Information Processing Systems. 2012 Dec 1;1:19–27.
Elhamifar, E., et al. “Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery.” Advances in Neural Information Processing Systems, vol. 1, Dec. 2012, pp. 19–27.
Elhamifar E, Sapiro G, Vidal R. Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery. Advances in Neural Information Processing Systems. 2012 Dec 1;1:19–27.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

December 1, 2012

Volume

1

Start / End Page

19 / 27

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology