Editing Convolution (section)

== Properties ==

=== Algebraic properties ===
{{See also|Convolution algebra}}
The convolution defines a product on the [[linear space]] of integrable functions. This product satisfies the following algebraic properties, which formally mean that the space of integrable functions with the product given by convolution is a commutative [[associative algebra]] without [[identity element|identity]] {{harv|Strichartz|1994|loc=§3.3}}. Other linear spaces of functions, such as the space of continuous functions of compact support, are [[closure (mathematics)|closed]] under the convolution, and so also form commutative associative algebras.

; [[Commutativity]]: <math display="block">f * g = g * f </math> Proof: By definition: <math display="block">(f * g)(t) = \int^\infty_{-\infty} f(\tau)g(t - \tau)\, d\tau</math> Changing the variable of integration to <math>u = t - \tau</math> the result follows.

; [[Associativity]]: <math display="block">f * (g * h) = (f * g) * h</math> Proof: This follows from using [[Fubini's theorem]] (i.e., double integrals can be evaluated as iterated integrals in either order).

; [[Distributivity]]: <math display="block">f * (g + h) = (f * g) + (f * h)</math> Proof: This follows from linearity of the integral.

; Associativity with scalar multiplication: <math display="block">a (f * g) = (a f) * g</math> for any real (or complex) number <math>a</math>.

; [[Multiplicative identity]]: No algebra of functions possesses an identity for the convolution. The lack of identity is typically not a major inconvenience, since most collections of functions on which the convolution is performed can be convolved with a [[Dirac delta|delta distribution]] (a unitary impulse, centered at zero) or, at the very least (as is the case of ''L''<sup>1</sup>) admit [[Nascent delta function|approximations to the identity]]. The linear space of compactly supported distributions does, however, admit an identity under the convolution. Specifically, <math display="block">f * \delta = f</math> where ''δ'' is the delta distribution.

; Inverse element: Some distributions ''S'' have an [[inverse element]] ''S''<sup>−1</sup> for the convolution which then must satisfy <math display="block">S^{-1} * S = \delta</math> from which an explicit formula for ''S''<sup>−1</sup> may be obtained.{{paragraph}}The set of invertible distributions forms an [[abelian group]] under the convolution.

; Complex conjugation: <math display="block">\overline{f * g} = \overline{f} * \overline{g}</math>

; Time reversal:  If &nbsp;<math>q(t) = r(t)*s(t),</math>&nbsp; then &nbsp;<math>q(-t) = r(-t)*s(-t).</math>

<blockquote>
Proof (using [[convolution theorem]]):

<math>q(t) \ \stackrel{\mathcal{F}}{\Longleftrightarrow}\ \ Q(f) = R(f)S(f)</math>

<math>q(-t) \ \stackrel{\mathcal{F}}{\Longleftrightarrow}\ \ Q(-f) = R(-f)S(-f)</math>

<math>
\begin{align}
q(-t) &= \mathcal{F}^{-1}\bigg\{R(-f)S(-f)\bigg\}\\
&= \mathcal{F}^{-1}\bigg\{R (-f)\bigg\} * \mathcal{F}^{-1}\bigg\{S(-f)\bigg\}\\
&= r(-t) * s(-t)
\end{align}
</math>
</blockquote>
; Relationship with differentiation: <math display="block">(f * g)' = f' * g = f * g'</math> Proof:
:<math>
\begin{align}
(f * g)' & = \frac{d}{dt} \int^\infty_{-\infty} f(\tau) g(t - \tau) \, d\tau \\
& =\int^\infty_{-\infty} f(\tau) \frac{\partial}{\partial t} g(t - \tau) \, d\tau \\
& =\int^\infty_{-\infty} f(\tau) g'(t - \tau) \, d\tau = f* g'.
\end{align}
</math>

; Relationship with integration: If <math display="inline">F(t) = \int^t_{-\infty} f(\tau) d\tau,</math> and <math display="inline">G(t) = \int^t_{-\infty} g(\tau) \, d\tau,</math> then <math display="block">(F * g)(t) = (f * G)(t) = \int^t_{-\infty}(f * g)(\tau)\,d\tau.</math>

=== Integration ===
If ''f'' and ''g'' are integrable functions, then the integral of their convolution on the whole space is simply obtained as the product of their integrals:<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Convolution|url=https://mathworld.wolfram.com/Convolution.html|access-date=2021-09-22|website=mathworld.wolfram.com|language=en}}</ref>
: <math>\int_{\mathbf{R}^d}(f * g)(x) \, dx=\left(\int_{\mathbf{R}^d}f(x) \, dx\right) \left(\int_{\mathbf{R}^d}g(x) \, dx\right).</math>

This follows from [[Fubini's theorem]]. The same result holds if ''f'' and ''g'' are only assumed to be nonnegative measurable functions, by [[Fubini's theorem#Tonelli's theorem|Tonelli's theorem]].

=== Differentiation ===
In the one-variable case,
: <math>\frac{d}{dx}(f * g) = \frac{df}{dx} * g = f * \frac{dg}{dx}</math>

where <math>\frac{d}{dx}</math> is the [[derivative]]. More generally, in the case of functions of several variables, an analogous formula holds with the [[partial derivative]]:
: <math>\frac{\partial}{\partial x_i}(f * g) = \frac{\partial f}{\partial x_i} * g = f * \frac{\partial g}{\partial x_i}.</math>

A particular consequence of this is that the convolution can be viewed as a "smoothing" operation: the convolution of ''f'' and ''g'' is differentiable as many times as ''f'' and ''g'' are in total.

These identities hold for example under the condition that ''f'' and ''g'' are absolutely integrable and at least one of them has an absolutely integrable (L<sup>1</sup>) weak derivative, as a consequence of [[Young's convolution inequality]]. For instance, when ''f'' is continuously differentiable with compact support, and ''g'' is an arbitrary locally integrable function,
: <math>\frac{d}{dx}(f* g) = \frac{df}{dx} * g.</math>

These identities also hold much more broadly in the sense of tempered distributions if one of ''f'' or ''g'' is a 
[[distribution (mathematics)#Convolution versus multiplication|rapidly decreasing tempered distribution]], a 
compactly supported tempered distribution or a Schwartz function and the other is a tempered distribution. On the other hand, two positive integrable and infinitely differentiable functions may have a nowhere continuous convolution.

In the discrete case, the [[difference operator]] ''D'' ''f''(''n'') = ''f''(''n'' + 1) − ''f''(''n'') satisfies an analogous relationship:
: <math>D(f * g) = (Df) * g = f * (Dg).</math>

=== Convolution theorem ===
The [[convolution theorem]] states that<ref>{{cite web |last1=Weisstein |first1=Eric W |title=From MathWorld--A Wolfram Web Resource |url=https://mathworld.wolfram.com/ConvolutionTheorem.html}}</ref>
: <math> \mathcal{F}\{f * g\} = \mathcal{F}\{f\}\cdot \mathcal{F}\{g\}</math>

where <math> \mathcal{F}\{f\}</math> denotes the [[Fourier transform]] of <math>f</math>.

==== Convolution in other types of transformations ====

Versions of this theorem also hold for the [[Laplace transform]], [[two-sided Laplace transform]], [[Z-transform]] and [[Mellin transform]].

==== Convolution on matrices ====

If <math>\mathcal W</math> is the [[DFT matrix|Fourier transform matrix]], then
: <math>\mathcal W\left(C^{(1)}x \ast C^{(2)}y\right) = \left(\mathcal W C^{(1)} \bull \mathcal W C^{(2)}\right)(x \otimes y) = \mathcal W C^{(1)}x \circ \mathcal W C^{(2)}y</math>,

where <math> \bull </math> is [[Khatri–Rao product#Face-splitting product|face-splitting product]],<ref name="slyusar">{{Cite journal|last=Slyusar|first=V. I.|date= December 27, 1996|title=End products in matrices in radar applications. |url=https://slyusar.kiev.ua/en/IZV_1998_3.pdf |archive-url=https://web.archive.org/web/20130811122444/https://slyusar.kiev.ua/en/IZV_1998_3.pdf |archive-date=2013-08-11 |url-status=live|journal=Radioelectronics and Communications Systems |volume=41 |issue=3|pages=50–53}}</ref><ref name="slyusar1">{{Cite journal|last=Slyusar|first=V. I.|date=1997-05-20|title=Analytical model of the digital antenna array on a basis of face-splitting matrix products. |url=https://slyusar.kiev.ua/ICATT97.pdf |archive-url=https://web.archive.org/web/20130811112059/https://slyusar.kiev.ua/ICATT97.pdf |archive-date=2013-08-11 |url-status=live|journal=Proc. ICATT-97, Kyiv|pages=108–109}}</ref><ref name="DIPED">{{Cite journal|last=Slyusar|first=V. I.|date=1997-09-15|title=New operations of matrices product for applications of radars|url=https://slyusar.kiev.ua/DIPED_1997.pdf |archive-url=https://web.archive.org/web/20130811113217/https://slyusar.kiev.ua/DIPED_1997.pdf |archive-date=2013-08-11 |url-status=live|journal=Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.|pages=73–74}}</ref><ref name="slyusar2">{{Cite journal|last=Slyusar|first=V. I.|date=March 13, 1998|title=A Family of Face Products of Matrices and its Properties|url=https://slyusar.kiev.ua/FACE.pdf |archive-url=https://web.archive.org/web/20130811113935/https://slyusar.kiev.ua/FACE.pdf |archive-date=2013-08-11 |url-status=live|journal=Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999.|volume=35|issue=3|pages=379–384|doi=10.1007/BF02733426|s2cid=119661450}}</ref><ref name="general">{{Cite journal|last=Slyusar|first=V. I.|date=2003|title=Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels|url=https://slyusar.kiev.ua/en/IZV_2003_10.pdf |archive-url=https://web.archive.org/web/20130811125643/https://slyusar.kiev.ua/en/IZV_2003_10.pdf |archive-date=2013-08-11 |url-status=live|journal=Radioelectronics and Communications Systems|volume=46|issue=10|pages=9–17}}</ref> <math> \otimes </math> denotes [[Kronecker product]], <math> \circ </math> denotes [[Hadamard product (matrices)|Hadamard product]] (this result is an evolving of [[count sketch]] properties<ref name="ninh">{{cite conference 
 | title = Fast and scalable polynomial kernels via explicit feature maps
 | last1 = Ninh | first1 = Pham
 | first2 = Rasmus | last2 = Pagh | author2-link = Rasmus Pagh
 | date = 2013
 | publisher = Association for Computing Machinery
 | conference = SIGKDD international conference on Knowledge discovery and data mining
 | doi = 10.1145/2487575.2487591
}}</ref>).

This can be generalized for appropriate matrices <math>\mathbf{A},\mathbf{B}</math>:

: <math>\mathcal W\left((\mathbf{A}x) \ast (\mathbf{B}y)\right) = \left((\mathcal W \mathbf{A}) \bull (\mathcal W \mathbf{B})\right)(x \otimes y) = (\mathcal W \mathbf{A}x) \circ (\mathcal W \mathbf{B}y)</math>
from the properties of the [[face-splitting product]].

=== Translational equivariance ===
The convolution commutes with translations, meaning that
: <math>\tau_x (f * g) = (\tau_x f) * g = f * (\tau_x g)</math>

where τ<sub>''x''</sub>f is the translation of the function ''f'' by ''x'' defined by
: <math>(\tau_x f)(y) = f(y - x).</math>

If ''f'' is a [[Schwartz function]], then ''τ<sub>x</sub>f'' is the convolution with a translated Dirac delta function ''τ''<sub>''x''</sub>''f'' = ''f'' ∗ ''τ''<sub>''x''</sub> ''δ''. So translation invariance of the convolution of Schwartz functions is a consequence of the associativity of convolution.

Furthermore, under certain conditions, convolution is the most general translation invariant operation. Informally speaking, the following holds
: Suppose that ''S'' is a bounded [[linear operator]] acting on functions which commutes with translations: ''S''(''τ<sub>x</sub>f'') = ''τ<sub>x</sub>''(''Sf'') for all ''x''. Then ''S'' is given as convolution with a function (or distribution) ''g''<sub>''S''</sub>; that is ''Sf'' = ''g''<sub>''S''</sub> ∗ ''f''.

Thus some translation invariant operations can be represented as convolution. Convolutions play an important role in the study of [[time-invariant system]]s, and especially [[LTI system theory]]. The representing function ''g''<sub>''S''</sub> is the [[impulse response]] of the transformation ''S''.

A more precise version of the theorem quoted above requires specifying the class of functions on which the convolution is defined, and also requires assuming in addition that ''S'' must be a [[continuous linear operator]] with respect to the appropriate [[topology]]. It is known, for instance, that every continuous translation invariant continuous linear operator on ''L''<sup>1</sup> is the convolution with a finite [[Borel measure]]. More generally, every continuous translation invariant continuous linear operator on ''L''<sup>''p''</sup> for 1 ≤ ''p'' < ∞ is the convolution with a [[Distribution (mathematics)#Tempered distributions and Fourier transform|tempered distribution]] whose [[Fourier transform]] is bounded. To wit, they are all given by bounded [[Fourier multiplier]]s.