Over the years, the probabilistic method has allowed for the original proof of Johnson and Lindenstrauss to be greatly simplified and sharpened, while at the same time giving conceptually simple randomized algorithms for constructing the embedding [5,6,8]. Roughly speaking, all such algorithms project the input points onto a spherically random hyperplane through the origin. While this is conceptually simple, in practical terms it amounts to multiplying the input matrix A with a dense matrix of real numbers. This can be a non-trivial task in many practical computational environments. At the same time, investigating the role of spherical symmetry in the choice of hyperplane is mathematically interesting in.
