Filed under: Papers

[author]Rasmus J. Kyng, Jeff M. Phillips and Suresh Venkatasubramanian[/author]

In the 20th Fall Workshop on Computational Geometry, 2010.

We propose an algorithm for dimensionality reduction on the simplex, mapping a set of high-dimensional distributions to a space of lower-dimensional distributions, whilst approximately preserving pairwise Hellinger distance between distributions. By introducing a restriction on the input data to distributions that are in some sense quite smooth, we can map $n$ points on the $d$-simplex to the simplex of $O(\eps^{-2}\log n)$ dimensions with $\eps$-distortion with high probability. The techniques used rely on a classical result by Johnson and Lindenstrauss on dimensionality reduction for Euclidean point sets and require the same number of random bits as non-sparse methods proposed by Achlioptas for database-friendly dimensionality reduction.

Links. PDF

Tags: CCF 0841185, CCF 0953066

No Comments so farLeave a commentLine and paragraph breaks automatic, e-mail address never displayed, HTML allowed:

`<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>`