Sparse Subspace Clustering Based On Subspace Pursuit Algorithm

Sparse subspace clustering is a kind of clustering framework based on spectral clustering,which is an effective way of clustering high-dimensional data.High-dimensional data is usually distributed in the union of low-dimensional subspaces.Therefore,they can be represented sparsely under appropriate dictionaries.The sparse representation coefficients can be used to construct similarity matrix.Finally,we can get the clustering results by spectral clustering.How to construct the appropriate similarity matrix is a critical step of sparse subspace clustering.This thesis deal with sparse subspace clustering based on greedy algorithm and the main work we have done is as follow:(1)We introduced subspace pursuit algorithm to construct the similarity matrix and gave the sparse subspace clustering theory framework based on subspace pursuit algorithm.Secondly,we proved the sufficient condition of the algorithm to ensure feature selection and feature reselection.Finally,Simulation experiments proved that the atoms selected by subspace pursuit algorithm are more representative than other algorithms.Moreover,its exact feature selection rate is also higher but clustering error have also been preserved or even lower than that of the original ones.(2)We analyzed the error between the sparse solution obtained by subspace pursuit algorithm and the optimal sparse solution of the high-dimensional data.In addition,we proved the accuracy of the sparse solution obtained by the subspace pursuit algorithm.(3)We gave a sparse subspace clustering theory framework based on generalized orthogonal matching pursuit algorithm.Simulation experiments show that performance of the running time has been greatly improved and clustering error have been preserved compared to other greedy algorithms.