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 (or ) satisfying the -RIP for

Building deterministic matrices pass the square-root bottleneck () 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 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 , certify that it indeed is RIP for some then one could have a randomized algorithm to build RIP matrices (but that is guaranteed to eventually find one). This motives the following questions:

- Let . For which is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix is -RIP?
- In particular, a -RIP matrix has to not have sparse vectors in its nullspace. This motivates a second question: Let . for which is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix does not have -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.

### Like this:

Like Loading...

*Related*

Kasper Green and Jelani Nelson have shown sharpness in the J-L Lemma.

A very pretty argument is here: http://arxiv.org/abs/1411.2404

Many thanks for the pointer, I wasn’t aware of this paper, it is quite a nice one indeed! I will edit the post (and notes) accordingly.