Convolution theorem for Fourier transforms, Poisson summation formula

Convolution Theorem for Fourier Transforms

The convolution theorem is a fundamental result in Fourier analysis that connects the Fourier transform of a convolution of two functions with the product of their individual Fourier transforms. This theorem is incredibly useful for solving differential equations, signal processing, and various other applications where operations like filtering or system response are analyzed.

Let's define the convolution of two functions, $f(x)$ and $g(x)$, denoted by $(f * g)(x)$. The convolution is defined as:

$(f * g)(x) = \int_{-\infty}^{\infty} f(\tau) g(x - \tau) d\tau$

This integral represents a 'weighted average' of the function $f(\tau)$ as it's 'swept' across by the 'flipped' and 'shifted' version of $g(x - \tau)$.

Now, let's consider the Fourier Transforms of $f(x)$ and $g(x)$. We'll use the common definition of the Fourier Transform as:

$\mathcal{F}\{f(x)\}(k) = F(k) = \int_{-\infty}^{\infty} f(x) e^{-ikx} dx$

And similarly for $g(x)$:

$\mathcal{F}\{g(x)\}(k) = G(k) = \int_{-\infty}^{\infty} g(x) e^{-ikx} dx$

The convolution theorem states that the Fourier Transform of the convolution of two functions is the product of their individual Fourier Transforms. Mathematically:

$\mathcal{F}\{(f * g)(x)\}(k) = F(k) G(k)$

This is a remarkable simplification. Instead of computing the Fourier Transform of a potentially complex convolution integral, we can simply multiply the Fourier Transforms of the individual functions.

Proof of the Convolution Theorem

Let's prove this theorem. We start by taking the Fourier Transform of the convolution $(f * g)(x)$:

$\mathcal{F}\{(f * g)(x)\}(k) = \int_{-\infty}^{\infty} \left( \int_{-\infty}^{\infty} f(\tau) g(x - \tau) d\tau \right) e^{-ikx} dx$

