6
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

6
$\begingroup$

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:

cross correlation with Barker code

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:

swap reference and waveform under test

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.

$\endgroup$
15
  • 1
    $\begingroup$ I think what OP is trying to say is using the cross-correlation to "find the lag between a signal and a pattern" appears to be misrepresented through a negation. I'd argue that the peak of $r(t)$ could instead be interpreted as "the time shift required on an input to make an input match a pattern." As evident in the last two equations you stated, if the first statement was to be defined as the use case for the cross-correlation when pattern matching, the signal, $x$, should be swapped with the pattern, $g$, such that you have $g(\tau)x(\tau-t)$. It boils down to interpretation of convention. $\endgroup$
    – Ash
    Commented Apr 8, 2022 at 18:17
  • $\begingroup$ @Ash - yes I think you see the point, in that is is convention, and as written "the pattern" is g(t) while the signal is x(t) results in a later delay being a negative time. I also see how the interpretation of pattern and signal is consistent with other common transforms, such as Fourier which itself is a correlation, where x(t) appears first and the pattern we compare it to appears second (in this case that would be exponential tones of the form ejωt, complex conjugated properly in this case just as in the complex form for the autocorrelation function. $\endgroup$ Commented Apr 8, 2022 at 21:04
  • 2
    $\begingroup$ @OverLordGoldDragon Yes, very interesting... your statement "Correlation" is a measure of similarity, yet cross-correlation at τ is not correlation at τ." summarizes it well. $\endgroup$ Commented Apr 8, 2022 at 21:18
  • 1
    $\begingroup$ I think you wrote a good post on answering e.g. "How to interpret lag in cross-correlation", also extending to complex. But I'm more looking for "with time reversal, thing happens at $\tau$", where "thing" is something significant enough to justify the notation. So far only "slide signal into system" rings such a bell. Perhaps that's all there is! Let's see what others say. $\endgroup$ Commented Apr 10, 2022 at 15:06
  • 1
    $\begingroup$ @OverLordGoldDragon Question is fine as is, I was referring to your last comment where you mentioned time reversal; just confirming we are on the same page which appears to be the case. $\endgroup$ Commented Apr 10, 2022 at 17:47
1
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ I actually expected you to roll in with some stats ... "it means intersection of eigensphere with Poisson hypertorus at $\tau$" ... but back to matter, while I favor this position, Wiki, MIT, and other sources make no mention of the alts, so $C^{(1)}$ is clearly favored for some reason. $\endgroup$ Commented Apr 10, 2022 at 21:12
  • 1
    $\begingroup$ @OverLordGoldDragon the Wiki page that you cited does mention one of the other definitions: "the cross-correlation is defined as ... which is equivalent to ...". Another one: fr.mathworks.com/help/matlab/ref/xcorr.html $\endgroup$
    – AlexTP
    Commented Apr 10, 2022 at 21:35
  • $\begingroup$ @AlexTP Yes, but since it's equivalent, it's not 'defined differently'. As for the other one... MATLAB's on right side of history. Then maybe $C^{(1)}$'s not as dominant as I thought. $\endgroup$ Commented Apr 11, 2022 at 17:29
  • $\begingroup$ I believe this all holds for the complex form as well, meaning no need to limit to real signals (or am I mistaken?) $\endgroup$ Commented Apr 12, 2022 at 0:08
  • $\begingroup$ @DanBoschen just Prof Sarwate seems not interested in this answer anymore (just kidding), I think yes it does hold for the complex form but then we have to talk about which $x(t)$ or $y(t)$ to conjugate, too many combinations! Well, I personally see simply that the correlation is an application of the inner product of a Hilbert space (I have not seen signals that are practical but not assumed to belong to a Hilbert space) and, therefore, all the aforementioned correlation "definitions" are trivially equivalent. $\endgroup$
    – AlexTP
    Commented Apr 15, 2022 at 13:44
1
$\begingroup$

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.

enter image description here

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.

enter image description here

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$. enter image description here

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$ .

enter image description here

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.