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.