{"ID":2872300,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.09652","arxiv_id":"2509.09652","title":"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}^{\\binom{n}{2}}_{\\geq 0}$ and the goal is to find the closest vector $X \\in \\mathbb{M}_{k}$, where $\\mathbb{M}_k \\subset \\mathbb{R}^{\\binom{n}{2}}_{\\geq 0}$ 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: \\[ \\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 \u003e 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 $\\textsf{OPT}_{\\textrm{EMV}} + \\varepsilon \\Vert D\\Vert_2^2$ in $(n\\cdot B)^{\\mathsf{poly}(k, \\varepsilon^{-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\u003e2$.","short_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}^{\\binom{n}{2}}_{\\geq 0}$ and the goal is to find the closest vector $X \\in \\mathbb{M}_{k}$, where $\\mathbb{M}...","url_abs":"https://arxiv.org/abs/2509.09652","url_pdf":"https://arxiv.org/pdf/2509.09652v1","authors":"[\"Prashanti Anderson\",\"Ainesh Bakshi\",\"Samuel B. Hopkins\"]","published":"2025-09-11T17:45:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}