Convolutions and Correlations
How to convolve and correlate two piecewise-polynomial periodic one-dimensional splines.
Terminology
Notations
The operator \(*\) indicates a convolution.
The operator \(\star\) indicates a crosscorrelation.
The superscript \(\mbox{}^{*}\) indicates a complex conjugate.
The superscript \(\mbox{}^{\vee}\) indicates a mirror, with \(\forall x\in{\mathbb{R}}:f^{\vee}(x):=f(-x).\)
Definitions
The mean value of a \(K\)-periodic function \(f\) is defined as \({\mathrm{E}}\{f\}=\frac{1}{K}\,\int_{0}^{K}\,f(x)\,{\mathrm{d}}x.\)
The variance of a \(K\)-periodic function \(f\) is defined as \({\mathrm{Var}}\{f\}=\frac{1}{K}\,\int_{0}^{K}\,\left(f(x)-{\mathrm{E}}\{f\}\right)^{2}\,{\mathrm{d}}x.\)
Convolutions
Ordinary Convolution
Let a one-dimensional function be \(h:{\mathbb{R}}\rightarrow{\mathbb{C}}\) and let another one-dimensional function be \(f:{\mathbb{R}}\rightarrow{\mathbb{C}}.\) Their convolution is defined as the function
Caution must be taken that the integration process does converge. For instance, it turns out that it does not converge when both \(h\) and \(f\) are periodic; thus, convolution must be defined differently in this particular case.
Periodic Convolution
Let a one-dimensional \(K\)-periodic function be \(h:{\mathbb{R}}\rightarrow{\mathbb{C}}\) and let another one-dimensional \(K\)-periodic function be \(f:{\mathbb{R}}\rightarrow{\mathbb{C}},\) with \(K\in{\mathbb{N}}+1,\) \(h(x)=h(x+K),\) and \(f(x)=f(x+K)\) for all \(x\in{\mathbb{R}}.\) Their periodic convolution is defined as the function
Caution must be taken that the integration process does converge; for simplicity, we shall henceforth restrict ourselves to periodic functions \(h\) and \(f\) that are nonsingular. Note that the notation for a convolution does not differ from that for a periodic convolution; both make use of the same operator \(*.\) More often than not, however, the context allows one to easily distinguish between them.
The convolution operator is commutative, with \(h*f=f*h.\)
The convolution operator is associative, with \(h_{1}*\left(h_{2}*f\right)=\left(h_{1}*h_{2}\right)*f.\)
These properties apply to true functions. Proceed with caution upon their application to generalized functions; for instance, integration (the convolution with a unit step) and differentiation (the convolution with the derivative of a Dirac delta function) do not commute.
Correlations
Crosscorrelation
The crosscorrelation of \(f:{\mathbb{R}}\rightarrow{\mathbb{C}}\) and \(g:{\mathbb{R}}\rightarrow{\mathbb{C}}\) is defined as the function
When the two functions are periodic of the same integer period \(K,\) the same caveats apply as for their convolution. Their periodic crosscorrelation is the function
Note that one must pay attention to distinguish the convolution operator \(*\) from the crosscorrelation operator \(\star.\)
The crosscorrelation operator satisfies a conjugate-reflective symmetry, with \(f\star g=\left(g\star f\right)^{*\vee}.\)
One has that \(f*g=f^{*\vee}\star g.\) Equivalently, one has that \(f\star g=f^{*\vee}*g.\)
Autocorrelation
The crosscorrelation \(R_{ff}=f\star f\) is called the autocorrelation of \(f.\) By the Wiener-Khinchin theorem, the \(\nu\)-th coefficient of the Fourier series of the autocorrelation of a \(K\)-periodic real function \(f:{\mathbb{R}}\rightarrow{\mathbb{R}}\) is related to the Fourier series of the function as \(F\{R_{ff}\}[\nu]=K\,\left|F\{f\}[\nu]\right|^{2}.\)
Periodic Normalized Crosscorrelation
Crosscorrelation measures how well \(f\) matches \(g\) in terms of their relative shift. Unfortunately, the measure is not easy to interpret because it depends on the units in which the functions are expressed. By contrast, the normalized crosscorrelation proposes a closely related measure that returns values in the interval \([-1,1]\) when the functions \(f:{\mathbb{R}}\rightarrow{\mathbb{R}}\) and \(g:{\mathbb{R}}\rightarrow{\mathbb{R}}\) are real. For periodic functions, the periodic normalized crosscorrelation is defined as the function
This definition returns exactly the same mapping as would two competing definitions, a first one in which no mean value would be subtracted from \(f(y)\) but instead the mean value \(E\{g\}\) would be subtracted from \(g(x+y),\) and a second one in which appropriate mean values would be subtracted at the same time from \(f(y)\) and from \(g(x+y).\)
When compared to crosscorrelation, one downside of the normalized crosscorrelation is that it is not well-defined when \({\mathrm{Var}}\{f\}\,{\mathrm{Var}}\{g\}=0.\)
Pearson Correlation Coefficient
The Pearson correlation coefficient is the normalized crosscorrelation evaluated at the origin, as \(\rho_{fg}(0).\)
Convolution and Filtering of Splines
The periodic convolution between a periodic \(h\) and a periodic \(f\) is best understood as the (non-periodic) convolution between the windowed version \(h_{[0,K)}\) of \(h\) and the periodic \(f.\) Indeed, if we let \({\mathbf{[\![}}\cdot\,{\mathbf{]\!]}}\) denote the Iverson bracket, then it holds that
In other words, the periodic convolution \(h*f\) is identical to the non-periodic, classic filtering of the (still periodic) signal \(f\) by a filter of finite, non-periodic causal impulse response \(h_{[0,K)}.\)
Let \(h\) be a periodic polynomial spline of period \(K,\) degree \(n_{1},\) and delay \(\delta x_{1}.\) In addition, let \(f\) be a periodic polynomial spline of period \(K,\) degree \(n_{2},\) and delay \(\delta x_{2}.\) Then, \(h*f\) turns out to be a spline of period \(K,\) degree \(n_{1}+n_{2}+1,\) and delay \(\delta x_{1}+\delta x_{2}.\)
We now propose a few lines of code that create and display two random splines and convolves them.
The first spline plays the role of the filter with continuously defined impulse response \(h.\) Its coefficients are built as the absolute value of independent realizations of a random variable that follows a Cauchy distribution; moreover, the spline is normalized in such a way that it has a unit integral over one period. This promotes lowpass filters; if chance has it, one of the Cauchy coefficients will dwarf the other ones and the impulse response will be unimodal, with a pronounced bulge.
The second spline plays the role of the signal \(f\) being filtered. Its coefficients are built as independent realizations of a random variable that follows a Gaussian distribution.
Jupyter Lab notebook
Crosscorrelation of Splines
We also propose a few lines of code that create and display two random splines and compute their crosscorrelation, with or without normalization. The Pearson correlation coefficient is also printed. The spline coefficients of the functions been cross-correlated are built as independent realizations of a random variable that follows a Cauchy distribution.
Jupyter Lab notebook
Autocorrelation of a Spline
We finally propose a few lines of code that create and display a random spline \(f\) and compute its autocorrelation, with or without normalization. The spline coefficients are built as independent realizations of a random variable that follows a uniform distribution.
It is noteworthy to make a few observations.
The autocorrelation (whether normalized or not) is independent of the delay of the spline.
The autocorrelation (whether normalized or not) has a central symmetry, with \(\rho_{ff}=\rho_{ff}^{\vee}\) and \(R_{ff}=R_{ff}^{\vee}.\) Combined with \(K\)-periodicity, the central symmetry implies that the continuously defined autocorrelation is also necessarily symmetric around \(\frac{K}{2}.\)
In general, the normalized autocorrelation takes a unit value at the origin (i.e., \(\rho_{ff}(0)=1\) unless \({\mathrm{Var}}\{f\}=0\)).
Jupyter Lab notebook