In the Crossing the Donoho-Tanner Border, I mentioned the following:
One could also, as I jokingly suggested, increase the size of the problem so that something that was barely sparse in one instance becomes highly sparse in the new setting.
and pinpointed how to read the Donoho-Tanner phase transition to see what to expect from l_1 minimization solvers. I am also sure y'all have noticed in the recent long post of the week that Emmanuel Candès, Yonina Eldar and Deanna Needell came up with a more mind blowing argument in: Compressed sensing with coherent and redundant dictionaries. If you don't want to read the previous entry, the abstract reads:
This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an l_1-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence
restriction on the dictionary and our results may be the first of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of l_1-analysis for such problems.
Of considerable interest:
...Hence, the result says that for any dictionary, signals f such that D* f decays rapidly can be approximately reconstructed using l1-analysis from just a few random measurements....In words, if the columns of the Gram matrix are reasonably sparse and if f happens to have a sparse expansion, then the frame coe cient sequence D* f is also sparse. All the transforms discussed above, namely, the Gabor, curvelet, undecimated wavelet, oversampled Fourier transform all have nearly diagonal Gram matrices and thus, sparse columns....
And then you have to read page 7 with it's little surprise. I wonder how our audio friends would think of that.... yeah.... I am talking to you Bob. I know you got two papers out, but this is important stuff :)
With regards to yesterday's question, Mingyan Liu tells me her group is currently investigating these sparse matrices.
8 comments:
Dear Igor,
You have to be careful: the paper of Candes et al. use an *analysis* prior, which means they consider the L1 norm of the inner product with the atoms, not the L1 norm of the coefficients in the dictionary.
For ortho systems, these are equivalent, but for redundant dictionaries, the more your dictionary is coherent, the more different these two reconstructions differ.
This is why this (wonderful) result tells another story. I think it is important to make the distinction between these "two kinds of L1", analysis vs. synthesis.
For some redundant systems (but not all !), which are tight frames (or approximately tight), like curvelet, etc. this analysis prior makes lots of sense, because for some image classes (eg. cartoon) one knows that the analysis is sparse.
Another fascinating question is for non tight frame analysis prior like TV : what can you tell.
Dear Igor,
Don't you mean 'perhaps de-coherence is not necessary' ?
Hello Anonymous 2,
Did you read the paper ?
Igor.
Dear Igor,
This is anonymous #2.
Admittedly, i just glanced over the paper but read the abstract.
To my limited understanding, compressed sensing is known to work with incoherent matrices.
In their paper, Candes et al. say that you can do this also when the matrices are coherent. Hence to my best understanding, the message should be 'perhaps incoherence is not necessary',
but perhaps i'm missing something here. The name of section 1.2 in their paper is 'do we really need incoherence?', which is consistent with my comment
Hello Anonymous #2,
You're right. It could be read that way. I was reading it having in mind the words "the concept of" as in "Perhaps the concept of coherence is not necessary." but maybe "perhaps incoherence is not necessary" might have been more to the point.
Thanks for feedback,
Cheers,
Igor.
Also I took the sentence right out of the paper.
Igor.
A minor typo: looking at the paper and Candes's website, it doesn't look like Yi Ma is involved with this work.
Oops. Thanks Anonymous, I just corrected it.
Igor
Post a Comment