The Shannon-Whitaker Sampling Theorem 1.1 2007/07/16 12:20:42.648 GMT-5 2007/09/21 23:12:30.183 GMT-5 Michael A Lexa amlexa@rice.edu Ronald A. DeVore devore@math.sc.edu Elchin Asgarov deoxman@gmail.com Raymond Wagner rwagner@rice.edu Richard G. Baraniuk richb@rice.edu Michael A Lexa amlexa@rice.edu Mark Davenport md@rice.edu Ronald A. DeVore devore@math.sc.edu 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 and define it in the following way: B A :={f∈L 2 (R):f ^(ω)=0,|ω|≥Aπ}. Here, the Fourier transform of f is defined by f ^(ω):=1 2π∫ R f(t)e -iωt dt. This formula holds for any f∈L 1 and extends easily to f∈L 2 via limits. The inversion of the Fourier transform is given by f(t):=1 2π∫ R f ^(ω)e ωt dω. Shannon-Whitaker Sampling Theorem If f∈B A , then f can be uniquely determined by the uniformly spaced samples fn A and in fact, is given by f(t)=1 2π∑ n∈Z fn A sinc (π( At -n)), where sinc (t)=sint t. It is enough to consider A=1, since all other cases can be reduced to this through a simple change of variables. Because f∈B A=1 , the Fourier inversion formula takes the form f(t)=1 2π∫ -π π f ^(ω)e iωt dω. Define F(ω) as the 2π periodization of f ^, F(ω):=∑ n∈Z f ^(ω-2nπ). Because F(ω) is periodic, it admits a Fourier series representation F(ω)=∑ n∈Z c n e -inω , where the Fourier coefficients c n given by c n =1 2π∫ -π π F(ω)e inω dω=1 2π∫ -π π f ^(ω)e inω dω. By comparing () with (), we conclude that c n =1 2πf(n). Therefore by plugging () back into (), we have that F(ω)=1 2π∑ n∈Z f(n)e -inω . Now, because f ^(ω)=F(ω)χ [-π,π] =1 2π∑ n∈Z f(n)e -inω χ [-π,π] , and because of the facts that F(χ [-π,π] )=1 2π sinc (πω)andF(g(t-n))=e -inω F(g(t)), we conclude f(t)=∑ n∈Z f(n) sinc (π(t-n)). Comments: (Good news) The set { sinc (π(t-n))} n∈Z is an orthogonal system and therefore, has the property that the L 2 norm of the function and its Fourier coefficients are related by, ∥f∥ L 2 2 =2π∑ n∈Z |f(n)| 2 (Bad news) The representation of f in terms of sinc functions is not a stable representation, i.e. ∑ n∈Z | sinc (π(t-n))|≈∑ n∈Z 1 |t-n|+1→divergences