Representative Selection on a Hypersphere

Finding representative examples is important for pattern discovery and data analytics. In this letter, we propose a novel formulation for representative selection via center reconstruction on a hypersphere, which makes the selection not affect the center information of given data, thus, the overall data distribution can also be easily maintained by those selected representatives. We adopt the proximal gradient strategy and the fast iterative shrinkage-thresholding algorithm to solve the problem. Compared with most existing methods with cubic time complexity in the number of samples, our method is considerably more efficient, with time complexity reduced to being quadratic. Our formulation has only one parameter. We analyze the behavior of this parameter and analyze its bound theoretically. Experiments on synthesis and real-world datasets validate the effectiveness and efficiency of our method and demonstrate its robustness to noise compared with the state-of-the-art methods.