Improving Sparse Subspace Clustering Using Subsampled Randomized Hadamard Transform
Sabra Hechmi, Ezzeddine Zagrouba · 2015
In the era of high dimensional data, trying to lind clusters is a challenging issue. In this context subspace clustering has showed surprising results. The tenet of this technique is to uncover groups of data that exist in multiple underlying subspaces. Recently, several methods have been proposed that arise in many research fields, including signal/image processing, system identification and computer vision. In the presented work, we are interested to an algorithm, namely Sparse Subspace clustering (SSC). This algorithm has showed encouraging results to cluster high dimensional data. In spite, the meaningful drawback of SSC is its computational complexity due to the solving of the sparse optimization problem. In this study, we propose a new method which can deal with large scale issues. The key idea is what we call Sub-sampled Randomized Hadamard Transform (SRHT) that approximates the amount of data XTX (X is the data matrix), used to compute the sparse solution. The performance of the proposed method is tested on real datasets, especially `Extended Yale B' database for face clustering and `Hopkins 155' for motion segmentation problem.