PROJECT TITLE :

A Multi-criteria Approach for Fast and Robust Representative Selection from Manifolds

ABSTRACT:

The problem of representative selection can be summed up as the challenge of selecting a small number of informative exemplars from a large dataset. The currently available methods for selecting data frequently fall short when it comes to simultaneously handling non-linear data structures, sampling concise and non-redundant subsets, rejecting outliers, and producing results that can be interpreted. In this paper, a novel representative selection approach for drawing descriptive sketches of arbitrary manifold structures is presented. The approach is given the name MOSAIC. MOSAIC promotes a multi-criteria selection approach that, by resting on a novel quadratic formulation, maximizes the global representation power of the sampled subset, ensures the novelty of the samples by minimizing redundancy, and rejects disruptive information by effectively detecting outliers. All of these goals can be accomplished simultaneously. Theoretical analyses shed light on the geometrical characterization of the obtained sketch and reveal that the sampled representatives maximize a well-defined notion of data coverage in a transformed space. This was discovered as a result of a comparison between the original space and the transformed space. In addition to this, we present a highly scalable and random implementation of the proposed algorithm that has been demonstrated to result in significant speedups. Extensive experiments performed on both real and synthetic data with comparisons to state-of-the-art algorithms demonstrate that MOSAIC is superior in achieving the desired characteristics of a representative subset all at once while exhibiting remarkable robustness to various types of outliers. These experiments were conducted in order to demonstrate MOSAIC's superiority.