What are the main open problems in compressed sensing?

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

  • 2
    $\begingroup$ This is not a sure finalist for the best question ever competition, of course, but why to downvote (especially without any explanation of what exactly you dislike)???? $\endgroup$ – fedja Dec 20 '14 at 23:17
  • 11
    $\begingroup$ There used to be a maxim on MO of the form "MathOverflow is not for people to request other people to write encyclopaedia entries for them". I therefore suggest that Felix should try to narrow his question down first, after looking online at research and survey articles in compressed sensing $\endgroup$ – Yemon Choi Dec 21 '14 at 0:42
  • 2
    $\begingroup$ @YemonChoi Well, I have an idea of what compressed sensing is - having read some articles and knowing a thing or two about linear algebra and signal processing, as background. But I cannot really tell which are the more fundamental problems, as opposed to sheer technicalities. That's why I asked for knowledgeable people, to give their estimate of what the main problems are - a bit like my old question mathoverflow.net/questions/118545/… which I think worked rather well. I did not ask anyone to write an encyclopaedia entry for me. $\endgroup$ – Felix Goldberg Dec 21 '14 at 0:53
  • $\begingroup$ One thing is that it makes a huge difference if one answers this question as a mathematician or as an engineer. Well, of course this is site for mathematics but the idea of compressed sensing is really a practical one: get information about a high dimensional object that lives in lower dimensional but nonlinear subspace from few measurements. The meaning of all ingredients is debatable here and varies a lot from problem to problem. Hence one open problem is to find the right mathematical formulation of the problem... $\endgroup$ – Dirk Dec 21 '14 at 13:31

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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