By 苏剑林 | April 16, 2015
Suppose we are listening to a song. After listening, we have actually undergone a process where our ears received sound wave stimulation over a period of time, leading to changes in brain activity. This song—the sound wave over that duration—can be described by a function $f(t)$ of time $t$, where the interval of the function is finite, such as $t \in [0, T]$. Now, consider another scenario: we want to record the song we are singing using a computer. What kind of process is this? It is important to note that computer signals are discrete, while sound waves are continuous. Therefore, to record the song, the computer can only sample and record the signal. In principle, the more points collected, the more realistically our singing can be restored. However, there is a question: how many points are enough? In information theory, a famous "Sampling Theorem" (also known as the Shannon Sampling Theorem or Nyquist Sampling Theorem) tells us: Collecting only a finite number of sample points is sufficient to completely restore our input signal!
Restoring a continuous function from just a finite number of points? How is this achieved? Below we explain this theorem.
Given any function, generally speaking, we can perform a Fourier transform on it:
$$F(\omega)=\int_{-\infty}^{+\infty} f(t)e^{i\omega t}dt\tag{1}$$
Although the limits of integration are written as positive and negative infinity, since $f(t)$ is a function on a finite interval, the actual integration interval is finite. 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 we ask: what is the meaning of the Fourier transform? In fact, it is the transformation of the same function between the time domain and the frequency domain. In layman's terms, the original sound wave was described as a function of time; after the Fourier transform, the independent variable becomes frequency. That is, the transformed function tells us which frequencies of harmonics make up the original sound wave. This leads us to a crucial step: the resulting frequency range might be finite—meaning that outside a certain interval $[-W, W]$, $F(\omega)$ is identically zero.
Let us explain why this phenomenon occurs. The appearance of this phenomenon might be intrinsic—that is, the transformed function really is identically zero outside a certain interval $[-W, W]$. However, more often than not, it is another situation: the frequencies we can receive are finite. For example, the range of frequencies the human ear can hear is between 20 and 20,000 Hertz (Hz). So, when recording sound, why care about the parts of the sound lower than 20 Hz or higher than 20,000 Hz? Images are similar; the frequencies of electromagnetic waves we can see—visible light—also have a range. In other words, when recording a song, as long as it sounds exactly the same to us, we don't need to care if it is truly, physically identical. (If we used different equipment, such as an ultrasonic detector, we might discover differences from the original sound wave, but when listening to a song, who pays attention to the sensations of an ultrasonic detector?)
Based on the discussion above, we can truncate the integral in equation (2):
$$f(t)=\frac{1}{2\pi}\int_{-W}^{W} F(\omega)e^{-i\omega t}d\omega\tag{3}$$
Note that $F(\omega)$ is now only a function on $[-W, W]$. A function on a finite interval can be expanded into a Fourier series (note that this is a Fourier series, not a Fourier transform):
$$F(\omega)=\sum_{n=-\infty}^{+\infty}c_n e^{n\pi i\omega/W} \tag{4}$$
Next, substitute (4) into (3) and swap the summation and integration signs to get:
\begin{equation}
\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}
\end{equation}
Now we can determine each $c_n$. We see that $c_n$ is independent of $t$. We can take a specific value, namely let $t \to \frac{n\pi}{W}$, and then we can derive:
$$\frac{c_n W}{\pi}=f\left(\frac{n\pi}{W}\right)$$
Which 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. When $|n|$ is sufficiently large, $f\left(\frac{n\pi}{W}\right)=0$. In other words, the above equation is actually a finite sum!
Equation (6) is the entirety of the sampling theorem. It tells us that as long as we collect the values of a finite number of sample points $f\left(\frac{n\pi}{W}\right)$, we can completely restore $f(t)$ according to equation (6)—at least, it will be the same within the range of our perception. This is one of the things I learned from The Feynman Lectures on Computation.
Some details in the proof process may not be strictly rigorous, but if you are a reader from physics or engineering, I think it should be sufficient. If you are a mathematics enthusiast pursuing strictness, then please feel free to rigorize it.