10
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ Calling Prof WBJ... calling Prof WBJ... $\endgroup$
    – Yemon Choi
    Sep 11, 2012 at 4:04
  • 1
    $\begingroup$ There are derandomized constructions of the matrices involved in the JL projection, if that's something that interests you. $\endgroup$ Sep 11, 2012 at 5:45
  • 3
    $\begingroup$ For example, this paper: arxiv.org/abs/1006.3585 that constructs the associated matrices using bounded independence hash functions. $\endgroup$ Sep 11, 2012 at 5:46

1 Answer 1

11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.