Non-probabilistic proof of the Johnson–Lindenstrauss lemma

Question

The Johnson–Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved (a set of $n$ points in high dimensional Euclidean space can be mapped into an $O(\log (n)/ \varepsilon^2)$-dimensional Euclidean space such that the distance between any two points changes by only a factor of $1 \overset{+}{-} \varepsilon)$. A well-known proof of this exploits the phenomenon of concentration of measure and involves, in a sense, a probabilistic argument (Gaussian random matrices). Does there exist a non-probabilistic proof of this lemma?

Answer 1

You might be interested in something Jelani Nelson wrote me in an email on Oct. 13, 2011:

"Another notion of derandomizing JL is the following: come up with a distribution over embeddings that can be sampled using as few random bits as possible so that, for any vector $x$ in $R^d$, a random vector has its $\ell_2$ norm preserved up to $1+\epsilon$ with probability $1-\delta$ by a random embedding from that distribution (embedding into $O(\epsilon^{-2}\log(1/\delta))$ dimensions). Existentially, it can be shown that there exists such a distribution which can be sampled from using $O(log(d/\delta))$ random bits. An actual explicit such distribution would imply the two works above, since our deterministic algorithm could just try all embeddings in the support of the distribution (there would be poly$(d/\delta)$ of them) and take the best one, with $\delta = 1/n^2$.

Obtaining a distribution that can be sampled using $O(\log(d/\delta))$ random bits is open. The best we have to date are:

-- Daniel M. Kane, Raghu Meka, Jelani Nelson: Almost Optimal Explicit Johnson-Lindenstrauss Families. APPROX-RANDOM 2011: 628-639. (requires $O(\log d + \log(1/\delta)*\log\log(1/\delta) + \log(1/\delta)\log(1/\epsilon))$ random bits)

-- Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. IEEE Conference on Computational Complexity 2011: 262-272. (requires $(1+o(1))\log d + O(\log(1/(\epsilon\delta))$ random bits).

In fact, combining the approaches of both works can get $(1+o(1))\log d + O(\log(1/\delta)\log\log(1/\delta) + \log(1/\delta)\log(1/\epsilon))$."

I suggest contacting Jelani directly if you want more information.