• Calendar

December 28, Sunday
12:00 – 14:00

The Johnson Lindenstrauss lemma states that for any n points in the Euclidean space (regardless of their initial dimension), there is a projection onto a subspace of dimension $O(\log n/epsilon^2)$ which preserves all pairwise distances to within a factor of $1+\epsilon$. In fact most projections will do, which is what makes this lemma so useful.

What happens when a faithful presentation of distances does not seem to be enough? What if we care about preserving additional geometric properties? i.e. preserving the angles between every three points? What about preserving the volumes spanned by four points, etc. ? In this work we extend the JL lemma to show that when projecting onto $k \log n \epsilon^2$ dimensions (i.e. an additional factor of $k$ compared to JL) we get that with high probability, no set of size $\le k$ changes its volume by a factor greater than $(1+\epsilon)^{k-1}$. Moreover, distances of points from affine hulls of such sets do not change by more than factor ($1+\epsilon$). A consequence of the above with $k=3$ is that angles can be preserved using the same number of dimensions as the one used in the JL lemma.

Our method can be applied to many problems with high-dimensional nature such as Projective Clustering and Approximated Nearest Affine Neighbour Search. In particular, it shows a first poly-logarithmic query time approximation algorithm to the latter.