A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies

arXiv:2311.17840v2 Announce Type: replace-cross
Abstract: Multi-dimensional Scaling (MDS) is a family of methods for embedding an $n$-point metric into low-dimensional Euclidean space. We study the Kamada-Kawai formulation of MDS: given a set of non-negative dissimilarities $\{d_{i,j}\}_{i , j \in [n]}$ over $n$ points, the goal is to find an embedding $\{x_1,\dots,x_n\} \in \mathbb{R}^k$ that minimizes \[\text{OPT} = \min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2 \right] \]
Kamada-Kawai provides a more relaxed measure of the quality of a low-dimensional metric …

abstract algorithm arxiv cs.ds cs.lg embedding family low mds negative polynomial scaling set space stat.ml study type via