Cross-correlation seems defined backwards

Question

Suppose $f$ and $g$ are real. Why

$$ C(\tau)=(f\star g)(\tau) = \int_{-\infty}^{\infty} f(t) g(t + \tau)dt \tag{1} $$

and not

$$ C(\tau)=(f\star g)(\tau) = \int_{-\infty}^{\infty} f(t) g(t - \tau)dt\tag{2} $$

where $f=$ input, $g =$ template/pattern to be matched. $(2)$ properties:

1. If $g$ is centered at $t=0$, and $f$ is $g$ shifted to $T$, then $C$ peaks at $T$.

2. If $g$ is centered at $t=T_0$, and $f$ is $g$ shifted to $T_1$, then $C$ peaks at $T_1 - T_0$.

   • Suppose $f$ is $g$ shifted to $t=0$. Then, $C$ peaks at $-T_0$, meaning $g$ is most similar to $f$ when shifted left by $T_0$.

$(1)$ has all of this backwards. $C$ at $1$ is similarity of $g$ with $f$ at $-1$, i.e. inner product of $f$ with $g$ shifted to $-1$.

How is this useful? Why not just have $C(1)$ mean "similarity of input with template shifted by $1$", which for template centered at 0 is nicely "template centered at $1$", e.g.

$C$ peaks at (1cm, 2cm) because that's where the apple is in the image

Yes, $(1)$ becomes $(2)$ if we look at it as matching input against template instead, but this answers the reverse of "where at input does this sub-pattern occur". I can also see it as answering "after how long will input match template if we pass it through the template (e.g. signal into system)", but we won't ask this for images and it's more suited as a physics than statistical tool.

Whatever the case, does $(2)$ have a name?

Answer 1

Interesting question. For purposes of "pattern matching" the resulting peak of the auto-correlation function will either be consistent with the actual time offset between the matching pattern in the two waveforms or of opposite sign, depending on which waveform we refer to as the "reference pattern" and how we define the sign as indicating leading or lagging time. So knowing this, and how the cross-correlation function is defined, we just need to understand for the purpose of pattern matching that we should interpret $f(t)$ as the reference pattern and $g(t)$ as the waveform under test. This would result in a peak at a $\tau$ that is consistent with the actual time offset (with a later offset of the pattern in the waveform under test being reported as a positive quantity). The formula as a cook-book is directing us to slide the waveform under test past our template from right to left (see graphics below), rather than slide the pattern past the waveform. That answer is too simple / obvious, so the next deeper question is are there any other reasons it would make more sense to have one or the other be the "reference"? For this we should look at other similar formulas for consistency in convention, and open it up to the complete complex expression rather than the simpler case of only being real (the two should be consistent).

Before further comments/opinions on that, I will open with a graphic demonstrating the question at hand to be clearer and repeating the OP's opening formula and the interpretation of this:

$$ C(\tau)=(f\star g)(\tau) = \int_{-\infty}^{\infty} f(t) g(t + \tau)dt \label{1}\tag{1} $$

Below shows an example pattern $g(t)$ as a square wave assigned values of +/-1 based on the symbols in a Barker Code sequence. $f(t)$ is the waveform under test with the pattern delayed by two symbols, and if we use the formula as given in \ref{1}, the reported lag has an opposite sign to the actual lag, which is what the OP is pointing out:

However, to continue the illustration, if we either changed the sign in the formula according to the OP's suggestion, or swapped reference and test waveform: the reported lag would be consistent in sign to the actual lag:

The formula is by convention, and by defining the operation we can properly use the formula and interpret the result. However, we then may ask why would it be written as such, and is having one or the other as the "template" consistent with other similar formulas having this basic transform structure? To consider this, I think it is important to include complex waveforms, with the real waveform case as a subset of the complex. Let's consider the following examples starting with "correlation" on its own.

Correlation and the Fourier Transform

Consider the general formula for correlation:

$$ C\{f(t)g(t)\} = \int_{-\infty}^{\infty} f(t) g^*(t)dt \label{2}\tag{2} $$

This is not the auto-correlation function but simply the correlation between two waveforms $f(t)$ and $g(t)$. The result is the linear similarity of the two waveforms when they are synchronized to both start at $t=0$. Note how importantly for this to work with the general case of complex waveforms, we must conjugate $g(t)$, shown here as $g^*(t)$, in order for the correlation process to be successful. If there is further curiosity about that, I explain why the conjugation is important in much further detail in this post, but for here we note that one of the two must be conjugated.

