Additive Approximation Schemes for Low-Dimensional Embeddings

Abstract

We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the $k$-Euclidean Metric Violation problem ($\textsf{$k$-EMV}$), where the input is $D\in {\mathbb{R}}_{\ge 0}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ and the goal is to find the closest vector $X\in {\mathbb{M}}_k$, where ${\mathbb{M}}_k\subset {\mathbb{R}}_{\ge 0}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ is the set of all $k$-dimensional Euclidean metrics on $n$ points, and closeness is formulated as the following optimization problem, where $\Vert \cdot \Vert$ is the entry-wise ${\ell }_2$ norm: \[ \textsf{OPT}_{\textrm{EMV}} = \min_{X \in \mathbb{M}_{k} } \Vert D - X \Vert_2^2\,.\] 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 $\textsf{$1$-EMV}$ and leaves finding a PTAS for it as an open question (reiterated recently by Lee [Lee'25]). Although $\textsf{$k$-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 $\textsf{$k$-EMV}$. In particular, we obtain an embedding with objective value ${\text{OPT}}_{\text{EMV}}+\epsilon \Vert D{\Vert }_2^2$ in $(n\cdot B{)}^{\mathsf{poly}(k,{\epsilon }^{-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 $\textsf{$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 $\textsf{$k$-EMV}$ and ${\ell }_p$ low-rank approximation for $p>2$.

57 pages