Search for: All records

We study the design of embeddings into Euclidean space with outliers. Given a metric space (X, d) and aninteger k, the goal is to embed all but k points in X (called the “outliers”) into ℓ2 with the smallest possibledistortion c. Finding the optimal distortion c for a given outlier set size k, or alternately the smallest k fora given target distortion c are both NP-hard problems. In fact, it is UGC-hard to approximate k to withina factor smaller than 2 even when the metric sans outliers is isometrically embeddable into ℓ2. We considerbi-criteria approximations. Our main result is a polynomial time algorithm that approximates the outlier setsize to within an O(log2 k) factor and the distortion to within a constant factor.The main technical component in our result is an approach for constructing Lipschitz extensions ofembeddings into Banach spaces (such as ℓp spaces). We consider a stronger version of Lipschitz extensionthat we call a nested composition of embeddings: given a low distortion embedding of a subset S of the metricspace X, our goal is to extend this embedding to all of X such that the distortion over S is preserved, whereasthe distortion over the remaining pairs of points in X is bounded by a function of the size of X \ S. Priorwork on Lipschitz extension considers settings where the size of X is potentially much larger than that of Sand the expansion bounds depend on |S|. In our setting, the set S is nearly all of X and the remaining setX \ S, a.k.a. the outliers, is small. We achieve an expansion bound that is polylogarithmic in |X \ S|.