The classical theory behind the encoding analog signals into bit
streams and decoding bit streams back into signals, rests on a famous sampling theorem
which is typically refereed to as the
Shannon-Whitaker Sampling Theorem. In this course, this sampling
theory will serve as a benchmark to which we shall compare the new
theory of compressed sensing.
To introduce the Shannon-Whitaker theory, we first define the class
of bandlimited signals. A bandlimited signal is a signal
whose Fourier transform only has finite support. We shall denote
this class as B A B A and define it in the following way:
B A :={f∈L 2 (R):f ^(ω)=0,|ω|≥Aπ}.B A :={f∈L 2 (R):f ^(ω)=0,|ω|≥Aπ}.(1)
Here, the Fourier transform of
ff is defined by
f ^(ω):=1 2π∫ R f(t)e -iωt dt.
f ^(ω):=1 2π∫ R f(t)e -iωt dt.(2)
This formula holds for any
f∈L 1 f∈L 1 and extends easily to
f∈L 2 f∈L 2 via limits.
The inversion of the Fourier transform is given by
f(t):=1 2π∫ R f ^(ω)e ωt dω.f(t):=1 2π∫ R f ^(ω)e ωt dω.(3)
If f∈B A f∈B A , then ff can be uniquely determined by the
uniformly spaced samples fn Afn A and in fact,
is given by
f(t)=1 2π∑ n∈Z fn A sinc (π( At -n)),f(t)=1 2π∑ n∈Z fn A sinc (π( At -n)),(4)
where
sinc (t)=sint t sinc (t)=sint t.
It is enough to consider A=1A=1, since all other cases can be reduced to this through a simple change of variables. Because f∈B A=1 f∈B A=1 , the Fourier inversion formula takes the
form
f(t)=1 2π∫ -π π f ^(ω)e iωt dω.f(t)=1 2π∫ -π π f ^(ω)e iωt dω.(5)
Define
F(ω)F(ω) as the
2π2π periodization of
f ^f ^,
F(ω):=∑ n∈Z f ^(ω-2nπ).F(ω):=∑ n∈Z f ^(ω-2nπ).(6)
Because
F(ω)F(ω) is periodic, it admits a Fourier series
representation
F(ω)=∑ n∈Z c n e -inω ,F(ω)=∑ n∈Z c n e -inω ,(7)
where the Fourier coefficients
c n c n given by
c n =1 2π∫ -π π F(ω)e inω dω=1 2π∫ -π π f ^(ω)e inω dω.c n =1 2π∫ -π π F(ω)e inω dω=1 2π∫ -π π f ^(ω)e inω dω.(8)
By comparing (
Equation 8) with (
Equation 5), we
conclude that
c n =1 2πf(n).c n =1 2πf(n).(9)
Therefore by plugging (
Equation 9) back
into (
Equation 6), we have that
F(ω)=1 2π∑ n∈Z f(n)e -inω .F(ω)=1 2π∑ n∈Z f(n)e -inω .(10)
Now, because
f ^(ω)=F(ω)χ [-π,π] =1 2π∑ n∈Z f(n)e -inω χ [-π,π] ,f ^(ω)=F(ω)χ [-π,π] =1 2π∑ n∈Z f(n)e -inω χ [-π,π] ,(11)
and because of the facts that
F(χ [-π,π] )=1 2π sinc (πω)andF(g(t-n))=e -inω F(g(t)),F(χ [-π,π] )=1 2π sinc (πω)andF(g(t-n))=e -inω F(g(t)),(12)
we conclude
f(t)=∑ n∈Z f(n) sinc (π(t-n)).f(t)=∑ n∈Z f(n) sinc (π(t-n)).(13)
Comments:
- (Good news) The set { sinc (π(t-n))} n∈Z { sinc (π(t-n))} n∈Z is an orthogonal system and therefore, has the property that the L 2 L 2 norm of the function and its Fourier coefficients are related by,
∥f∥ L 2 2 =2π∑ n∈Z |f(n)| 2 ∥f∥ L 2 2 =2π∑ n∈Z |f(n)| 2 (14)
- (Bad news) The representation of ff in terms of sinc functions is not a stable representation, i.e.
∑ n∈Z | sinc (π(t-n))|≈∑ n∈Z 1 |t-n|+1→divergences∑ n∈Z | sinc (π(t-n))|≈∑ n∈Z 1 |t-n|+1→divergences(15)
