Editing Cross-correlation (section)

==Cross-correlation of deterministic signals==
For continuous functions <math>f</math> and <math>g</math>, the cross-correlation is defined as:<ref>Bracewell, R. "Pentagram Notation for Cross Correlation." The Fourier Transform and Its Applications. New York: McGraw-Hill, pp. 46 and 243, 1965.</ref><ref>Papoulis, A. The Fourier Integral and Its Applications. New York: McGraw-Hill, pp.&nbsp;244–245 and 252-253, 1962.</ref><ref>Weisstein, Eric W. "Cross-Correlation." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Cross-Correlation.html</ref><math display="block">(f \star g)(\tau)\ \triangleq \int_{-\infty}^{\infty} \overline{f(t)} g(t+\tau)\,dt</math>which is equivalent to<math display="block">(f \star g)(\tau)\ \triangleq \int_{-\infty}^{\infty} \overline{f(t-\tau)} g(t)\,dt</math>where <math>\overline{f(t)}</math> denotes the [[complex conjugate]] of <math>f(t)</math>, and <math>\tau</math> is called ''displacement'' or ''lag''. 

For highly-correlated <math>f</math> and <math>g</math> which have a maximum cross-correlation at a particular <math>\tau</math>, a feature in <math>f</math> at <math>t</math> also occurs later in <math>g</math> at <math>t+\tau</math>, hence <math>g</math> could be described to ''lag'' <math>f</math> by <math>\tau</math>.

