19
$\begingroup$

From what I have heard, compressed sensing can only be utilized for a sparse signal. Is this correct?

If that is the case, how can a sparse signal be distinguished from any bandlimited signal? Every signal can be expanded to include a sparse or zero-coefficient signal part. Does it become a sparse signal in that case?

Does compressed sensing all the time retrieve information or signal perfectly?

Added: by the way, I just started to learn these things, so the purpose of this question is to taste a bit of what these things are.

Improve this question
$\endgroup$
2
  • $\begingroup$ @DilipSarwate So is there any case where a person is forced only to use Shannon-nyquist sampling theorem? $\endgroup$
    – user2346
    Commented May 18, 2012 at 13:25
  • $\begingroup$ I think that if you are in a situation where the sampling matrix is not optimal with respect to the measurement matrix (i.e. your measurement and representation bases are coherent) you might not have a choice but to use the Nyquist frequency if you want to catch the highest frequency content. Otherwise, you could design your measurement matrix to be incoherent with respect to some representation basis. $\endgroup$
    – val
    Commented Feb 10, 2014 at 23:39

4 Answers 4

Reset to default
12
$\begingroup$

Like @sansuiso said, compressed sensing is a way of acquiring signals that happens to be efficient if the signals are sparse or compressible.

Compressed Sensing is efficient because signals are multiplexed, hence the number of multiplexed samples (called measurements) is smaller than the number of samples required by Shannon-Nyquist where there are no strong assumptions on the signal.

In the noiseless case, it can be shown that compressive sensing reconstruction solver can recover an exact solution.

In the compressible case, as opposed to the strictly sparse case, it can be shown that the reconstruction error is bounded.

And yes most signals, including ultrasounds are somehow either sparse or compressible. It generally comes down to figuring out the dictionary where the signal is sparse. Domain experts generally know these things.

The interesting question you have is: Imagine you have a non sparse signal and then add zeros to make it sparse and then use compressed sensing to sample that signal, wouldn't it better than directly sampling the full signal?

The answer is no.

It turns out that the sampling requirements for which CS work require more infromation than just performing a full sampling of the original (full/non-zero) signal. In other words, the number of CS measurements required would be higher than the number of non-zero elements in the signals. By sparsifying the signal, you are "losing" on purpose the information about where the signal is supported (i.e. non-zero). The hard part of Compressive Sensing and attendant reconstruction solvers is to find that location where those non zero elements of the signal live: If you know beforehand the locations of those non zero elements, then there is no need to go to a less efficient method of sampling that signal. Indeed, finding the location of the non-zero elements of a signal is the reason we talk about compressive sensing being NP-Hard, BPP and so forth..... Up until 2004, we thought it was hard to do.

