[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