An efficient matrix factorization based low-rank representation for subspace clustering

In recent years, robust subspace clustering is an important unsupervised clustering problem in machine learning and computer vision communities. The recently proposed spectral clustering based approach, called low-rank representation (LRR), yields an optimal solution for the case of independent subspaces and partially corrupted data. However, it has to be solved iteratively and involves singular value decomposition (SVD) at each iteration, and then suffers from high computation cost of multiple SVDs. In this paper, we propose an efficient matrix tri-factorization (MTF) approach with a positive semidefinite (PSD) constraint to approximate the original nuclear norm minimization (NNM) problem and mitigate the computation cost of performing SVDs. Specially, we introduce a matrix tri-factorization idea into the original low-rank representation framework, and then convert it into a small scale matrix nuclear norm minimization problem. Finally, we establish an alternating direction method (ADM) based algorithm to efficiently solve the proposed problem. Experimental results on a variety of synthetic and real-world data sets validate the efficiency, robustness and effectiveness of the proposed MTF approach comparing with the state-of-the-art algorithms.

► The matrix tri-factorization idea is introduced into the LRR-PSD framework.
► A small scale matrix NNM model with a PSD constraint is proposed.
► An iterative scheme under the ADM framework is developed.
► Promising experimental results on synthetic and real-world data are presented.