7
$\begingroup$

I am looking for theory on whether compressed sensing reconstruction via ℓ1-minimization is unique and under which conditions.
I have looked through:

Tropp, J. A., "Just relax: convex programming methods for identifying sparse signals in noise," IEEE Transactions on Information Theory, 2006, 52, 1030-1051.

This paper states that the minimizer is unique but I can't quite boil down exactly what is required for this uniqueness (Eq. (ℓ1-Error) and Theorem 14) to hold.

I also looked at:

Candès, E. J.; Romberg, J. & Tao, T., "Stable signal recovery from incomplete and inaccurate measurements," Communications on Pure and Applied Mathematics, 2006, 59, 1207-1223.

However, they do not seem to claim that the minimizer is unique.
Since both of these papers are from the earlier days of compressed sensing, I suspect that there may be newer results on this uniqueness of the solution. Do any of you have some hints?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
6
$\begingroup$

"Recovery of Exact Sparse Representations in the Presence of Bounded Noise", by J. Fuchs, deals with the case you ask. From the abstract:

The purpose of this contribution is to extend some recent results on sparse representations of signals in redundant bases developed in the noise-free case to the case of noisy observations. [..] We consider the case $b = Ax_0 + e$ [...] and seek conditions under which $x_0$ can be recovered from $b$ ...

I think theorem 2 and 3 are what you're looking for (at least in part).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for this answer. Now I just wonder to which extent the conditions around theorem 2 + 3 are satisfied by random Gaussian matrices: - $\bar A_o$ full rank - linear independence of the active columns, I suppose. - The mutual coherence condition in (2). - The condition in (8). Any idea? $\endgroup$
    – Thomas Arildsen
    Commented May 14, 2013 at 19:59
  • 1
    $\begingroup$ I suspect the full rank and the mutual coherence conditions are true for Gaussian matrices with "very high probability". I'm not sure about condition (8). By the way, take a look at chapter 5 of Elad's book (Sparse and redundant representations). It seems that for the noisy observations case, the focus should be on stability, rather than in uniqueness. $\endgroup$
    – Alejandro
    Commented May 16, 2013 at 12:13
  • $\begingroup$ I think you are right about stability in the noisy case. This also seems to be the theme of the paper @peter-k recommended in his comment. I will look into that. $\endgroup$
    – Thomas Arildsen
    Commented May 16, 2013 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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