Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1 - Deshpande, Amit (36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), 2016)
Goemans showed that any n points x_1,..., x_n in d-dimensions satisfying l_2^2 triangle inequalities can be embedded into l_[1], with worst-case distortion at most sqrt[d]. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_[2]^[2]-to-l_[1] embedding with average distortion at most the stable rank, 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 SPARSEST CUT 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 l_[2]^[2] metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion sqrt[d].