# Compressed sensing and Logan's Theorem

The authors of the book, Data Driven Science & Engineering Book webpage, also have a Youtube Channel. ne of the videos on compressed has the title "Beating Nyquist with Compressed Sensing." The video shows an example of random sampling of sinusoids which are sparse in the FT, and reconstructing the original signal with $$l_1$$ norm. As per the title, the first impression is that there is a violation of the sampling theorem but Wikipedia Link, History says the following:

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

Note that compressive sensing has nothing to do with aliasing and then figuring out the actual frequencies. In some research papers in the nuclear magnetic resonance field, Logan's theorem is used to provide a justification Ref:

"Logan’s Theorem states that perfect recovery of the spectrum is possible even from incomplete and noisy measurements by minimizing the $$l_1$$ norm of the spectrum while ensuring consistency with the measured data, provided that certain conditions on sparsity and noise level are met, and the spectrum is band-limited." B. F. Logan. Properties of high-pass signals. (Ph.D. thesis, Department of Electrical Engineering, Columbia University, 1965).

I got hold of the thesis copy from Columbia University (don't have it anymore) but could not find any explicit statement. The thesis does not exist online. The question is

(i) Is classical sampling theorem only valid for uniformly sampled data?

(ii) Has anyone else encountered this Logan's theorem in some other form but relevant to compressive sensing?

Note: It is not related to Logan's 1977, Information in the Zero Crossings of Bandpass-Signals. The thesis is not available online anywhere.

We should at least read the original sources (Shannon 1949, Communication in the Presence of Noise):

Theorem 1: If a function contains no frequencies higher than $$W$$ cps, it is completely determined by giving its ordinates at a series of points spaced 1/2 $$W$$ seconds apart.

(cps is "cycles per second", so "Hertz" for harmonic oscillations).

Not more, not less.

So, yes, what that wikipedia comment says in many words could also be said as

just because we need so and so many regular samples to reconstruct any signal that has no frequencies outside some limit doesn't mean there's not some signals that can be done with less.

(i) Is classical sampling theorem only valid for uniformly sampled data?

See above, including the wikipedia article you cite.

(ii) Has anyone else encountered this Logan's theorem in some other form but relevant to compressive sensing?

"Logan's theorem" seems to me to be a less common used term. I guess.

I can't read the full text of the article you link to, nor can I get access to the cited PhD thesis anywhere, but if I have to take a guess, this refers to the same principles explained in Logan 1977, Information in the Zero Crossings of Bandpass-Signals, which basically says that, ignoring all zeros that are inflection points of the signal (more precisely, all zeros that are both in the signal and its Hilbert transform), any signal band-limited to one octave or less will be reconstructable up to a constant factor only from the positions of zero-crossings.

So, no, I haven't encountered the statement in the form you mention it; the "up to a factor" does kind of conflict with the "perfect recovery", so I suspect there is some weight carried around by providing "certain conditions on sparsity and noise level", which you really need to understand before transferring this to any other field.

• Yes, thesis is not online. I had requested it from Columbia University. The zero crossings of bandpass signals is not related to modern compressed sensing. It is only one set of authors who call it "Logan's theorem". It could be an eponymous theorem. May be it is appropriate to contact the authors rather.
– ACR
Commented Jul 1 at 18:46