A Nonlinear Approach to Dimension Reduction

Details A Nonlinear Approach to Dimension Reduction A Nonlinear Approach to Dimension Reduction

2009-07-31

arxiv.org/abs/0907.5477v3

Computer Science

Computational Geometry

Scientific paper

The l_2 flattening lemma of Johnson and Lindenstrauss [JL84] is a powerful tool for dimension reduction. It has been conjectured that the target dimension bounds can be refined and bounded in terms of the intrinsic dimensionality of the data set (for example, the doubling dimension). One such problem was proposed by Lang and Plaut [LP01] (see also [GKL03,MatousekProblems07,ABN08,CGT10]), and is still open. We prove another result in this line of work: The snowflake metric d^{1/2} of a doubling set S \subset l_2 embeds with constant distortion into l_2^D, for dimension D that depends solely on the doubling constant of the metric. In fact, the distortion can be made arbitrarily close to 1, and the target dimension is polylogarithmic in the doubling constant. Our techniques are robust and extend to the more difficult spaces l_1 and l_\infty, although the dimension bounds here are quantitatively inferior than those for l_2.

Affiliated with

Also associated with

No associations

Rating

A Nonlinear Approach to Dimension Reduction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Nonlinear Approach to Dimension Reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Nonlinear Approach to Dimension Reduction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-267344