The need for non-linear mappings

In the last post, I recalled the problem of dimension reduction for finite subsets of $L_1$ . I thought I should mention the main obstacle to reducing the dimension below $O(n)$ for $n$ -point subsets: It can’t be done with linear mappings.

All the general results mentioned in that post use a linear mapping. In fact, they are all of the form:

Change of density, i.e. preprocess the points/subspace so that no point has too much weight on any one coordinate.
Choose a subset of the coordinates, possibly multiplying the chosen coordinates by non-negative weights. (Note that the Newman-Rabinovich result, based on Batson, Spielman, and Srivastava, is deterministic, while in the other bounds, the sampling is random.)

(The dimension reduction here is non-linear, but only applies to special subsets of $L_1$ , like the Brinkman-Charikar point set.)

The next theorem shows that linear dimension reduction mappings cannot do better than $O(n)$ dimensions.

Theorem: For every $1 \leq p \leq \infty$ , there are arbitrarily large $n$ -point subsets of $L_p$ on which any linear embedding into $L_2$ incurs distortion at least $\left(\frac{n-1}{2}\right)^{|1/p-1/2|}.$

Since the identity map from $\ell_1^n$ to $\ell_2^n$ has distortion $\sqrt{n}$ , this theorem immediately implies that there are $n$ -point subsets on which any linear embedding requires $\Omega(n)$ dimension for an ${O(1)}$ -distortion embedding. The $p=1$ case of the preceding theorem was proved by Charikar and Sahai. A simpler proof, which extends to all $p \geq 1$ is given in Lemma 3.1 of a paper by myself, Mendel, and Naor.