# Dissimilarity-based Sparse Subset Selection

arXiv: https://arxiv.org/abs/1407.6810 · HTML: https://mlsanity.com/paper/1407.6810/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2014.

## Built on by (most cited first, 19 of 19)

- [Align and Attend: Multimodal Summarization with Dual Contrastive Losses](https://mlsanity.com/paper/2303.07284/) (2023)
- [Convolutional Neural Opacity Radiance Fields](https://mlsanity.com/paper/2104.01772/) (2021)
- [Diagnosing Ensemble Few-Shot Classifiers](https://mlsanity.com/paper/2206.04372/) (2022)
- [Batch Active Learning of Reward Functions from Human Preferences](https://mlsanity.com/paper/2402.15757/) (2024)
- [Learning Preferences for Interactive Autonomy](https://mlsanity.com/paper/2210.10899/) (2022)
- [A Comprehensive Review of the Video-to-Text Problem](https://mlsanity.com/paper/2103.14785/) (2021)
- [A Survey of Dataset Refinement for Problems in Computer Vision Datasets](https://mlsanity.com/paper/2210.11717/) (2022)
- [OpenGCD: Assisting Open World Recognition with Generalized Category Discovery](https://mlsanity.com/paper/2308.06926/) (2023)
- [Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection](https://mlsanity.com/paper/2106.06983/) (2021)
- [Efficient Cross-Modal Video Retrieval with Meta-Optimized Frames](https://mlsanity.com/paper/2210.08452/) (2022)
- [Dynamical Deep Generative Latent Modeling of 3D Skeletal Motion](https://mlsanity.com/paper/2106.10393/) (2021)
- [Early Exit and Multi Stage Knowledge Distillation in VLMs for Video Summarization](https://mlsanity.com/paper/2504.21831/) (2025)
- [Interactive Hybrid Rice Breeding with Parametric Dual Projection](https://mlsanity.com/paper/2507.11848/) (2025)
- [Cluster Representatives Selection in Non-Metric Spaces for Nearest Prototype Classification](https://mlsanity.com/paper/2107.01345/) (2021)
- [Automated Machine Learning: A Case Study on Non-Intrusive Appliance Load Monitoring](https://mlsanity.com/paper/2203.02927/) (2022)
- [Transformer meets wcDTW to improve real-time battery bids: A new approach to scenario selection](https://mlsanity.com/paper/2404.01646/) (2024)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [Prototype Selection Using Topological Data Analysis](https://mlsanity.com/paper/2511.04873/) (2025)
- [Silence and Noise: Resolving Suppression and Overvaluation in Multimodal Entity Alignment](https://mlsanity.com/paper/2610.16106/) (2026)

## Abstract (arXiv)

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.