# A Nonlinear Approach to Dimension Reduction - Computer Science > Computational Geometry

A Nonlinear Approach to Dimension Reduction - Computer Science > Computational Geometry - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The $l 2$ flattening lemma of Johnson and Lindenstrauss JL84 is a powerfultool for dimension reduction. It has been conjectured that the target dimensionbounds can be refined and bounded in terms of the intrinsic dimensionality ofthe data set for example, the doubling dimension. One such problem wasproposed by Lang and Plaut LP01 see alsoGKL03,MatousekProblems07,ABN08,CGT10, and is still open. We prove anotherresult in this line of work:The snowflake metric $d^{1-2}$ of a doubling set $S \subset l 2$ embeds withconstant distortion into $l 2^D$, for dimension $D$ that depends solely on thedoubling constant of the metric. In fact, the distortion can be madearbitrarily close to 1, and the target dimension is polylogarithmic in thedoubling constant. Our techniques are robust and extend to the more difficultspaces $l 1$ and $l \infty$, although the dimension bounds here arequantitatively inferior than those for $l 2$.