About Assaf Naor’s Bourbaki Seminar talk, jan. 22

Well, the week was not quite finished when I published the last post. Indeed, on saturday, Assaf Naor gave a nice Bourbaki talk on Batson, Spielman and Srivastava’s sparsification theorem.

The theorem states that given a nonnegative quadratic form {Q} in {n} variables, expressed as a sum of squares of an arbitrary number of linear forms, there is a positive linear combination of at most {O(n/\epsilon^2)} of these squares which is {\epsilon}-close to {Q}. Assaf described a few striking applications and even managed to give a glimpse of the proof.

Let me mention one of these numerous applications. It is a recent theorem of Newman and Rabinovich, quoted in Moses Charikar’s talk last week. It states that every {n} point subset of {L^1} can be embedded with {(1+\epsilon)}-distorsion in {\ell_{1}^{N}} with {N=O(n/\epsilon^2)}. Assaf’s Bourbaki report contains a half-page derivation of this result from BSS sparsification. I cannot refrain from reproducing it here.

Express the {L^1}-induced metric as a combination of cut metrics,

\displaystyle  \begin{array}{rcl}  |v_i -v_j|_{L^1}=\sum_{E\subseteq[n]}w_{E}|1_E (i) -1_E (j)|, \end{array}

where {w_E \geq 0}. Denote by {e_1 ,\ldots, e_n} the standard basis of {{\mathbb R}^n}. For every {E\subseteq[n]}, let

\displaystyle  \begin{array}{rcl}  x_{E}=\sqrt{w_{E}}\sum_{i\in E}e_{i}\in {\mathbb R}^n. \end{array}

BSS provide us with a collection {\sigma\subset 2^{[n]}} of at most {O(n/\epsilon^2)} subsets of {[n]}, and nonnegative weights {s_E}, {E\in\sigma}, such that

\displaystyle  \begin{array}{rcl}  \sum_{E\subseteq[n]}x_{E}\otimes x_{E}\leq \sum_{E\in\sigma}s_{E}x_{E}\otimes x_{E}\leq (1+\epsilon)\sum_{E\subseteq[n]}x_{E}\otimes x_{E}. \end{array}

This means that for every vector {y\in{\mathbb R}^n},

\displaystyle  \sum_{E\subseteq[n]}w_{E}(\sum_{i\in E}y_i)^2 \leq \sum_{E\in\sigma}s_{E}w_{E}(\sum_{i\in E}y_i)^2 \leq (1+\epsilon)\sum_{E\subseteq[n]}w_{E}(\sum_{i\in E}y_i)^2 .

Define {n} vectors {z_1 ,\ldots,z_n \in{\mathbb R}^{\sigma}} by

\displaystyle  \begin{array}{rcl}  z_{i}=(s_{E}w_{E}1_{E}(i))_{E\in\sigma}. \end{array}

Let {y=e_i -e_j}. Then {(\sum_{i\in E}y_i )^2 =|1_E (i) -1_E (j)|}. Thus

\displaystyle  \begin{array}{rcl}  \sum_{E\in\sigma}s_{E}w_{E}(\sum_{i\in E}y_i)^2 = \sum_{E\in\sigma}s_{E}w_{E}|1_E (i) -1_E (j)|=|z_i -z_j|_{\ell_{1}^{\sigma}}. \end{array}

Substituting {y} into the BBS inequality gives

\displaystyle  \begin{array}{rcl}  |v_i -v_j|_{L^1}\leq |z_i -z_j|_{\ell_{1}^{\sigma}}\leq (1+\epsilon)|v_i -v_j|_{L^1} \end{array}

Newman and Rabinovich’s proof is different. Their paper contains a higher dimensional generalization of the above embedding theorem. Higher dimensional is taken in the following sense. {L^1}-embeddable metrics are combinations of cut metrics. Newman and Rabinovich generalize metrics (thought of as {1}-dimensional volumes of graphs) to volumes of simplicial complexes. Cuts generalize to coboundaries in {{\mathbb Z}/2{\mathbb Z}}-cohomology, and cut metrics have a generalization, cut volumes. This seems to me related to the topic of Nati Linial’s course, which starts tomorrow.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Other, Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s