The problem of clustering noisy and incompletely observed high-dimensional data points into a union of low-dimensional subspaces and a set of outliers is considered. The number of subspaces, their dimensions, and their orientations are assumed unknown. We propose a simple low-complexity clustering algorithm based on thresholding correlations between the data points followed by spectral clustering. A statistical performance analysis shows that this algorithm succeeds even when the subspaces intersect and when the dimensions of the subspaces scale (up to a log-factor) linearly in the ambient dimension. Moreover, we prove that the algorithm succeeds even when the data points are incompletely observed with the number of missing observations scaling (up to a log-factor) linearly in the ambient dimension. The algorithm is shown to be robust in the presence of structured (i.e., sparse) and of unstructured additive noise. Our results reveal an explicit tradeoff between the affinity of the subspaces and the tolerable noise level. Finally, we propose a simple scheme that provably detects outliers, and present numerical results on real and synthetic data.

本研究提出了一种简单、低复杂度的子空间聚类算法，通过阈值化数据点之间的相关性来构建邻接矩阵，并且对噪声和异常值具有鲁棒性，可用于处理高维、噪声丰富的数据点。

阈值法稳健子空间聚类