Editing Convolution theorem (section)

== Functions of a continuous variable ==
Consider two functions <math>u(x)</math> and <math>v(x)</math> with [[Fourier transform]]s <math>U</math> and <math>V</math>:

:<math>\begin{align}
U(f) &\triangleq \mathcal{F}\{u\}(f) = \int_{-\infty}^{\infty}u(x) e^{-i 2 \pi f x} \, dx, \quad f \in \mathbb{R}\\
V(f) &\triangleq \mathcal{F}\{v\}(f) = \int_{-\infty}^{\infty}v(x) e^{-i 2 \pi f x} \, dx, \quad f \in \mathbb{R}
\end{align}</math>

where <math>\mathcal{F}</math> denotes the '''Fourier transform [[Operator (mathematics)|operator]]'''.  The transform may be normalized in other ways, in which case constant scaling factors (typically <math>2\pi</math> or <math>\sqrt{2\pi}</math>) will appear in the convolution theorem below.  The convolution of <math>u</math> and <math>v</math> is defined by:

:<math>r(x) = \{u*v\}(x) \triangleq \int_{-\infty}^{\infty} u(\tau) v(x-\tau)\, d\tau = \int_{-\infty}^{\infty} u(x-\tau) v(\tau)\, d\tau.</math>

In this context the [[asterisk]] denotes convolution, instead of standard multiplication. The [[tensor product]] symbol <math>\otimes</math> is sometimes used instead.

The '''convolution theorem''' states that''':'''<ref name=McGillem/><ref name=Weisstein/>{{rp|eq.8}}

{{Equation box 1
|indent=:|cellpadding=0|border=0|background colour=white
|equation={{NumBlk||
<math>R(f) \triangleq \mathcal{F}\{r\}(f) = U(f) V(f). \quad f \in \mathbb{R}</math> &nbsp; &nbsp;
|{{EquationRef|Eq.1a}} }} }}

Applying the inverse Fourier transform <math>\mathcal{F}^{-1},</math> produces the corollary''':'''<ref name=Weisstein/>{{rp|eqs.7,10}}

{{Equation box 1|title='''Convolution theorem'''
|indent=|cellpadding=6|border=|border colour=#0073CF|background colour=#F5FFFA
|equation={{NumBlk|:|
<math>r(x) = \{u*v\}(x) = \mathcal{F}^{-1}\{U\cdot V\}.</math> &nbsp; &nbsp;
|{{EquationRef|Eq.1b}} }} }}

The theorem also generally applies to multi-dimensional functions.

{{Collapse top|title=Multi-dimensional derivation of Eq.1}}
Consider functions <math>u,v</math> in [[Lp space|L<sup>''p''</sup>]]-space <math>L^1(\mathbb{R}^n),</math> with Fourier transforms <math>U,V</math>''':'''

:<math>
\begin{align}
U(f) &\triangleq \mathcal{F}\{u\}(f) = \int_{\mathbb{R}^n} u(x) e^{-i 2 \pi f \cdot x} \, dx, \quad f \in \mathbb{R}^n\\
V(f) &\triangleq \mathcal{F}\{v\}(f) = \int_{\mathbb{R}^n} v(x) e^{-i 2 \pi f \cdot x} \, dx,
\end{align}
</math>

where <math>f\cdot x</math> indicates the [[dot product|inner product]] of '''<math>\mathbb{R}^n</math>:''' &nbsp; <math>f\cdot x = \sum_{j=1}^{n} {f}_j x_j,</math> &nbsp; and &nbsp; <math>dx = \prod_{j=1}^{n} d x_j.</math>

The [[convolution]] of <math>u</math> and <math>v</math> is defined by''':'''

:<math>r(x) \triangleq \int_{\mathbb{R}^n} u(\tau) v(x-\tau)\, d\tau.</math>

Also''':'''

:<math>\iint |u(\tau)v(x-\tau)|\,dx\,d\tau=\int \left( |u(\tau)| \int |v(x-\tau)|\,dx \right) \,d\tau = \int |u(\tau)|\,\|v\|_1\,d\tau=\|u\|_1 \|v\|_1.</math>

