This is an announcement for the paper "A nonlinear approach to dimension reduction" by Lee-Ad Gottlieb and Robert Krauthgamer.
Abstract: A powerful embedding theorem in the context of dimension reduction is the $\ell_2$ flattening lemma of Johnson and Lindenstrauss. It has been conjectured that improved dimension bounds may be achievable for some data sets by bounding the target dimension in terms of the intrinsic dimensionality of the data set (for example, the doubling dimension). One such problem was proposed by Lang and Plaut, and is still open. We pose another question in this line of work: Does the snowflake metric $d^{1/2}$ of a doubling set $S\subset\ell_2$ always embed with distortion O(1) into $\ell_2^D$, for dimension $D$ that depends solely on the doubling constant of the metric? We resolve this question in the affirmative, and furthermore obtain distortion arbitrarily close to 1. Moreover, our techniques are sufficiently robust to be applicable also to the more difficult spaces $\ell_1$ and $\ell_\infty$, although these extensions achieve dimension bounds that are quantitatively inferior than those for $\ell_2$.
Archive classification: cs.CG cs.DS math.FA
The source file(s), , is(are) stored in gzipped form as with size . The corresponding postcript file has gzipped size .
Submitted from: adi@cs.nyu.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/0907.5477
or
http://arXiv.org/abs/0907.5477
or by email in unzipped form by transmitting an empty message with subject line
uget 0907.5477
or in gzipped form by using subject line
get 0907.5477
to: math@arXiv.org.