The result of this correlation will have both a magnitude and phase result. If we considered two waveforms with only a phase difference, it is clear that the template is the one that should be conjugated in order for the phase result to match the phase difference between the two waveforms:

$$f(t) = K(t)e^{j\phi_1}$$

$$g(t)= K(t)e^{j\phi_2}$$

$$C\{f(t)g^*(t)\} = C\{K(t)K^*(t)\}e^{j(\phi_1-\phi_2)}$$

The point above is if we seek to know the phase difference of $f(t)$ relative to $g(t)$, which is $\phi_1-\phi_2$, then if we conjugate $g(t)$ we will get this result. This suggests the template is the one to be conjugated when the template is complex.

Now consider if we wanted to use correlation as given in \ref{2} to compare our arbitrary waveform $f(t)$ with a template given by a single exponential frequency given as $g(t) = e^{j\omega t}$:

$$C\{f(t)g(t)\} = \int_{-\infty}^{\infty} f(t) g^*(t)dt = \int_{-\infty}^{\infty} f(t) e^{-j \omega t}dt \label{3}\tag{3}$$

If we vary $\omega$ in the template, so that we can determine all the frequency components in our waveform, we get the Fourier Transform! The Fourier Transform is another example where correlation is used against a template as we vary a parameter, and the template is properly the conjugated waveform:

$$\mathscr{F}\{f(t)\} = \int_{-\infty}^{\infty} f(t) e^{-j\omega t}dt\label{4}\tag{4}$$

Now we consider the auto-correlation function as the OP introduced but including the complex numbers as specified in the references given here :

$$ C(\tau)=(f\star g)(\tau) = \int_{-\infty}^{\infty} f^*(t) g(t + \tau)dt \label{5}\tag{5} $$

Notice that it is $f(t)$ that is conjugated. This would imply, for similarity to the other forms introduced, that $f(t)$ is the template. This is consistent with the specified formula for the cross-correlation function, using $g(t+\tau)$, with further justification for $f(t)$ to be template: it will provide a result that is consistent in both lag and relative phase. This isn't to say this must be the case, as we can rewrite the equations to change the sign and conjugate the waveform instead of the template (and still have the same result), but to suggest why one form may be more prevalent than the other.

It is interesting to point out that both the Fourier Transform (FT) and the cross-correlation function are correlations against a template, and we vary a parameter to see how that correlation changes versus the parameter. In the cross correlation function we sweep over offset in the time domain (delay); in the Fourier Transform we sweep over rotation in the time domain (phase).

Convolution and Correlation Similarity and Differences

We can also compare and contrast "convolution" and "correlation" for real waveforms as typically presented for further clues as to a logical choice for the sign:

Cross-Correlation function:

$$r(\tau) = \int_{t=-\infty}^{\infty}f(t)g(\tau+t)dt$$

Convolution:

$$c(t) = \int_{\tau=-\infty}^{\infty}f(\tau)g(t-\tau)d\tau$$

By swapping the variables of $t$ and $\tau$ in correlation, the key difference between the two and the importance of the sign in the relationship between the two becomes clearer:

Cross-Correlation Function:

$$r(t) = \int_{\tau=-\infty}^{\infty}f(\tau)g(\tau+t)d\tau$$

Convolution:

$$c(t) = \int_{\tau=-\infty}^{\infty}f(\tau)g(-\tau+t)d\tau$$

