# 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:

1. Change of density, i.e. preprocess the points/subspace so that no point has too much weight on any one coordinate.
2. 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.