The Sampling Theorem: Reconstructing an Entire Function from Finitely Many Points

采样定理：有限个点构建出整个函数 苏剑林 · 2015-04-16 · Mathematics integral Fourier sampling

Suppose we're listening to a song. What happens after we've finished listening to it is essentially this: our ears receive a stimulus from sound waves over a period of time, which in turn induces changes in brain activity. This song — that is, the sound wave over that stretch of time — can be described by a function $f(t)$ of time $t$, and this function has a finite domain, say $t\in[0,T]$. Now consider another scenario — we want to use a computer to record ourselves singing. What kind of process is this? Note that the computer's signal is discretized, while the sound wave is continuous. So, for the computer to record the song, it can only sample the signal at discrete points. In principle, the more points we sample, the more faithfully we can reconstruct our singing. But there's a question: how many points are enough? In information theory, a famous result — the "sampling theorem" (also known as the Shannon sampling theorem, or the Nyquist sampling theorem) — tells us: it suffices to collect finitely many sample points in order to completely reconstruct our input signal!

Collecting finitely many points is enough to reconstruct a continuous function? How is this possible? Let's explain this theorem below.

Given an arbitrary function, in general we can take its Fourier transform:

$$F(\omega)=\int_{-\infty}^{+\infty} f(t)e^{i\omega t}dt\tag{1}$$

Although we've written the limits of integration as plus and minus infinity, since $f(t)$ is a function defined on a finite interval, the integration range above is in fact finite. Moreover, the inverse transform of the above is

$$f(t)=\frac{1}{2\pi}\int_{-\infty}^{+\infty} F(\omega)e^{-i\omega t}d\omega\tag{2}$$

Now let's ask: what is the meaning of the Fourier transform? In fact, it's a way of expressing the same function in the time domain and the frequency domain interchangeably. Colloquially speaking, the original sound wave is described as a function of time; after the Fourier transform, its independent variable becomes frequency, i.e. the transformed function tells us which frequencies of simple harmonic waves are being superposed to make up the original sound wave. And now we arrive at the crucial step: the range of frequencies after transformation may well be finite, meaning that outside some interval $[-W,W]$, $F(\omega)$ is identically zero.

Let's explain why this phenomenon occurs. This could, in principle, be an essential property — i.e. the transformed function really is identically zero $F(\omega)$ outside some interval $[-W,W]$ — but more often, it's due to a different reason: the range of frequencies we can perceive is limited. For instance, the frequencies our ears can hear lie between 20 Hz and 20,000 Hz. So when recording sound, why should we care about the parts below 20 Hz or above 20,000 Hz? The same goes for images — the frequencies of electromagnetic waves we can see, i.e. visible light, also have a limited range. In other words, when we record a song, all that matters is that it sounds identical to us — it doesn't matter whether it's actually identical. (If we switched to different equipment, say an ultrasonic detector, we might well find discrepancies from the original sound wave, but when listening to a song, who cares what an ultrasonic detector would perceive?)

Based on the discussion above, we can truncate the integral in $(2)$:

$$f(t)=\frac{1}{2\pi}\int_{-W}^{W} F(\omega)e^{-i\omega t}d\omega\tag{3}$$

Note that now $F(\omega)$ is simply a function on $[-W,W]$, and a function defined on a finite interval can be expanded as a Fourier series (note: a Fourier series, not a Fourier transform):

$$F(\omega)=\sum_{n=-\infty}^{+\infty}c_n e^{n\pi i\omega/W} \tag{4}$$

Substituting $(4)$ into $(3)$ and swapping the order of the integral and the summation, we get

$$\begin{aligned}f(t)=&\frac{1}{2\pi}\int_{-W}^{W} \left(\sum_{n=-\infty}^{+\infty}c_n e^{n\pi i\omega/W}\right)e^{-i\omega t}d\omega\\ =&\frac{1}{2\pi}\sum_{n=-\infty}^{+\infty}c_n\int_{-W}^{W} e^{n\pi i\omega/W-i\omega t}d\omega\\ =&\frac{1}{2\pi}\sum_{n=-\infty}^{+\infty}c_n\left.\frac{e^{n\pi i\omega/W-i\omega t}}{i(n\pi /W- t)}\right|_{-W}^W\\ =&\frac{1}{2\pi}\sum_{n=-\infty}^{+\infty}c_n\frac{2\sin(n\pi -W t)}{n\pi /W- t}\\ =&\sum_{n=-\infty}^{+\infty}\left(\frac{c_n W}{\pi}\right)\frac{\sin(n\pi -W t)}{n\pi - Wt} \end{aligned}\tag{5}$$

Now we can determine each $c_n$. We notice that $c_n$ has nothing to do with $t$, so we can pick a special value — namely, take $t\to \frac{n\pi}{W}$ — and then derive:

$$\frac{c_n W}{\pi}=f\left(\frac{n\pi}{W}\right)$$

that is,

$$f(t)=\sum_{n=-\infty}^{+\infty}f\left(\frac{n\pi}{W}\right)\frac{\sin(n\pi -W t)}{n\pi - Wt}\tag{6}$$

Notice that $f(t)$ is defined on a finite interval, so once $|n|$ is large enough, $f\left(\frac{n\pi}{W}\right)=0$ — in other words, the sum above is actually a sum over finitely many terms!

Equation $(6)$ is the whole content of the sampling theorem: it tells us that as long as we collect the values $f\left(\frac{n\pi}{W}\right)$ at finitely many sample points, we can completely reconstruct $f(t)$ using formula $(6)$ — at least, identical within the range that we're able to perceive. This is one of the things I learned from Feynman's Computation Course.

Some details in the derivation may not be entirely rigorous, but if you're a reader from a physics or engineering background, I think this should be sufficient; and if you're a mathematics enthusiast who craves full rigor, then please go ahead and make it rigorous yourself.