In the cross-correlation function, our objective is to find the similarity between the two waveforms versus a time delay and this is accomplished by having the two waveforms in the same time direction (here $f(\tau)$ and $g(\tau)$, where for each possible time delay $t$ we compute the correlation as a "sum of products" (or as done here in continuous time, multiply and integrate).

With convolution, and for the purposes where we would use it, we must time reverse one of the waveforms first, (here we see that with $f(\tau)$ and $g(-\tau)$ and then we can proceed in similar fashion as we did with correlation where we shift $t$ and then compute the "sum of products".

So in both cases, as $t$ increases in the positive direction such as in $r(t)$, so too does it increase in a positive direction within each function. In either case we could certainly, and consistently between the two, have $t$ subtracted instead of added. This would serve to time-reverse the result (effectively $r(-t)$). So we could give (2) a name in that it is a time-reversed cross-correlation with $f(t)$ as our reference.

For purposes of correlation the time reversal is arbitrary but will define how we interpret the result in terms of what means lagging or leading between the two waveforms. However for convolution the sign as done is consistent with the temporal result of a linear system given the convolution of the input waveform with the impulse response.

Conclusion:

It is all just a matter of convention and proper interpretation given the function as defined. However specific to the OP's question and curiosity; the autocorrelation function is appropriately signed if we consider $f(t)$ to be the template. This use is consistent with the general form for correlation and the Fourier Transform (which itself is a correlation to $e^{j\omega t}$. With review of the complete equation including complex waveforms, we get further justification for using $f(t)$ as the template in which case both the lag and the relative phase in the result will be consistent in sign.

Answer 2

There are four different definitions of the cross-correlation function for two real signals $x(t)$ and $y(t)$, but they are all closely related, and which one anyone chooses to use can be attributed to a matter of personal preference; translation from one to another is easy. The four definitions are

\begin{align} C_{x,y}^{(1)}(\tau) &= \int_{-\infty}^\infty x(t)y(t+\tau) \,\mathrm dt, ~-\infty < \tau < \infty,\\ C_{x,y}^{(2)}(\tau) &= \int_{-\infty}^\infty x(t)y(t-\tau) \,\mathrm dt, ~-\infty < \tau < \infty,\\ C_{x,y}^{(3)}(\tau) &= \int_{-\infty}^\infty x(t+\tau)y(t) \,\mathrm dt, ~-\infty < \tau < \infty,\\ C_{x,y}^{(4)}(\tau) &= \int_{-\infty}^\infty x(t-\tau)y(t) \,\mathrm dt, ~-\infty < \tau < \infty.\\ \end{align} It is, I hope, relatively easy to see that $C_{x,y}^{(2)}(\tau) = C_{x,y}^{(1)}(-\tau), ~\text{and}~ C_{x,y}^{(3)}(\tau) = C_{x,y}^{(4)}(-\tau);$ disbelievers should do a formal change of variables to verify these wild claims. Similarly, $C_{x,y}^{(3)}(\tau) = C_{x,y}^{(2)}(\tau), ~\text{and}~ C_{x,y}^{(4)}(\tau) = C_{x,y}^{(1)}(-\tau)$.

Answer 3

You could use any one of the equation given in Dilip's answer. But preferably use complex equation with conjugate, even though it doesn't make any difference in case of real functions.

The idea remains the same, conjugate any one of the function ( Why do we need to conjugate ? , because when one function $f(t)$ gets aligned parallel to the other one $g(t)$ then the value of real part of $f^*(t)×g(t)$ maximises ) then multiply with the other function. Before multiplication apply shift to either one of the function.

Remember it doesn't matter to which function you are applying the shift, because your reference will always on function in which you applied the shift. Suppose if you applied $\tau$ shift on $f$ i.e. $f(t \pm \tau)$ then lag or lead will always be calculated with respect to $f(t)$ not with $g(t)$. Similarly for $g(t)$ , if you apply $\pm \tau$ on $g$ then your reference signal will be $g(t)$. $\tau$ measures how much shift you given to the original signal.

Coming back to OP's query, which form should be using (1) or (2) ? It depends solely on the technical terminology you are going to use.

If you want to go technically correct with the term correlation lag ($\tau$) , then you should use (1). Why?

To bring clarity to anyone comes in this way, lets talk about lag & lead.(feel free to skip)

if we walk along the time axis from negative side of the axis to the positive side and encounters the reference signal and If you further move forward and then you see the second signal, we say the second signal is delayed with respect to the reference, like in this figure.

So a minus term in the argument of function represent a delay or lag.

On contrary to that if you have already seen the other signal when you encounter with the reference signal then it is said to be leading w.r.t reference.

So a positive number in argument part represent a lead, like in this figure.

When considering two functions $f$ & $g$ ,if there is a feature in $f$ (marked by black dot) and there is a similar feature in $g$ (marked by blue dot) to make it coincide with one another it has to be shifted back towards $f$ as shown by dotted line. For that shift to happen we need to apply a lead (+ value) to the argument. That's why the first equation is having a positive $\tau$ on $g$.

So to get a match, we are applying a lead and we are calling $\tau$ as correlation lag ,how is it possible? The interpretation is clearly given in wikipedia article.

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

The corresponding feature in $g$ is in a delayed position w.r.t similar feature point in $f$, thus the term correlation lag. When graphing $C(\tau)$ against $\tau$, it shows how much $g$ is delayed w.r.t $f$.

$\underline{\text{To conclude:}}$

If your interpretation needs to be in line with the terminology $\underline{\text{correlation lag}}$ use the form of equation given by (1). Which is,

$$C(\tau)=(f\star g)(\tau) = \int_{-\infty}^{\infty} f^*(t) g(t + \tau)dt $$