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 (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:

1. Let . For which is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix is -RIP?
2. 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.

Advertisement