PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (191)
Orphanage
Unclass'd
Unproven (496)
Corrections (10)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
[parent] proof of sampling theorem (Proof)

Set-up

Let $ w > 0$ be the (two-sided) bandwidth. The variable $ \xi$ below will denote frequency, and the variable $ t$ will denote time. (Both $ w$ and $ \xi$ are measured in cycles per unit time.)

Consider the space of functions:

$\displaystyle \mathcal{H}' = \{ g \in \mathbf{L}^2(\mathbb{R}) \colon g(\xi) = 0$    for almost all $\displaystyle \lvert\xi\rvert > w/2 \} $
which is clearly seen to be a complex Hilbert space with the usual inner product for $ \mathbf{L}^2(\mathbb{R})$.

Let $ \mathcal{F}$ denote the Fourier transform on $ \mathbf{L}^2(\mathbb{R})$, which is a unitary transform by Plancherel's theorem. So,

$\displaystyle \mathcal{H}= \{ f \in \mathbf{L}^2(\mathbb{R}) \colon (\mathcal{F}f)(\xi) = 0$    for almost all $\displaystyle \lvert\xi\rvert > w/2 \} = \mathcal{F}^{-1} \mathcal{H}' $
is also a Hilbert space.

Computation of orthonormal basis

One orthonormal basis for $ \mathcal{H}'$ consists of the usual Fourier basis functions on the interval $ [-w/2, w/2]$, extended to be zero on $ \mathbb{R}\setminus [-w/2, w/2]$:

$\displaystyle \phi_n(\xi) = \begin{cases} \frac{1}{\sqrt{w}} e^{-2 \pi i n \xi/... ...q w/2 \ 0\„ & \lvert\xi\rvert > w/2\„ \end{cases}\quad n \in \mathbb{Z} . $
Mapping these by $ \mathcal{F}^{-1}$ produces an orthonormal basis for $ \mathcal{H}$:
$\displaystyle (\mathcal{F}^{-1} \phi_n)(t)$ $\displaystyle = \frac{1}{\sqrt{w}} \int_{-w/2}^{w/2} e^{-2 \pi i n \xi/w} e^{2\pi i \xi t} d\xi$    
  $\displaystyle = \frac{1}{\sqrt{w}} \int_{-w/2}^{w/2} e^{2 \pi i \xi (t-n/w)} d\xi$    
  $\displaystyle = \frac{1}{\sqrt{w}} \bigl( w {\mathrm{sinc}}(w (t-n/w)) \bigr) = \sqrt{w} {\mathrm{sinc}}(wt-n)\„$    

where we have used the fact that the Fourier transform of $ t \mapsto w {\mathrm{sinc}}(wt)$ (normalized sinc function) is the rectangular box function of bandwidth $ w$, and vice versa.

Expansion by orthonormal basis

Given $ f \in \mathcal{H}$, let $ g = \mathcal{F}f \in \mathcal{H}'$. We can expand $ g$ in a Fourier series with respect to the basis $ \{ \phi_n \}$:

$\displaystyle g(\xi) = \sum_{n \in \mathbb{Z}} \langle g, \phi_n \rangle \phi_n(\xi)\„ $
with the infinite sum converging in $ \mathbf{L}^2(\mathbb{R})$. Taking $ \mathcal{F}^{-1}$ of both sides, we obtain:
$\displaystyle f(t) = (\mathcal{F}^{-1} g)(t) = \sum_{n \in \mathbb{Z}} \langle ... ... \sum_{n \in \mathbb{Z}} \langle g, \phi_n \rangle {\mathrm{sinc}}(wt-n) . $
Moreover,
$\displaystyle \langle g, \phi_n \rangle = \frac{1}{\sqrt{w}} \int_{-\infty}^\in... ...g)\Bigl( \frac{n}{w} \Bigr) = \frac{1}{\sqrt{w}} f\Bigl( \frac{n}{w} \Bigr) . $
(Since $ g$ is also in $ \mathbf{L}^1$, its inverse Fourier transform $ \mathcal{F}^{-1}g$ is a continuous function. Provided that we modify $ f$ on a set of measure zero, we can assume that $ f = \mathcal{F}^{-1} (\mathcal{F}f) = \mathcal{F}^{-1} g$ is continuous. So it is legal to talk about the pointwise values $ f(n/w)$.)

Result

Hence, we arrive at the representation:

$\displaystyle f(t) = \sum_{n \in \mathbb{Z}} f\Bigl( \frac{n}{w} \Bigr) {\mathrm{sinc}}(wt - n)\„ $
thereby reconstructing any $ f \in \mathcal{H}$ -- a square-integrable band-limited function -- from its samples at every time period of length $ 1/w$.

Uniform and absolute convergence of series

The infinite series for $ f$ converges in $ \mathbf{L}^2$ by construction, but in fact it also converges uniformly and absolutely. To see this, first note that by the Cauchy-Schwarz inequality,

$\displaystyle \sum_{n \in \mathbb{Z}} \lvert f(\tfrac{n}{w}) \rvert \lvert{... ...^{1/2} \Bigl( \sum_{n \in \mathbb{Z}} {\mathrm{sinc}}^2(wt -n) \Bigr)^{1/2} . $
The series $ \sum_n \lvert f(n/w)\rvert ^2$ converges by Parseval's theorem ( $ w^{-1/2} f(n/w)$ are the Fourier coefficients of $ g$). Also, the series $ \sum_n {\mathrm{sinc}}^2(wt-n)$ is uniformly bounded for all $ t \in \mathbb{R}$. To prove this, it suffices to restrict to $ t$ bounded inside $ [0, 1/w]$ as the function $ t \mapsto \sum_n {\mathrm{sinc}}^2(wt-n)$ is $ 1/w$-periodic; and then it becomes an easy estimate using the fact that $ \sum_n n^{-2} < \infty$. It follows that the series $ \sum_n \lvert f(n/w)\rvert \lvert{\mathrm{sinc}}(wt-n)\rvert $ is uniformly bounded for all $ t$, and its tail tends to zero uniformly in $ t$.

Illustrations

Figure: Reconstructing a Bessel function (of the first kind), using a $ {\mathrm{sinc}}$ series with $ n = -10, -9 \dotsc, 0, \dotsc, 10$. Theoretically exact bandwidth is $ w = 1/\pi \approx 0.32$.
\includegraphics{bessel.eps}
Figure: Effect of under-sampling and over-sampling beyond the actual bandwidth of the function
\includegraphics{bessel-extra.eps}
Figure: The basis functions $ {\mathrm{sinc}}(t)$, $ \tfrac12 {\mathrm{sinc}}(t\pm 1)$, $ \tfrac14 {\mathrm{sinc}}(t \pm 2)$
\includegraphics{basis.eps}



"proof of sampling theorem" is owned by stevecheng.
(view preamble)

View style:

See Also: Plancherel's theorem


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: bounded, Fourier coefficients, Parseval's theorem, Cauchy-Schwarz inequality, converges uniformly, converges, series, period, pointwise, measure zero, continuous function, inverse, sum, infinite, Fourier series, expand, sinc function, mapping, interval, functions, orthonormal basis, Plancherel's theorem, Transform, unitary, Fourier transform, inner product, Hilbert space, complex, space of functions, variable

This is version 10 of proof of sampling theorem, born on 2006-12-21, modified 2007-06-30.
Object id is 8650, canonical name is ProofOfSamplingTheorem.
Accessed 1505 times total.

Classification:
AMS MSC: 94A20 (Information and communication, circuits :: Communication, information :: Sampling theory)
 42A38 (Fourier analysis :: Fourier analysis in one variable :: Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)