We introduce a new variant of the nearest neighbor search problem, which allows for some coordinates of the dataset to be arbitrarily corrupted or unknown. Formally, given a dataset of @math points @math in high-dimensions, and a parameter @math , the goal is to preprocess the dataset, such that given a query point @math , one can compute quickly a point @math , such that the distance of the query to the point @math is minimized, when ignoring the "optimal" @math coordinates. Note, that the coordinates being ignored are a function of both the query point and the point returned. We present a general reduction from this problem to answering ANN queries, which is similar in spirit to LSH (locality sensitive hashing) [IM98]. Specifically, we give a sampling technique which achieves a bi-criterion approximation for this problem. If the distance to the nearest neighbor after ignoring @math coordinates is @math , the data-structure returns a point that is within a distance of @math after ignoring @math coordinates. We also present other applications and further extensions and refinements of the above result. The new data-structures are simple and (arguably) elegant, and should be practical -- specifically, all bounds are polynomial in all relevant parameters (including the dimension of the space, and the robustness parameter @math ).
There has been a large body of research focused on adapting widely used methods for high-dimensional data processing to make them applicable to corrupt or irrelevant data. For example, Robust PCA @cite_7 is an adaptation of the PCA algorithm that handles a limited amount of adversarial errors in the input matrix. Although similar in spirit, those approaches follow a different technical development than the one in this paper.
@cite_7
2145962650
This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individuallyq We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the e1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.