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-\textsf{EMV}\)), where the input is \(D \in \mathbb{R}_{\geqslant 0}^{\binom{n}{2}}\) and the goal is to find the closest vector \(X \in \mathbb{M}_k\), where \(\mathbb{M}_k \subset \mathbb{R}_{\geqslant 0}^{\binom{n}{2}}\) is the set of all \(k\)-dimensional Euclidean metrics on \(n\) points, and closeness is formulated as the following optimization problem, where \(\|\cdot\|\) is the entry-wise \(\ell_2\) norm: \(\mathsf{OPT}_{\textsf{EMV}} = \min_{X \in \mathbb{M}_k} \|D - X\|_2^2\). 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-\textsf{EMV}\) and leaves finding a PTAS for it as an open question (reiterated recently by Lee [Lee25]). Although \(k-\textsf{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 \gt 1\), to the best of our knowledge.