Subspace Clustering via Structured Sparse Relation Representation

Due to the corruptions or noises that existed in real-world data sets, the affinity graphs constructed by the classical spectral clustering-based subspace clustering algorithms may not be able to reveal the intrinsic subspace structures of data sets faithfully. In this article, we reconsidered the data reconstruction problem in spectral clustering-based algorithms and proposed the idea of ``relation reconstruction.'' We pointed out that a data sample could be represented by the neighborhood relation computed between its neighbors and itself. The neighborhood relation could indicate the true membership of its corresponding original data sample to the subspaces of a data set. We also claimed that a data sample's neighborhood relation could be reconstructed by the neighborhood relations of other data samples; then, we suggested a much different way to define affinity graphs consequently. Based on these propositions, a sparse relation representation (SRR) method was proposed for solving subspace clustering problems. Moreover, by introducing the local structure information of original data sets into SRR, an extension of SRR, namely structured sparse relation representation (SSRR) was presented. We gave an optimization algorithm for solving SRR and SSRR problems and analyzed its computation burden and convergence. Finally, plentiful experiments conducted on different types of databases showed the superiorities of SRR and SSRR.