  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<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.
