Embedding approximately low-dimensional $\ell_2^2$ metrics into $\ell_1$
Amit Deshpande, Prahladh Harsha, Rakesh Venkat · arXiv (Cornell University) · 2015
Goemans showed that any $n$ points $x_1, \dotsc x_n$ in $d$-dimensions satisfying $\ell_2^2$ triangle inequalities can be embedded into $\ell_{1}$, with worst-case distortion at most $\sqrt{d}$. We extend this to the case when the points are approximately low-dimensional, albeit with average distortion guarantees. More precisely, we give an $\ell_{2}^{2}$-to-$\ell_{1}$ embedding with average distortion at most the stable rank, $\mathrm{sr}(M)$, of the matrix $M$ consisting of columns $\{x_i-x_j\}_{i