Additive Approximation Schemes for Low-Dimensional Embeddings

We consider the task of fitting low-dimensional embeddings to high-dimensional data.

In particular, we study the k-Euclidean Metric Violation problem (k-EMV), where the input is

⩾0 and the goal is to find the closest vector X ∈ M k , where

⩾0 is the set of all k-dimensional Euclidean metrics on n points, and closeness is formulated as the following optimization problem, where ∥ • ∥ is the entry-wise ℓ 2 norm:

Cayton and Dasgupta [CD06] showed that this problem is NP-Hard, even when k = 1. Dhamdhere [Dha04] obtained a O(log(n))-approximation for 1-EMV and leaves finding a PTAS for it as an open question (reiterated recently by Lee [Lee25]). Although k-EMV has been studied in the statistics community for over 70 years, under the name "multidimensional scaling," there are no known efficient approximation algorithms for k > 1, to the best of our knowledge. We provide the first polynomial-time additive approximation scheme for k-EMV. In particular, we obtain an embedding with objective value OPT EMV + ε∥D∥ 2 2 in (n • B) poly(k,ε -1 ) time, where each entry in D can be represented by B bits. We believe our algorithm is a crucial first step towards obtaining a PTAS for k-EMV. Our key technical contribution is a new analysis of correlation rounding for Sherali-Adams / Sum-of-Squares relaxations, tailored to low-dimensional embeddings. We also show that our techniques allow us to obtain additive approximation schemes for two related problems: a weighted variant of k-EMV and ℓ p low-rank approximation for p > 2.