I started the compressive sensing thread, but stuff happened and did not follow up. I did not visit EEVblog for a long time. My apologies. Somehow I just stumbled across this thread
Shannon *always* applies. Nyquist does or does not depending upon whether the signal is "sparse" in some basis.
In other words, if a signal is the sum of 4-5 sinusoids, it can be *exactly* recovered with far fewer than Nyquist samples. Doing this is computationally intensive, but L1 (least summed absolute error) solutions were shown by David Donoho of Stanford to be identical to the L0 (exhaustive search) solution. L0 is NP-Hard. The following is the most important paper in my view. You can very reasonably spend a few years of your life reading the work of Donoho and Emmanuel Candes. They have been staggeringly prolific.
https://statweb.stanford.edu/~donoho/Reports/2004/l1l0EquivCorrected.pdfThe reason that non-uniform sampling is so valuable is simple, but *very* difficult to grasp. I looked at the problem 10 years ago and gave up.
Simply put, the Fourier transform of a spike series in time is a spike series in frequency. A comb in one space is a comb in the other. This is why aliasing occurs with uniform sampling. But the Fourier transform of a random spike series in time is not a random spike series in frequency, so there is no aliasing in the conventional sense. Shannon still applies, but the difference between Donoho and Nyquist is pretty mind boggling. Even more so if you've been doing DSP for 30 years before you encounter Donoho.
As it turns out, in the real world much of the time the "signal" is sparse. The non-sparse part is random sensor noise. As a result sparse approximations can be used for noise removal in addition to compression.
It is not correct to assume that one must perform Nyquist sampling and the do compression as a separate step.
I consider Donoho's work the most important work in signal processing since Norbert Wiener in the 1940's. For over 60 years that was the gospel. Wavelet theory started eroding that in the late 80's, but was grossly misrepresented by many people. I was caustically sarcastic about wavelet theory for a long time. I was wrong. My objections to the claims about frequency resolution were valid, but there was more to wavelet theory than I realized. Having read Mallat's 3rd edition cover to cover, I think I have done appropriate penance.
For what I find a mind boggling example, search on:
"Single-Pixel Imaging via Compressive Sampling"
For reasons known only to the illuminati at google, I can't get a link that doesn't pass through google. There's an IEEE paper which is generally paywalled and then a longer version at citeseerx.psu.edu