What are the main open problems in compressed sensing?

I am interested in theoretical as well as in numerical point of view.

$\begingroup$
$\endgroup$

A relatively recent (2012) overview of open problems and challenges in compressive sensing has been written by Thomas Strohmer. A somewhat older (2007) listing by Terence Tao is still timely:

- A first question is derandomisation; all of the measurement ensembles for which the really strong compressed sensing results are known have to be generated by a random process; no deterministic compressed sensing method which is rigorously backed by theory is known.
- Another question is to see whether one can improve the two basic algorithms of basis pursuit and matching pursuit and obtain better results (in either accuracy, speed, or robustness); given the lack of lower bounds in this subject it is difficult to tell how close the current algorithms are to being optimal.
- A third is to relax the hypotheses on the measurement ensemble, in particular to allow for some limited amount of linear dependence (or near-dependence) between columns of the measuremement matrix.

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

or
notask anyone to write an encyclopaedia entry for me. $\endgroup$