Sparsification

Open problem: Dimension reduction in L_1

~ James ~ Leave a comment

Since I’ve been interacting a lot with the theory group at MSR Redmond (see the UW-MSR Theory Center), I’ve been asked occasionally to propose problems in the geometry of finite metric spaces that might be amenable to probabilistic tools. Here’s a fundamental problem that’s wide open. Let {c_D(n)} be the smallest number such that every {n}-point subset of {L_1} embeds into {\ell_1^{c_D(n)}} with distortion at most {D}. Here’s what’s known.

  1. Talagrand (following work of Bourgain-Lindenstrauss-Milman and Schechtman) proved that for every {\varepsilon > 0}, every {n}-dimensional subspace of {L_1} admits a {(1+\varepsilon)}-distortion embedding into {\ell_1^{d}} with {d = O((n \log n)/\varepsilon^2)}. In particular, this gives

    \displaystyle c_{1+\varepsilon}(n) = O((n \log n)/\varepsilon^2).

  2. Brinkman and Charikar showed that {c_D(n) \geq \Omega(n^{1/D^2})} for {D \geq 1}. A significantly simpler proof was later given by Assaf Naor and myself. (With Brinkman and Karagiozova, we have also shown that this bound is tight for the Brinkman-Charikar examples and their generalizations.)
  3. Recently, Newman and Rabinovich showed that one can take {c_{1+\varepsilon}(n) = O(n/\varepsilon^2)} for any {\varepsilon > 0}. Their paper relies heavily on the beautiful spectral sparsification method of Batson, Spielman, and Srivastava. In fact, it is shown that one can use only {O(n/\varepsilon^2)} weighted cuts (see the paper for details). This also hints at a limitation of their technique, since it is easy to see that the metric on {\{1,2,\ldots,n\} \subseteq \mathbb R} requires {\Omega(n)} cuts for a constant distortion embedding (and obviously only one dimension).

The open problem is to get better bounds. For instance, we only know that

\displaystyle \Omega(n^{1/100}) \leq c_{10}(n) \leq O(n).

There is evidence that n^{\Theta(1/D^2)} might be the right order of magnitude.  In the large distortion regime, when D = \Omega(\sqrt{\log n} \log \log n), results of Arora, myself, and Naor show that c_D(n) = O(\log n).