Dissimilarity-Based Sparse Subset Selection.

Area of Science:

• Data Science
• Computer Vision
• Machine Learning

Background:

• Selecting informative subsets from large datasets is crucial for various computational tasks.
• Existing methods face challenges with large-scale, complex data structures.

Purpose of the Study:

• To develop an efficient algorithm for finding representative subsets from large data collections.
• To address challenges in data representation and clustering across diverse domains.

Main Methods:

• Formulated the problem as a row-sparsity regularized trace minimization.
• Employed convex relaxation for an NP-hard optimization problem.
• Utilized the Alternating Direction Method of Multipliers (ADMM) for efficient implementation.

Main Results:

• The algorithm identifies representatives and assigns target set elements, revealing underlying data clusters.
• Demonstrated effective handling of outliers and arbitrary dissimilarities (asymmetric, non-triangle inequality).
• Achieved state-of-the-art performance in scene categorization and time-series modeling.

Conclusions:

• The proposed method provides an effective and scalable solution for representative subset selection.
• The ADMM implementation enables parallelization, significantly reducing computational time.
• The framework advances data analysis in computer vision, recommender systems, and bioinformatics.