Let me put it some other way: Let us assume a signal has K non zero components. If you know the location of these K elements, then you need only K information to know your signal. If you add zeros anywhere in the signal and make that signal of size N, you now need to sample the signal N times through traditional sampling or O(Klog(K/N)) times with a compressive sensing approach. Since O(Klog(K/N) > K, losing the information about the location of the non zeros elements has yielded a larger set of samples/measurements.

You might be interested in reading my small blog on the subject: http://nuit-blanche.blogspot.com/search/label/CS And the following resource: http://nuit-blanche.blogspot.com/p/teaching-compressed-sensing.html

Improve this answer
$\endgroup$
7
$\begingroup$

There are two things here: sparsity and compressed sensing.

Sparsity is a general hypothesis, just claiming that most of the energy of a signal is stored in a small number of coefficients in the good basis. This is quite intuitive, looking at Fourier transforms or wavelet transforms. It is true for probably any signal of interest (image, sound...) and explains why jpeg or mp3 compression work.

Quoting J-L Starck at ICIP'11 (during the questions after his plenary talk):

Compressed sensing is a theorem.

What he means is that compressed sensing is a set of results that guarantees you that a sparse signal can be exactly recovered with very few measurements, provided you have the good sensing matrix, i.e. your measurements have some nice properties (someone explained that to me as a kind of multiplexed sensing). Reconstruction algorithms use the sparsity of the signal as additional information during the reconstruction process, usually by minimizing the L1 norm of the signal in some wavelet basis (recall that the L0-norm-constrained recovery problem is usually not solvable, because it is NP-hard).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Just for the record, my research is in medical ultrasound, the raw information of which is notable for being pretty much incompressible. $\endgroup$
    – Henry Gomersall
    Commented May 20, 2012 at 8:50
  • $\begingroup$ @HenryGomersall That is interesting - can you please expand on that? It is incompressible because ultrasound signals have a lot of support in the frequency domain? (Hence not sparse?) $\endgroup$
    – Spacey
    Commented May 24, 2012 at 20:21
  • $\begingroup$ @Mohammad yes. The information is in essence an interference pattern from a pretty random distribution of scatterers at every scale. This gives an essentially white signal. There is a whole philosophical discussion as to whether the salient information is sparse, but that would not be an ultrasound image as clinicians would expect it. $\endgroup$
    – Henry Gomersall
    Commented May 24, 2012 at 21:36
  • 1
    $\begingroup$ @HenryGomersall Interesting, I just saw this discussion, but if your data is essentially white, then how is it data to begin with? What possible use do you have for it? $\endgroup$
    – TheGrapeBeyond
    Commented Feb 10, 2014 at 22:42
  • $\begingroup$ It means there is no correlation between samples. Whiteness is a statement about the PSD, which is the Fourier transform of the autocorrelation function. So no correlation implies a white signal. The nature of incompressible signals is they look like random noise. $\endgroup$
    – Henry Gomersall
    Commented Feb 14, 2014 at 11:29
2
$\begingroup$

I am not an expert on compressed sensing, but I have some familiarity with it.

I heard somewhere that compressed sensing can only be utilized for a sparse signal. Is this right?

No, it can be used anywhere, but as Dilip said, it only makes sense for sparse signals. If the signal isn't sparse then there is no reason to not do standard Nyquist sampling since that will be efficient.

And how can you distinguish a sparse signal from any bandlimited signal?

Although I am sure that there are formal definitions of "sparsity" out there (and they are probably not the same, either), I am not aware of a formal definition. What people mean by sparsity tends to change depending on the context.

I would say that a sparse signal is any signal that has much lower information (using the information theory definition of the word) content than it potentially could have if it was continuous and fully utilized its frequency range. What are some examples of sparse signals? Frequency hopping signals. Bursty signals. A walkie-talkie AM signal that is transmitted continuously even if no one is talking.

Every signal can be expanded to include a sparse or zero-coefficient signal part.......

What, like saying the signal is 100 MHz wide even if it's only 1 MHz wide? You can define things to be whatever you want, just like old-time astronomers were able to get the math of the sun orbiting the Earth to work. That doesn't mean that their equations were useful.

And does compressed sensing all the time retrieve information or signal perfectly?

Compressed sensing is a technique. Like any technique (including Nyquist sampling) it has conditions. If you satisfy the conditions- use good feature extractors for the signal that you are trying to sense- it will work well. If you don't, it won't. No technique extracts signals perfectly in anything outside of a theoretical model. Yes, I'm sure that there are theoretical signals that compressed sensing can extract perfectly.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What, like saying the signal is 100 MHz wide even if it's only 1 MHz wide? You can define things to be whatever you want, just like old-time astronomers were able to get the math of the sun orbiting the Earth to work. That doesn't mean that their equations were useful. - What does this statement mean? $\endgroup$
    – Dipan Mehta
    Commented May 18, 2012 at 14:28
  • $\begingroup$ @DipanMehta It means that you can artificially "expand" your signal to make it "sparse", but that is not a useful thing to do. $\endgroup$
    – Jim Clay
    Commented May 18, 2012 at 14:32
  • 3
    $\begingroup$ I would appreciate it if whoever downvoted the answer would give a reason why. $\endgroup$
    – Jim Clay
    Commented May 18, 2012 at 14:51
0
$\begingroup$

It is not like that it will work only for sparse signals, but you have find the domain in which the signal is nearly sparse (All naturally occurring signals will be sparse in some domain,except for random noise).In some domain the signal can be approximated with fewer measurements, all other measurements will be relatively small so you can safety discard them.

Improve this answer
$\endgroup$

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.