In the last post, I recalled the problem of dimension reduction for finite subsets of . I thought I should mention the main obstacle to reducing the dimension below for -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 , like the Brinkman-Charikar point set.)
The next theorem shows that linear dimension reduction mappings cannot do better than dimensions.
Theorem: For every , there are arbitrarily large -point subsets of on which any linear embedding into incurs distortion at least
Since the identity map from to has distortion , this theorem immediately implies that there are -point subsets on which any linear embedding requires dimension for an -distortion embedding. The case of the preceding theorem was proved by Charikar and Sahai. A simpler proof, which extends to all is given in Lemma 3.1 of a paper by myself, Mendel, and Naor.