18.S096: Johnson-Lindenstrauss Lemma and Gordon’s Theorem

The fifth set of Lecture notes for my course is available here. They are about dimension reduction, Johnson-Lindenstrauss Lemma and Gordon’s Escape Through a Mesh Theorem, it also includes three open problems. As usual, I will document the open problems here, while referring a much more detailed description of the problems on the notes, including description of partial progress.

Originally there was a problem stated regarding the optimality of the Johnson-Lindenstrauss Lemma, but it had been solved (here) and so it was removed (thanks to the reader that pointed out this paper).

Open Problem 5.1. (Deterministic Restricted Isometry Property matrices)

Construct deterministic matrices A\in\mathbb{C}^{M\times N} (or A\in\mathbb{R}^{M\times N}) satisfying the (s,\frac13)-RIP for s\approx\frac{M^{0.6}}{\mathrm{polylog}(N)}

Building deterministic matrices pass the square-root bottleneck (s\approx\sqrt{M}) is a notoriously hard problem, see the notes for references, history, and more information.

Open Problem 5.2. (Certifying the Restricted Isometry Property)

If we take A a matrix with i.i.d. Gaussian entries then it should be RIP for $s \approx \frac{M}{\log\left( N \right)}$ (see notes). If we were able to, given A, certify that it indeed is RIP for some s then one could have a randomized algorithm to build RIP matrices (but that is guaranteed to eventually find one). This motives the following questions:

  1. Let N = 2M. For which s is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix A is \left(s,\frac13\right)-RIP?
  2. In particular, a \left(s,\frac13\right)-RIP matrix has to not have s sparse vectors in its nullspace. This motivates a second question: Let N = 2M. for which s is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix A does not have s-sparse vectors in its nullspace?

The second question is tightly connected with the question of finding sparsest vectors on a subspace that was target of much recent research, we refer to the notes for references, some known results, and more information.

2 thoughts on “18.S096: Johnson-Lindenstrauss Lemma and Gordon’s Theorem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s