Subspace clustering by (k, k)-sparse matrix factorization

Abstract

High-dimensional data often lie in low-dimensional subspaces instead of the whole space. Subspace clustering is a problem to analyze data that are from multiple low-dimensional subspaces and cluster them into the corresponding subspaces. In this work, we propose a (k, k)-sparse matrix factorization method for subspace clustering. In this method, data itself is considered as the “dictionary”, and each data point is represented as a linear combination of the basis of its cluster in the dictionary. Thus, the coefficient matrix is lowrank and sparse. With an appropriate permutation, it is also blockwise with each block corresponding to a cluster. With an assumption that each block is no more than k-by-k in matrix recovery, we seek a low-rank and (k, k)-sparse coefficient matrix, which will be used for the construction of affinity matrix in spectral clustering. The advantage of our proposed method is that we recover a coefficient matrix with (k, k)-sparse and low-rank simultaneously, which is better fit for subspace clustering. Numerical results illustrate the effectiveness that it is better than SSC and LRR in real-world classification problems such as face clustering and motion segmentation.