Header menu link for other important links
X
Embedding approximately low-dimensional ℓ22 metrics into ℓ1
A. Deshpande, P. Harsha,
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2016
Volume: 65
   
Pages: 10.1 - 10.13
Abstract
Goemans showed that any n points x1, . . . xn in d-dimensions satisfying ℓ22 triangle inequalities can be embedded into ℓ1, with worst-case distortion at most √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 ℓ22-to-ℓ1 embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {xi-xj}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 ℓ22 metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion √d. © Amit Deshpande, Prahladh Harsha, and Rakesh Venkat.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969