What are the main open problems in compressed sensing?
I am interested in theoretical as well as in numerical point of view.
$\begingroup$
$\endgroup$
4
asked Dec 20, 2014 at 22:56
-
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$– fedjaCommented Dec 20, 2014 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 ChoiCommented Dec 21, 2014 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 GoldbergCommented Dec 21, 2014 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$– DirkCommented Dec 21, 2014 at 13:31
Add a comment
|
1 Answer
$\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.
answered Dec 21, 2014 at 11:55