Embedding approximately low-dimensional ${\ell }_2^2$ metrics into ${\ell }_1$

Abstract

Goemans showed that any $n$ points $x_1,\dots 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<j}$. Average distortion embedding suffices for applications such as the Sparsest Cut problem. Our embedding gives an approximation algorithm for the \sparsestcut problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a new perspective on ${\ell }_2^2$ metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion $\sqrt{d}$. Furthermore, while the seminal result of Arora, Rao and Vazirani giving a $O(\sqrt{\log n})$ guarantee for Uniform Sparsest Cut can be seen to imply Goemans' theorem with average distortion, our work opens up the possibility of proving such a result directly via a Goemans'-like theorem.

References in corpus (3)

• Finite metric spaces--combinatorics, geometry and algorithms
• Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
• Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank