On a randomized version of compressive sensing - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T13:38:50Z http://mathoverflow.net/feeds/question/73837 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73837/on-a-randomized-version-of-compressive-sensing On a randomized version of compressive sensing Daniel 2011-08-27T11:24:20Z 2011-08-29T13:40:06Z <p>The compressive sensing theory of Candes and Tao (See <a href="http://en.wikipedia.org/wiki/Compressed_sensing" rel="nofollow">http://en.wikipedia.org/wiki/Compressed_sensing</a>) relies highly on the fact that the underlying data (such as a signal or an image) is sparse or compressible under some basis. </p> <p>Now we suppose that the underlying data is probabilistic, namely the data follow some distribution. And we want to know with how much probability that the samples from the distribution would be sparse or compressive under some basis.</p> <p>Is there any relevant literature? Thanks. </p> http://mathoverflow.net/questions/73837/on-a-randomized-version-of-compressive-sensing/73844#73844 Answer by Igor Rivin for On a randomized version of compressive sensing Igor Rivin 2011-08-27T13:58:57Z 2011-08-27T13:58:57Z <p><a href="http://www-stat.stanford.edu/~candes/papers/IncoherenceCS.pdf" rel="nofollow">http://www-stat.stanford.edu/~candes/papers/IncoherenceCS.pdf</a></p> http://mathoverflow.net/questions/73837/on-a-randomized-version-of-compressive-sensing/73866#73866 Answer by Sujit_Nair for On a randomized version of compressive sensing Sujit_Nair 2011-08-27T20:40:35Z 2011-08-27T20:40:35Z <p>@Daniel: Can you make your question more precise? In traditional CS, the signal is \$k\$-sparse but their locations are typically uniformly distributed, i.e., there are \$n\choose k\$ possibilities. I am a bit confused as to what you mean by "data follow some distribution".</p> http://mathoverflow.net/questions/73837/on-a-randomized-version-of-compressive-sensing/73969#73969 Answer by Alejandro for On a randomized version of compressive sensing Alejandro 2011-08-29T13:40:06Z 2011-08-29T13:40:06Z <p>This paper may be related:</p> <p><a href="http://www.ece.rice.edu/~vc3/nips2009.pdf" rel="nofollow">V. Cevher, “Learning with compressible priors,” in NIPS, Vancouver, BC, Canada, 2008, p. 7--12.</a></p> <p>From the abstract:</p> <blockquote> <p>We describe a set of probability distributions, dubbed compressible priors, whose independent and identically distributed (iid) realizations result in p-compressible signals. [...] We show that the membership of generalized Pareto, Student’s t, log-normal, Frechet, and log-logistic distributions to the set of compressible priors depends only on the distribution parameters and is independent of N. In contrast, we demonstrate that the membership of the generalized Gaussian dis- tribution (GGD) depends both on the signal dimension and the GGD parameters</p> </blockquote>