We consider a fundamental problem in unsupervised learning called : given a collection of @math points in @math , if many but not necessarily all of these points are contained in a @math -dimensional subspace @math can we find it? The points contained in @math are called inliers and the remaining points are outliers . This problem has received considerable attention in computer science and in statistics. Yet efficient algorithms from computer science are not robust to adversarial outliers, and the estimators from robust statistics are hard to compute in high dimensions. Are there algorithms for subspace recovery that are both robust to outliers and efficient? We give an algorithm that finds @math when it contains more than a @math fraction of the points. Hence, for say @math this estimator is both easy to compute and well-behaved when there are a constant fraction of outliers. We prove that it is Small Set Expansion hard to find @math when the fraction of errors is any larger, thus giving evidence that our estimator is an optimal compromise between efficiency and robustness. As it turns out, this basic problem has a surprising number of connections to other areas including small set expansion, matroid theory and functional analysis that we make use of here.
We note that much of the recent work from statistics and machine learning has focused on a setting where one posits a distributional model that generates both the inliers and outliers and the goal is to recover the subspace @math with high probability. For example, see the recent work of @cite_32 and @cite_37 and references therein. In principle, our work is not directly comparable to these models since our results are not contingent on any one distributional model. Yet in some of these probabilistic models (e.g. in @cite_37 ) the probability that a point is chosen from the subspace @math is larger than @math in which case Condition is satisfied with high probability and hence our algorithm succeeds in these cases too.
@cite_37 @cite_32
2165952088 2139054653
Section 1 of the paper contains a general discussion of robustness. In Section 2 the influence function of the Hampel-Rousseeuw least median of squares estimator is derived. Linearly invariant weak metrics are constructed in Section 3. It is shown in Section 4 that @math -estimators satisfy an exact Holder condition of order 1 2 at models with normal errors. In Section 5 the breakdown points of the Hampel-Krasker dispersion and regression functionals are shown to be 0. The exact breakdown point of the Krasker-Welsch dispersion functional is obtained as well as bounds for the corresponding regression functional. Section 6 contains the construction of a linearly equivariant, high breakdown and locally Lipschitz dispersion functional for any design distribution. In Section 7 it is shown that there is no inherent contradiction between efficiency and a high breakdown point. Section 8 contains a linearly equivariant, high breakdown regression functional which is Lipschitz continuous at models with normal errors. This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower dimensional planes. As is common in computer vision or unsupervised learning applications, we do not know in advance how many subspaces there are nor do we have any information about their dimensions. We develop a novel geometric analysis of an algorithm named sparse subspace clustering (SSC) [11], which signicantly broadens the range of problems where it is provably eective. For instance, we show that SSC can recover multiple subspaces, each of dimension comparable to the ambient dimension. We also prove that SSC can correctly cluster data points even when the subspaces of interest intersect. Further, we develop an extension of SSC that succeeds when the data set is corrupted with possibly overwhelmingly many outliers. Underlying our analysis are clear geometric insights, which may bear on other sparse recovery problems. A numerical study complements our theoretical analysis and demonstrates the eectiveness of these methods.