Research Area:  Machine Learning

Abstract:

In this paper, a novel low-rank structural model is proposed for segmenting data drawn from a high-dimensional space. Our method is based on the fact that all groups clustered from a high-dimensional dataset are distributed in multiple low-rank subspaces. In general, it’s a very difficult task to find the low-rank structures hidden in data. Different from the classical sparse subspace clustering (SSC) and low-rank representation (LRR) which all take two steps including building the affinity matrix and spectral clustering, we introduce a new rank constraint into our model. This constraint allows our model to learn a subspace indicator which can capture different clusters directly from the data without any postprocessing. To further approximate the rank constraint, a piecewise function is utilized as the relaxing item for the proposed model. Besides, under the subspace indicator constraints, the integer programming problem is avoided, which makes our algorithm more efficient and scalable. In addition, we prove the convergence of the proposed algorithm in theory and further discuss the general case in which subspaces don’t pass through the origin. Experiment results on both synthetic and real-world datasets demonstrate that our algorithm significantly outperforms the state-of-the-art methods.

Keywords:  
segmenting data
dimensional space
low-rank subspace
affinity matrix
postprocessing

Author(s) Name:  Feiping Nie, Wei Chang, Zhanxuan Hu, Xuelong Li

Publisher name:  IEEE

DOI:  10.1109/TKDE.2020.2995896

Volume Information:  Volume 34

Paper Link: https://ieeexplore.ieee.org/abstract/document/9097350