A Multi-criteria Approach for Fast and Outlier-aware Representative Selection from Manifolds
This addresses the challenge of efficient and robust representative selection for data analysis, though it appears incremental as it builds on existing selection approaches with multi-criteria enhancements.
The paper tackles the problem of selecting informative exemplars from large datasets with non-linear structures by introducing MOSAIC, a method that maximizes representation power, ensures diversity, and detects outliers, achieving substantial speedups and demonstrating superiority over state-of-the-art algorithms in experiments.
The problem of representative selection amounts to sampling few informative exemplars from large datasets. This paper presents MOSAIC, a novel representative selection approach from high-dimensional data that may exhibit non-linear structures. Resting upon a novel quadratic formulation, Our method advances a multi-criteria selection approach that maximizes the global representation power of the sampled subset, ensures diversity, and rejects disruptive information by effectively detecting outliers. Through theoretical analyses we characterize the obtained sketch and reveal that the sampled representatives maximize a well-defined notion of data coverage in a transformed space. In addition, we present a highly scalable randomized implementation of the proposed algorithm shown to bring about substantial speedups. MOSAIC's superiority in achieving the desired characteristics of a representative subset all at once while exhibiting remarkable robustness to various outlier types is demonstrated via extensive experiments conducted on both real and synthetic data with comparisons to state-of-the-art algorithms.