# Conditions for unique (not exact) recovery from noisy compressed measurements

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?

## 1 Answer

"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).

• 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? May 14, 2013 at 19:59
• 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. May 16, 2013 at 12:13
• 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. May 16, 2013 at 13:07