# compressed sensing on a non-sparse signal and Nyquist-Shannon sampling

Compressed sensing is often utilized on a sparse signal, allowing compression and sampling to be done in a lower rate.

What happens if compressed sensing is used on non-sparse signal and wireless signal? Will compressed sensing eventually produce a result basically equal to sampling Nyquist-Shannon theorem?

-
I don't understand this question: if you have a sparse signal, you will sample at Nyquist rate only the interesting part, so no violation – clabacchio May 24 '12 at 16:01
@clabacchio so, there is no violation of nyquist rate at all? – user25148 May 24 '12 at 16:04
It depends on how you sample and how the signal is, but in principle not – clabacchio May 24 '12 at 16:05

Compressed sensing is only used for sparse or compressible signals. Most of the time, you don't know where the interesting part (non sparse component) of your signal is so you have to resort to compressive sensing (CS). CS essentially performs some compressed measurements through the packing of 'normal" samples into what is called compressed sensing measurements. The number of measurement is generally much lower than the typical number of samples required by Shannon-Nyquist (hence the sub-Nyquist nickname)

Once these measurements have been taken, you have to reconstruction the full signal from the compressed measurements. In order to do so the reconstruction algorithm performs two steps: step 1: find out the location of the signal where that signal is non zero. step 2: find out the amplitude of that signal at the location identified in step 1

step 1 is really the hard part and we did not have proof of convergence for algorithms (greedy, Basis pursuit, and many more) until 2004. step 2 is easy when step 1 is solved. It generally is equivalent to Shannon Nyquist.

Hence clearly, using the methods of compressed sensing on non sparse signals is adding some extra level of complexity that is not needed. At that level, the answer to your questions are: Nothing. yes.

However, most signals are sparse in the sense that they have what is called structured sparsity. In wavelet decomposition for instance, one notices that the tree based decomposition of a signal is structured in that only certain "branches" are activated. Compressive sensing therefore can be applied to those cases with an improvement over Shanon-Nyquist, see for instance: http://nuit-blanche.blogspot.com/2012/05/bound-optimization-based-block-space.html For most man made signals, the answer to your questions are: If your signal is not sparse, does it have some structured sparsity ? if yes, then the answer to the second part of your question is No, it's better than Shannon-Nyquist.

-

There are two main reconstruction algorithms used: basis pursuit (BP) and orthogonal matched pursuit (OMP).

I read that "BP reconstruction algorithm out-performs OMP algorithms, due to the lack of true sparsity in real audio signals. Based on Signal Distortion Ratios (SDR) the discrete cosine transform (DCT) and a discrete wavelet transform (DWT) with Symmlet ﬁlters of order 8 is often used to test. DCT performs better than the DWT for all but the impulsive signal."

BP seeks to estimate the basis components simultaneously, whereas OMP does this in a component-by-component fashion.

-