If <math>f</math> and <math>g</math> are both continuous periodic functions of period <math>T</math>, the integration from <math>-\infty</math> to <math>\infty</math> is replaced by integration over any interval <math>[t_0,t_0+T]</math> of length <math>T</math>:<math display="block">(f \star g)(\tau)\ \triangleq \int_{t_0}^{t_0+T} \overline{f(t)} g(t + \tau)\,dt</math>which is equivalent to<math display="block">(f \star g)(\tau)\ \triangleq \int_{t_0}^{t_0+T} \overline{f(t-\tau)} g(t)\,dt</math>Similarly, for discrete functions, the cross-correlation is defined as:<ref>{{cite book | last1 =Rabiner | first1 =L.R. | last2 =Schafer | first2 =R.W. | title =Digital Processing of Speech Signals | publisher =Prentice Hall | series =Signal Processing Series | date =1978 | location =Upper Saddle River, NJ | pages =[https://archive.org/details/digitalprocessin00rabi_0/page/147 147–148] | isbn =0132136031 | url-access =registration | url =https://archive.org/details/digitalprocessin00rabi_0/page/147 }}</ref><ref>{{cite book | last1 =Rabiner | first1 =Lawrence R. | last2 =Gold | first2 =Bernard | title =Theory and Application of Digital Signal Processing | publisher =Prentice-Hall | date =1975 | location =Englewood Cliffs, NJ | pages =[https://archive.org/details/theoryapplicatio00rabi/page/401 401] | isbn =0139141014 | url-access =registration | url =https://archive.org/details/theoryapplicatio00rabi/page/401 }}</ref><math display="block">(f \star g)[n]\ \triangleq \sum_{m=-\infty}^{\infty} \overline{f[m]} g[m+n]</math>which is equivalent to:<math display="block">(f \star g)[n]\ \triangleq \sum_{m=-\infty}^{\infty} \overline{f[m - n]} g[m]</math>For finite discrete functions <math>f,g\in\mathbb{C}^N</math>, the (circular) cross-correlation is defined as:<ref>{{cite thesis | last1=Wang | first1=Chen | title=Kernel learning for visual perception, Chapter 2.2.1 | publisher =Nanyang Technological University, Singapore | type =Doctoral thesis | date =2019 | pages =[https://hdl.handle.net/10356/105527 17–18] | doi=10.32657/10220/47835 | hdl=10356/105527 | doi-access=free | hdl-access=free }}</ref><math display="block">(f \star g)[n]\ \triangleq \sum_{m=0}^{N-1} \overline{f[m]} g[(m+n)_{\text{mod}~N}]</math>which is equivalent to:<math display="block">(f \star g)[n]\ \triangleq \sum_{m=0}^{N-1} \overline{f[(m-n)_{\text{mod}~N}]} g[m]</math>For finite discrete functions <math>f\in\mathbb{C}^N</math>, <math>g\in\mathbb{C}^M</math>, the kernel cross-correlation is defined as:<ref>{{cite journal | last1=Wang | first1=Chen | last2=Zhang | first2=Le | last3=Yuan | first3=Junsong | last4=Xie | first4=Lihua | title=Kernel Cross-Correlator | journal=Proceedings of the AAAI Conference on Artificial Intelligence | publisher=Association for the Advancement of Artificial Intelligence | series=The Thirty-second AAAI Conference On Artificial Intelligence | date =2018 | volume=32 | pages =4179–4186 | doi=10.1609/aaai.v32i1.11710 | s2cid=3544911 | url=https://ojs.aaai.org/index.php/AAAI/article/view/11710 | doi-access=free }}</ref><math display="block">(f \star g)[n]\ \triangleq \sum_{m=0}^{N-1} \overline{f[m]} K_g[(m+n)_{\text{mod}~N}]</math>where <math>K_g = [k(g, T_0(g)), k(g, T_1(g)), \dots, k(g, T_{N-1}(g))]</math> is a vector of kernel functions <math>k(\cdot, \cdot)\colon \mathbb{C}^M \times \mathbb{C}^M \to \mathbb{R}</math> and <math>T_i(\cdot)\colon \mathbb{C}^M \to \mathbb{C}^M</math> is an [[affine transform]].

Specifically, <math>T_i(\cdot)</math> can be circular translation transform, rotation transform, or scale transform, etc. The kernel cross-correlation extends cross-correlation from linear space to kernel space. Cross-correlation is equivariant to translation; kernel cross-correlation is equivariant to any affine transforms, including translation, rotation, and scale, etc.

===Explanation===
As an example, consider two real valued functions <math>f</math> and <math>g</math> differing only by an unknown shift along the x-axis. One can use the cross-correlation to find how much <math>g</math>  must be shifted along the x-axis to make it identical to <math>f</math>. The formula essentially slides the <math>g</math> function along the x-axis, calculating the integral of their product at each position. When the functions match, the value of <math>(f\star g)</math> is maximized. This is because when peaks (positive areas) are aligned, they make a large contribution to the integral. Similarly, when troughs (negative areas) align, they also make a positive contribution to the integral because the product of two negative numbers is positive.

[[File:Cross correlation animation.gif|center|thumb|500x500px|Animation of how cross-correlation is calculated. The left graph shows a green function G that is phase-shifted relative to function F by a time displacement of 𝜏. The middle graph shows the function F and the phase-shifted G represented together as a [[Lissajous curve]]. Integrating F multiplied by the phase-shifted G produces the right graph, the cross-correlation across all values of 𝜏.]]

With [[complex-valued function]]s <math>f</math> and <math>g</math>, taking the [[Complex conjugate|conjugate]] of <math>f</math> ensures that aligned peaks (or aligned troughs) with imaginary components will contribute positively to the integral.

In [[econometrics]], lagged cross-correlation is sometimes referred to as cross-autocorrelation.<ref>{{cite book |last1=Campbell |last2=Lo |last3=MacKinlay |year=1996 |title=The Econometrics of Financial Markets |location=NJ |publisher=Princeton University Press |isbn=0691043019 }}</ref>{{rp|p. 74}}

===Properties===
{{unordered list
| The cross-correlation of functions <math>f(t)</math> and <math>g(t)</math> is equivalent to the [[convolution]] (denoted by <math>*</math>) of <math>\overline{f(-t)}</math> and <math>g(t)</math>. That is:
: <math>[f(t) \star g(t)](t) = [\overline{f(-t)} * g(t)](t).</math>
| <math>[f(t) \star g(t)](t) = [\overline{g(t)} \star \overline{f(t)}](-t).</math>
| If <math>f</math> is a [[Hermitian function]], then <math>f \star g = f * g.</math>
| If both <math>f</math> and <math>g</math> are Hermitian, then <math>f \star g = g \star f</math>.
| <math>\left(f \star g\right) \star \left(f \star g\right) = \left(f \star f\right) \star \left(g \star g\right)</math>.
| Analogous to the [[convolution theorem]], the cross-correlation satisfies
: <math>\mathcal{F}\left\{f \star g\right\} = \overline{\mathcal{F} \left\{f\right\}} \cdot \mathcal{F}\left\{g\right\},</math>

where <math>\mathcal{F}</math> denotes the [[Fourier transform]], and an <math>\overline{f}</math> again indicates the complex conjugate of <math>f</math>, since <math>\mathcal{F}\left\{\overline{f(-t)}\right\}=\overline{\mathcal{F}\left\{f(t)\right\}}</math>. Coupled with [[fast Fourier transform]] algorithms, this property is often exploited for the efficient numerical computation of cross-correlations<ref name="KAP">{{cite book|doi=10.1109/ICSPCS.2015.7391783|isbn=978-1-4673-8118-5|chapter = GPU implementation of cross-correlation for image generation in real time|title = 2015 9th International Conference on Signal Processing and Communication Systems (ICSPCS)|pages = 1–6|year = 2015|last1 = Kapinchev|first1 = Konstantin|last2 = Bradu|first2 = Adrian|last3 = Barnes|first3 = Frederick|last4 = Podoleanu|first4 = Adrian|s2cid=17108908 }}</ref> (see [[circular cross-correlation]]).
| The cross-correlation is related to the [[spectral density]] (see [[Wiener–Khinchin theorem]]).
| The cross-correlation of a convolution of <math>f</math> and <math>h</math> with a function <math>g</math> is the convolution of the cross-correlation of <math>g</math> and <math>f</math> with the kernel <math>h</math>:
: <math>g \star \left(f * h\right) = \left(g \star f\right) * h</math>.
}}