Skip to main content

Dissimilarity-Based Sparse Subset Selection.

Publication ,  Journal Article
Elhamifar, E; Sapiro, G; Sastry, SS
Published in: IEEE transactions on pattern analysis and machine intelligence
November 2016

Finding an informative subset of a large collection of data points or models is at the center of many problems in computer vision, recommender systems, bio/health informatics as well as image and natural language processing. Given pairwise dissimilarities between the elements of a 'source set' and a 'target set,' we consider the problem of finding a subset of the source set, called representatives or exemplars, that can efficiently describe the target set. We formulate the problem as a row-sparsity regularized trace minimization problem. Since the proposed formulation is, in general, NP-hard, we consider a convex relaxation. The solution of our optimization finds representatives and the assignment of each element of the target set to each representative, hence, obtaining a clustering. We analyze the solution of our proposed optimization as a function of the regularization parameter. We show that when the two sets jointly partition into multiple groups, our algorithm finds representatives from all groups and reveals clustering of the sets. In addition, we show that the proposed framework can effectively deal with outliers. Our algorithm works with arbitrary dissimilarities, which can be asymmetric or violate the triangle inequality. To efficiently implement our algorithm, we consider an Alternating Direction Method of Multipliers (ADMM) framework, which results in quadratic complexity in the problem size. We show that the ADMM implementation allows to parallelize the algorithm, hence further reducing the computational time. Finally, by experiments on real-world datasets, we show that our proposed algorithm improves the state of the art on the two problems of scene categorization using representative images and time-series modeling and segmentation using representative models.

Duke Scholars

Published In

IEEE transactions on pattern analysis and machine intelligence

DOI

EISSN

1939-3539

ISSN

0162-8828

Publication Date

November 2016

Volume

38

Issue

11

Start / End Page

2182 / 2197

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 4611 Machine learning
  • 4603 Computer vision and multimedia computation
  • 0906 Electrical and Electronic Engineering
  • 0806 Information Systems
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Elhamifar, E., Sapiro, G., & Sastry, S. S. (2016). Dissimilarity-Based Sparse Subset Selection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(11), 2182–2197. https://doi.org/10.1109/tpami.2015.2511748
Elhamifar, Ehsan, Guillermo Sapiro, and S Shankar Sastry. “Dissimilarity-Based Sparse Subset Selection.IEEE Transactions on Pattern Analysis and Machine Intelligence 38, no. 11 (November 2016): 2182–97. https://doi.org/10.1109/tpami.2015.2511748.
Elhamifar E, Sapiro G, Sastry SS. Dissimilarity-Based Sparse Subset Selection. IEEE transactions on pattern analysis and machine intelligence. 2016 Nov;38(11):2182–97.
Elhamifar, Ehsan, et al. “Dissimilarity-Based Sparse Subset Selection.IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 11, Nov. 2016, pp. 2182–97. Epmc, doi:10.1109/tpami.2015.2511748.
Elhamifar E, Sapiro G, Sastry SS. Dissimilarity-Based Sparse Subset Selection. IEEE transactions on pattern analysis and machine intelligence. 2016 Nov;38(11):2182–2197.

Published In

IEEE transactions on pattern analysis and machine intelligence

DOI

EISSN

1939-3539

ISSN

0162-8828

Publication Date

November 2016

Volume

38

Issue

11

Start / End Page

2182 / 2197

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 4611 Machine learning
  • 4603 Computer vision and multimedia computation
  • 0906 Electrical and Electronic Engineering
  • 0806 Information Systems
  • 0801 Artificial Intelligence and Image Processing