Efficient sparse subspace clustering by nearest neighbour filtering

Subspace identification has been used extensively because its ability to detail the internal subspace structure of data, which can be used in a variety of applications such as dimension reduction, anomaly detection and so on. However, many advanced algorithms are limited on their applicability in large data sets due to large computation and memory requirements with respect to the number of input data points. To overcome this problem, we propose a simple method that screens out a large number of data points by using k nearest neighbours and subspace recovery is performed on reduced set. The proposed method is surprisingly simple with significant reduction to both memory and computations requirements, and yet possesses desirable probability lower bound for its success in the context of big data. Besides theoretical analysis, our experiments also show that our method exceeds theoretical expectations and outperforms existing similar algorithms.