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.
The above discussion has focused on notions of robustness that allow an adversary to corrupt a constant fraction of the entries in the matrix @math . However, this is only one possible definition of what it means for an estimator to be robust to noise. For example, principal component analysis can be seen as finding a @math -dimensional subspace that minimizes the sum of squared distances to the data points. A number of works have proposed modifications to this objective function (along with approximation algorithms) in the hopes that this objective function is more robust. As an example, @cite_27 gave a @math approximation algorithm for the problem of finding a subspace that minimizes the sum of @math distances to the data points (for @math ). Another example is the recent work of @cite_6 which gives a constant factor approximation for finding a @math -dimensional subspace that maximizes the sum of Euclidean lengths of the projections of the data points (instead of the sum of squared lengths). Lastly, we mention that @cite_33 gave a geometric definition of an outlier (that does not depend on a hidden subspace @math ) and give an optimal algorithm for removing outliers according to this definition.
@cite_27 @cite_33 @cite_6
1976986203 2050991582
We study the problem of finding an outlier-free subset of a set of points (or a probability distribution) in n-dimensional Euclidean space. As in [BFKV 99], a point x is defined to be a β-outlier if there exists some direction w in which its squared distance from the mean along w is greater than β times the average squared distance from the mean along w. Our main theorem is that for any e > 0, there exists a (1 - e) fraction of the original distribution that has no O(n e(b + logn e))-outliers, improving on the previous bound of O(n7b e). This is asymptotically the best possible, as shown by a matching lower bound. The theorem is constructive, and results in a 1 1-e approximation to the following optimization problem: given a distribution µ (i.e. the ability to sample from it), and a parameter e > 0, find the minimum β for which there exists a subset of probability at least (1 - e) with no β-outliers. The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.