We can interchange the order of integration (Fubini's Theorem, assuming suitable conditions on $f$ and $g$):

$= \int_{-\infty}^{\infty} f(\tau) \left( \int_{-\infty}^{\infty} g(x - \tau) e^{-ikx} dx \right) d\tau$

Now, let's focus on the inner integral: $\int_{-\infty}^{\infty} g(x - \tau) e^{-ikx} dx$.

Let $u = x - \tau$. Then $x = u + \tau$, and $dx = du$. Substituting these into the inner integral:

$\int_{-\infty}^{\infty} g(u) e^{-ik(u + \tau)} du = \int_{-\infty}^{\infty} g(u) e^{-iku} e^{-ik\tau} du$

Since $e^{-ik\tau}$ is a constant with respect to the integration variable $u$, we can pull it out:

$= e^{-ik\tau} \int_{-\infty}^{\infty} g(u) e^{-iku} du$

The integral $\int_{-\infty}^{\infty} g(u) e^{-iku} du$ is simply the Fourier Transform of $g(u)$, which is $G(k)$. So, the inner integral becomes:

$= e^{-ik\tau} G(k)$

Now, substitute this back into the expression for the Fourier Transform of the convolution:

$\mathcal{F}\{(f * g)(x)\}(k) = \int_{-\infty}^{\infty} f(\tau) \left( e^{-ik\tau} G(k) \right) d\tau$

Since $G(k)$ is independent of $\tau$, we can pull it out of the integral:

$= G(k) \int_{-\infty}^{\infty} f(\tau) e^{-ik\tau} d\tau$

The remaining integral $\int_{-\infty}^{\infty} f(\tau) e^{-ik\tau} d\tau$ is the Fourier Transform of $f(\tau)$, which is $F(k)$. Therefore:

$\mathcal{F}\{(f * g)(x)\}(k) = G(k) F(k)$

This completes the proof.

Properties and Applications

The convolution theorem is crucial because it transforms a convolution operation in the time (or spatial) domain into a simple multiplication in the frequency domain. This is often computationally much easier.

One of the most important applications is in solving linear time-invariant (LTI) systems. If $f(x)$ represents the input signal and $h(x)$ represents the impulse response of an LTI system, then the output signal $y(x)$ is given by the convolution:

$y(x) = (f * h)(x)$

Taking the Fourier Transform of both sides:

$Y(k) = \mathcal{F}\{y(x)\}(k)$

$H(k) = \mathcal{F}\{h(x)\}(k)$ (This is often called the frequency response of the system)

$F(k) = \mathcal{F}\{f(x)\}(k)$

By the convolution theorem, $Y(k) = F(k) H(k)$. This means that the Fourier Transform of the output is the product of the Fourier Transform of the input and the frequency response of the system. To find the output signal $y(x)$, we would then compute the inverse Fourier Transform of $Y(k)$.

This is widely used in signal processing for filtering. For example, to apply a low-pass filter to a signal, we convolve the signal with the impulse response of the low-pass filter. In the frequency domain, this corresponds to multiplying the signal's Fourier Transform by the filter's frequency response, effectively attenuating high frequencies.

Example: Fourier Transform of a Gaussian

Let's consider the convolution of two Gaussian functions. A Gaussian function is of the form $f(x) = e^{-ax^2}$. It's known that the Fourier Transform of a Gaussian is also a Gaussian.

Let $f(x) = e^{-ax^2}$ and $g(x) = e^{-bx^2}$.

The Fourier Transforms are:

$F(k) = \sqrt{\frac{\pi}{a}} e^{-\frac{k^2}{4a}}$

$G(k) = \sqrt{\frac{\pi}{b}} e^{-\frac{k^2}{4b}}$

According to the convolution theorem, the Fourier Transform of $(f * g)(x)$ is $F(k)G(k)$:

$\mathcal{F}\{(f * g)(x)\}(k) = \left(\sqrt{\frac{\pi}{a}} e^{-\frac{k^2}{4a}}\right) \left(\sqrt{\frac{\pi}{b}} e^{-\frac{k^2}{4b}}\right)$

$= \sqrt{\frac{\pi^2}{ab}} e^{-\frac{k^2}{4a} - \frac{k^2}{4b}} = \frac{\pi}{\sqrt{ab}} e^{-k^2 \left(\frac{1}{4a} + \frac{1}{4b}\right)}$

$= \frac{\pi}{\sqrt{ab}} e^{-k^2 \left(\frac{a+b}{4ab}\right)}$

This result can then be inverted to find the explicit form of the convolution of two Gaussians without directly evaluating the convolution integral, which would be more challenging.

Poisson Summation Formula

The Poisson summation formula is a powerful identity that relates the sum of a function's values at integer points to the sum of its Fourier transform's values at integer points. It provides a bridge between a function and its frequency-domain representation in a discrete sense.

Let $f(x)$ be a function. Its Fourier Transform is $F(k) = \int_{-\infty}^{\infty} f(x) e^{-ikx} dx$.

The Poisson summation formula states:

$\sum_{n=-\infty}^{\infty} f(n) = \sum_{m=-\infty}^{\infty} F(2\pi m)$

Here, the left side is the sum of the function $f(x)$ evaluated at all integers $n$. The right side is the sum of the Fourier Transform of $f(x)$, $F(k)$, evaluated at integer multiples of $2\pi$, specifically $m = 0, \pm 1, \pm 2, \ldots$.

This formula holds true under certain conditions, typically that $f(x)$ and its Fourier transform $F(k)$ are absolutely integrable, and that certain related functions decay sufficiently rapidly at infinity.

Understanding the Formula

Consider the function $g(x) = \sum_{n=-\infty}^{\infty} f(x + n)$. This function is periodic with period 1.

The Fourier series of a periodic function $g(x)$ with period $T$ is given by:

$g(x) = \sum_{m=-\infty}^{\infty} c_m e^{i \frac{2\pi m x}{T}}$

where the Fourier coefficients are $c_m = \frac{1}{T} \int_{0}^{T} g(x) e^{-i \frac{2\pi m x}{T}} dx$.

In our case, the period $T=1$. So, $g(x) = \sum_{m=-\infty}^{\infty} c_m e^{i 2\pi m x}$.

The coefficients are $c_m = \int_{0}^{1} g(x) e^{-i 2\pi m x} dx$.

Substitute $g(x) = \sum_{n=-\infty}^{\infty} f(x + n)$ into the expression for $c_m$:

$c_m = \int_{0}^{1} \left( \sum_{n=-\infty}^{\infty} f(x + n) \right) e^{-i 2\pi m x} dx$

Assuming we can interchange summation and integration:

$c_m = \sum_{n=-\infty}^{\infty} \int_{0}^{1} f(x + n) e^{-i 2\pi m x} dx$

Let $u = x + n$. Then $x = u - n$, and $dx = du$. When $x=0$, $u=n$. When $x=1$, $u=n+1$.

The integral becomes $\int_{n}^{n+1} f(u) e^{-i 2\pi m (u - n)} du = \int_{n}^{n+1} f(u) e^{-i 2\pi m u} e^{i 2\pi m n} du$.

Since $m$ and $n$ are integers, $e^{i 2\pi m n} = (\cos(2\pi mn) + i \sin(2\pi mn)) = 1$.

So, the integral is $\int_{n}^{n+1} f(u) e^{-i 2\pi m u} du$.

Summing over all $n$:

$c_m = \sum_{n=-\infty}^{\infty} \int_{n}^{n+1} f(u) e^{-i 2\pi m u} du = \int_{-\infty}^{\infty} f(u) e^{-i 2\pi m u} du$.

This integral is precisely the Fourier Transform of $f(u)$ evaluated at $k = 2\pi m$. So, $c_m = F(2\pi m)$.

Now, let's evaluate $g(x)$ at $x=0$.

$g(0) = \sum_{n=-\infty}^{\infty} f(0 + n) = \sum_{n=-\infty}^{\infty} f(n)$.

From the Fourier series expansion, $g(0) = \sum_{m=-\infty}^{\infty} c_m e^{i 2\pi m (0)} = \sum_{m=-\infty}^{\infty} c_m$.

Substituting $c_m = F(2\pi m)$:

$g(0) = \sum_{m=-\infty}^{\infty} F(2\pi m)$.

Equating the two expressions for $g(0)$:

$\sum_{n=-\infty}^{\infty} f(n) = \sum_{m=-\infty}^{\infty} F(2\pi m)$.

This is the Poisson summation formula.

Applications of the Poisson Summation Formula

The Poisson summation formula is a fundamental tool in various fields, including number theory, signal processing, and physics.

1. Number Theory: It is used to evaluate sums involving number-theoretic functions. For instance, it can be used to derive properties of the Riemann zeta function.

2. Signal Processing: It relates the discrete-time Fourier transform (DTFT) to the continuous-time Fourier transform (CTFT). If we consider a sampled signal $f_s(t) = \sum_{n=-\infty}^{\infty} f(nT) \delta(t - nT)$, its Fourier Transform is related to the original function's Fourier Transform $F(\omega)$ by:

$\mathcal{F}\{f_s(t)\}(\omega) = \frac{1}{T} \sum_{m=-\infty}^{\infty} F\left(\frac{\omega - 2\pi m}{T}\right)$.

The Poisson summation formula essentially shows that summing a function $f(t)$ at integer points is equivalent to summing its Fourier transform $F(\nu)$ at integer multiples of the frequency unit. If we consider $f(t)$ and its Fourier transform $F(\nu)$, the formula relates $\sum f(n)$ to $\sum F(2\pi m)$.

3. Physics: It appears in solid-state physics when dealing with crystal lattices and reciprocal lattices. The structure factor of a crystal lattice, which describes how X-rays scatter from the lattice, can be analyzed using this formula. The formula connects the spatial arrangement of atoms (direct lattice) to their arrangement in momentum space (reciprocal lattice).

4. Calculating Integrals: It can be used to evaluate certain definite integrals by transforming them into sums, or vice-versa.

Example: Sum of $e^{-a n^2}$

Let's use the Poisson summation formula to evaluate the sum $S = \sum_{n=-\infty}^{\infty} e^{-a n^2}$, where $a > 0$.

Here, $f(x) = e^{-ax^2}$. We need its Fourier Transform $F(k)$.

We know that the Fourier Transform of $e^{-cx^2}$ is $\sqrt{\frac{\pi}{c}} e^{-\frac{k^2}{4c}}$.

So, for $f(x) = e^{-ax^2}$, its Fourier Transform is $F(k) = \sqrt{\frac{\pi}{a}} e^{-\frac{k^2}{4a}}$.

According to the Poisson summation formula:

$\sum_{n=-\infty}^{\infty} f(n) = \sum_{m=-\infty}^{\infty} F(2\pi m)$

The left side is the sum we want to evaluate: $S = \sum_{n=-\infty}^{\infty} e^{-a n^2}$.

The right side is:

$\sum_{m=-\infty}^{\infty} \sqrt{\frac{\pi}{a}} e^{-\frac{(2\pi m)^2}{4a}} = \sqrt{\frac{\pi}{a}} \sum_{m=-\infty}^{\infty} e^{-\frac{4\pi^2 m^2}{4a}} = \sqrt{\frac{\pi}{a}} \sum_{m=-\infty}^{\infty} e^{-\frac{\pi^2 m^2}{a}}$

Thus, the Poisson summation formula gives us the identity:

$\sum_{n=-\infty}^{\infty} e^{-a n^2} = \sqrt{\frac{\pi}{a}} \sum_{m=-\infty}^{\infty} e^{-\frac{\pi^2 m^2}{a}}$

This identity is known as Jacobi's theta function identity. It shows a remarkable relationship between a sum and another sum involving its Fourier transform, highlighting the deep connections between a function and its frequency-domain representation.

Both the Convolution Theorem and the Poisson Summation Formula are cornerstones of Fourier analysis. The convolution theorem simplifies complex operations by moving them to the frequency domain, while the Poisson summation formula connects discrete sums of a function to discrete sums of its Fourier transform, revealing profound relationships between time and frequency domains.