Regarding the Nyquist Criterion

I recently read that with compressive Sensing it possible to sample the signal at a rate lesser than that suggested by Nyquist Criterion. However, I am still not getting how this is possible. Can someone suggest an intuitive way of understanding this concept of sampling at lower rates? And if this is possible, do modern communication techniques use this concept?

• @PaulR I do not believe that the link here is related to the question. The linked question links to equivalent-time sampling, whereas compressive sensing is is a new paradigm altogether that exploits sparsity in some domain. From a practitioners viewpoint though, knowing all forms would be helpful. – Tarin Ziyaee Aug 14 '13 at 14:50
• @user4619: OK - thanks - I hadn't heard of compressive sampling before - I'll delete my comment. – Paul R Aug 14 '13 at 15:32

The Nyquist criteria refers not to the frequency, but to the bandwidth, which is related to information density in a signal. A very high frequency signal, of approximately known frequency, with a sufficiently small bandwidth, will still be aliased or folded down with baseband frequencies by undersampling. But if the bandwidth (or other known characteristics) of the signal is known to rule out other aliased frequencies (such as the non-existence of baseband spectrum content), that knowledge in conjunction with the undersampled samples may still provide enough information to reconstruct the signal.

Yes, it is possible to sample and reconstruct a signal at sampling frequency lower than the Nyquist Criteria. For that, the signal has to be sparse in some representation basis. Then it is absolutely possible to reconstruct the signal with a certain probability in having an error in reconstruction. Please refer to Terrence Tao's work in this regard.

As far as I know, CS ( Compressive Sampling ) has already been used for recovering MRI images, and also EPFL has done real-time CS sampling and reconstruction of ECG signals. Please refer to Igor Carron's blog for more such applications.

• Could you suggest an appropriate source for researching Tao's work? – Speedy Aug 15 '13 at 8:33
• You can search for Dr.Tao's work in this link – sm176357 Aug 15 '13 at 10:18

As @hotpaw2 explains, the Nyquist criterion has to do with the bandwidth of the signal, not the highest frequency as such. But if you do not know the exact frequency of the sampled signal (e.g. 40Hz) and only know that it is somewhere in a frequency range (e.g. 0-1000Hz), you in principle have to sample above 2000Hz (according to Nyquist) in order to be sure that you sample the signal correctly. The essence of compressed sensing is that you can still sample this signal only knowing the frequency range (the 0-1000Hz), but at a significantly lower sampling rate (perhaps 200Hz).

This is generally done by "mixing together" what you would think of as the corresponding Nyquist-rate samples before actually sampling them, forming linear combinations of the Nyquist-rate samples and then only sampling a few of these combinations. Strikingly, the theory even suggests that it is best to do this combination randomly.

To get back to (reconstruct) a Nyquist-rate representation of the signal, you need to solve a non-linear optimization problem that "disentangles" the mentioned sampled linear combinations.

Regarding the second part of your question: employing compressed sensing in communication systems is still at a fairly immature research level. What we have found in our research at Aalborg University (http://vbn.aau.dk/en/persons/thomas-arildsen%28334e2ddc-15ec-4123-82b7-de85132ae371%29/publications.html) is that it is very hard to implement in a useful way directly on the communication signals, but it is also being investigated, e.g. at the network level or in channel modelling.

EDIT: Regarding @talasila's comment, the classic example of a non-linear optimization problem reconstructing the signal is (9) or (11) in http://www-stat.stanford.edu/~candes/papers/spm-robustcs-v05.pdf - (the noiseless or noisy case, respectively). In general, the mixing of the samples is just multiplication of a vector of the Nyquist-rate samples by a fat matrix obeying certain properties (see the above paper by Candès and Wakin). As an example of this operation implemented in hardware, see for example http://www.ece.rice.edu/~jnl5066/papers/DCAS2006_randmod.pdf (random demodulator).

• Can you suggest any simple references showing mixing together of nyqvist rate samples and then how it is reconstructed by solving a non linear optimization problem. – Karan Talasila Aug 27 '13 at 4:32
• @talasila, I added more info to my answer. – Thomas Arildsen Aug 28 '13 at 20:15

Signal sampled at Nyquist frequency can be perfectly reconstructed. But that does not mean that the information content of that signal is always evenly distributed across the bandwidth (which is limited by Nyquist frequency). Compressed sensing tries to exploit this trade off. Signal encoded with compressed sensing is able to encode enough information to be able to reconstruct the desired signal which may or may not be as perfect as signal encoded by sampling at Nyquist frequency.

I quote from Wikipedia article on Compressed Sensing. "At first glance, compressed sensing, because it depends on the sparsity of the signal in question and not its highest frequency, might seem to violate the sampling theorem. This is a misconception, because the sampling theorem guaranties perfect reconstruction given sufficient, not necessary, conditions. A sampling method different from the classical fixed-rate sampling therefore can not "violate" the sampling theorem. Sparse signals with high frequency components can be highly under-sampled using compressed sensing compared to classical fixed-rate sampling."

First, the Nyquist Criterion is a sufficient condition for a subclass of signals. If a continuous signal is band limited, with appropriate sampling, the discretized version possesses all the information (analysis) and the continuous can be recover perfectly from discrete samples (synthesis). So, it is NOT a necessary condition, and can be overcome in some cases.

In compressive sensing, or sparse sampling in general, there is often a probabilistic interpretation. Under some conditions, the sensed signals are recovered with high probability, potentialy not perfectly.

One line of theory not mentioned here provides some interesting insights: FRI for Finite Rate of Innovation. It deals with signals which, in a unit of time, can be represented by a parametric model with $K$ parameters, i.e. a form of sparse representation. They can be Diracs or piecewise polynomials, and also include data represented as a sum of sines.

What I like in this setting is two-fold:

1. It deals with continuous signals,
2. It generalizes Nyquist sampling by providing reconstruction from $N=2K$ measurements.

It basically says that the number of required samples can be related to (twice) the number of degrees of freedom in the description of a signal.

A recent account is given in Reconstruction of Finite Rate of Innovation Signals with Model-Fitting Approach, 2015.