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.

Automated summary

This article revisited the data reconstruction problem in spectral clustering-based algorithms and proposed the concept of "relation reconstruction." By introducing the idea of neighborhood relation, a new method called sparse relation representation (SRR) was developed for subspace clustering, with a further extension known as structured sparse relation representation (SSRR) incorporating local structure information. The proposed optimization algorithm was analyzed for computational burden and convergence, with experiments demonstrating the superior performance of SRR and SSRR on various databases.