Fast subspace segmentation via Random Sample Probing

Subspace segmentation is to group a given set of n data points into multiple clusters, with each cluster corresponding to a subspace. Prevalent methods such as Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR) are effective in terms of segmentation accuracy, but computationally inefficient while applying to gigantic datasets where n is very large as they possess a complexity of O(n3). In this paper, we propose an iterative method called Random Sample Probing (RANSP). In each iteration, RANSP finds the members of one subspace by randomly choosing a data point (called “seed”) at first, and then using Ridge Regression (RR) to retrieve the other points that belong to the same subspace as the seed. Such a procedure is repeated until all points have been classified. RANSP has a computational complexity of O(n) and can therefore handle large-scale datasets. Experiments on synthetic and real datasets confirm the effectiveness and efficiency of RANSP.