2025/09/11 by Anderson, Prashanti, Bakshi, Ainesh, Hopkins, Samuel B.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.09652
We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the k-Euclidean Metric Violation problem (\textsfk-EMV), where the input is D ∈ ℝ^\binomn2≥ 0 and the goal is to find the closest vector X ∈ \mathbbMk, where \mathbbMk ⊂ ℝ^\binomn2≥ 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: \textsfOPT_\textrmEMV = min_X ∈ \mathbbMk \Vert D - X \Vert22 . Cayton and Dasgupta [CD'06] showed that this problem is NP-Hard, even when k=1. Dhamdhere [Dha'04] obtained a O(log(n))-approximation for \textsf1-EMV and leaves finding a PTAS for it as an open question (reiterated recently by Lee [Lee'25]). Although \textsfk-EMV has been studied in the statistics community for over 70 years, under the name "multi-dimensional 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 \textsfk-EMV. In particular, we obtain an embedding with objective value \textsfOPT_\textrmEMV + ε \Vert D\Vert22 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 \textsfk-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 \textsfk-EMV and ℓp low-rank approximation for p>2.