Hence by [[Fubini's theorem]] we have that <math>r\in L^1(\mathbb{R}^n)</math> so its Fourier transform <math>R</math> is defined by the integral formula''':'''

:<math>
\begin{align}
R(f) \triangleq \mathcal{F}\{r\}(f) &= \int_{\mathbb{R}^n} r(x) e^{-i 2 \pi f \cdot x}\, dx\\
&= \int_{\mathbb{R}^n} \left(\int_{\mathbb{R}^n} u(\tau) v(x-\tau)\, d\tau\right)\, e^{-i 2 \pi f \cdot x}\, dx.
\end{align}
</math>

Note that <math>|u(\tau)v(x-\tau)e^{-i 2\pi f \cdot x}|=|u(\tau)v(x-\tau)|,</math>&nbsp; Hence by the argument above we may apply Fubini's theorem again (i.e. interchange the order of integration)''':'''

:<math>
\begin{align}
R(f) &= \int_{\mathbb{R}^n} u(\tau)
\underbrace{\left(\int_{\mathbb{R}^n} v(x-\tau)\ e^{-i 2 \pi f \cdot x}\,dx\right)}_{V(f)\ e^{-i 2 \pi f \cdot \tau}}\,d\tau\\
&=\underbrace{\left(\int_{\mathbb{R}^n} u(\tau)\ e^{-i 2\pi f \cdot \tau}\,d\tau\right)}_{U(f)}\ V(f).
\end{align}
</math>
{{Collapse bottom}}

This theorem also holds for the [[Laplace transform]], the [[two-sided Laplace transform]] and, when suitably modified, for the [[Mellin transform]] and [[Hartley transform]] (see [[Mellin inversion theorem]]).  It can be extended to the Fourier transform of [[abstract harmonic analysis]] defined over [[locally compact abelian group]]s.

=== Periodic convolution (Fourier series coefficients) ===

Consider <math>P</math>-periodic functions <math>u_{_P}</math> &nbsp; and &nbsp; <math>v_{_P},</math> which can be expressed as [[periodic summation]]s:

:<math>u_{_P}(x)\ \triangleq \sum_{m=-\infty}^{\infty} u(x-mP)</math> &nbsp; and &nbsp; <math>v_{_P}(x)\ \triangleq \sum_{m=-\infty}^{\infty} v(x-mP).</math>

In practice the non-zero portion of components <math>u</math> and <math>v</math> are often limited to duration <math>P,</math> but nothing in the theorem requires that.

The [[Fourier series]] coefficients are:

:<math>\begin{align}
   U[k] &\triangleq \mathcal{F}\{u_{_P}\}[k] = \frac{1}{P} \int_P u_{_P}(x) e^{-i 2\pi k x/P} \, dx, \quad k \in \mathbb{Z}; \quad \quad \scriptstyle \text{integration over any interval of length } P\\
   V[k] &\triangleq \mathcal{F}\{v_{_P}\}[k] = \frac{1}{P} \int_P v_{_P}(x) e^{-i 2\pi k x/P} \, dx, \quad k \in \mathbb{Z}
 \end{align}</math>

where <math>\mathcal{F}</math> denotes the '''Fourier series integral'''.

* The product:  <math>u_{_P}(x)\cdot v_{_P}(x)</math> is also <math>P</math>-periodic, and its Fourier series coefficients are given by the [[Convolution#Discrete convolution|discrete convolution]] of the <math>U</math> and <math>V</math> sequences:

:<math>\mathcal{F}\{u_{_P}\cdot v_{_P}\}[k] = \{U*V\}[k].</math>

*The convolution:

:<math>\begin{align}
\{u_{_P} * v\}(x)\ &\triangleq \int_{-\infty}^{\infty} u_{_P}(x-\tau)\cdot v(\tau)\ d\tau\\
&\equiv \int_P u_{_P}(x-\tau)\cdot v_{_P}(\tau)\ d\tau; \quad \quad \scriptstyle \text{integration over any interval of length } P
\end{align}</math>

is also <math>P</math>-periodic, and is called a '''[[periodic convolution]]'''.

{{Collapse top|title=Derivation of periodic convolution}}
:<math>\begin{align}
\int_{-\infty}^\infty u_{_P}(x - \tau) \cdot v(\tau)\,d\tau
  &= \sum_{k=-\infty}^\infty \left[\int_{x_o+kP}^{x_o+(k+1)P} u_{_P}(x - \tau) \cdot v(\tau)\ d\tau\right] \quad x_0 \text{ is an arbitrary parameter}\\
  &=\sum_{k=-\infty}^\infty \left[\int_{x_o}^{x_o+P} \underbrace{u_{_P}(x - \tau-kP)}_{u_{_P}(x - \tau), \text{ by periodicity}} \cdot v(\tau + kP)\ d\tau\right] \quad \text{substituting } \tau \rightarrow \tau+kP\\
  &=\int_{x_o}^{x_o+P} u_{_P}(x - \tau) \cdot \underbrace{\left[\sum_{k=-\infty}^\infty v(\tau + kP)\right]}_{\triangleq \ v_{_P}(\tau)}\ d\tau
\end{align}</math>
{{Collapse bottom}}

The corresponding convolution theorem is''':'''

{{Equation box 1
|indent=|cellpadding=0|border=0|background colour=white
|equation={{NumBlk|:|
<math>\mathcal{F}\{u_{_P} * v\}[k] =\ P\cdot U[k]\ V[k].</math> &nbsp; &nbsp;
|{{EquationRef|Eq.2}} }} }}

<!--{{math proof|title=Derivation of Eq.2| proof = -->
{{Collapse top|title=Derivation of Eq.2}}
:<math>\begin{align}
\mathcal{F}\{u_{_P} * v\}[k] &\triangleq \frac{1}{P} \int_P \left(\int_P u_{_P}(\tau)\cdot v_{_P}(x-\tau)\ d\tau\right) e^{-i 2\pi k x/P} \, dx\\
&= \int_P u_{_P}(\tau)\left(\frac{1}{P}\int_P v_{_P}(x-\tau)\ e^{-i 2\pi k x/P} dx\right) \, d\tau\\
&= \int_P u_{_P}(\tau)\ e^{-i 2\pi k \tau/P}
\underbrace{\left(\frac{1}{P}\int_P v_{_P}(x-\tau)\ e^{-i 2\pi k (x-\tau)/P} dx\right)}_{V[k], \quad \text{due to periodicity}} \, d\tau\\
&=\underbrace{\left(\int_P\ u_{_P}(\tau)\ e^{-i 2\pi k \tau/P} d\tau\right)}_{P\cdot U[k]}\ V[k].
\end{align}</math>
{{Collapse bottom
}}