What is the intuitive thought behind the cross-correlation function?

Hi all,

I was told the claim that the cross-correlation of two functions f(x) and 
g(x), defined as :

(f & g) (x)=integrate(f(u), g(u+x), w.r.t. u from -inf to inf)

reflects the similarity between the two functions f and g.

After some Matlab experiments, I was convinced.

But what is the intuitive(phylosophical) thought behind this 
cross-correlation function? Why it reflects the similarity between the two 
functions f and g? Can it be proved mathematically?

Any thoughts?

-N 

> But what is the intuitive(phylosophical) thought behind this
> cross-correlation function? Why it reflects the similarity between the two
> functions f and g? Can it be proved mathematically?

Here is a nice demo for a GPS-receiver:
http://www.ottmarlabonde.de/L1/krzkor.Applet1.html
(its german, so
"Neue Signalmuster erzeugen"="create new signal patterns"
"Verz�gerungen durch Signallaufzeiten"~"delay by distance")

On 2004-10-20 09:35:20 +0200, "kiki" <lunaliu3@yahoo.com> said:

> But what is the intuitive(phylosophical) thought behind this 
> cross-correlation function? Why it reflects the similarity between the 
> two functions f and g?

Well, if you look closely you'll see that the (cross)correlation 
process does something that can be seen as actually "comparing" one 
data set with an inreasingly delayed version of another data set. If 
you have a perfect match of the two sets for a given delay ("lag") you 
get a peak in the correlation function. That's pretty intuitive 
already, isn't it?
-- 
Stephan M. Bernsee
http://www.dspdimension.com

On Wed, 20 Oct 2004 00:35:20 -0700, "kiki" <lunaliu3@yahoo.com> wrote:

>Hi all,
>
>I was told the claim that the cross-correlation of two functions f(x) and 
>g(x), defined as :
>
>(f & g) (x)=integrate(f(u), g(u+x), w.r.t. u from -inf to inf)
>
>reflects the similarity between the two functions f and g.
>
>After some Matlab experiments, I was convinced.
>
>But what is the intuitive(phylosophical) thought behind this 
>cross-correlation function? Why it reflects the similarity between the two 
>functions f and g? Can it be proved mathematically?
>
>Any thoughts?
>
>-N 
>
>
Suppose x(k) and x(n) are two random variables which can be +1 or -1.

We have 4 possibilities

   x(k)  y(n)   x(k)y(n)
1)  1      1         1
2)  1     -1        -1
3) -1      1        -1
4) -1     -1         1

If x(k) and x(n) are independents, and take values -1 or +1 with the
same probability, then the 4 values of product are equiprobable, and
the average of this product is null &#4294967295; If x(k) and y(n) are dependent
and tend to take value +1 or -1 more frequently, then the cases 1) and
4) are more frequent, and the average of the product is positive &#4294967295;

Conversely, if they are dependent but more frequently take the opposed
values, the cases 2) and 3) are more frequent, and the average of the
product is negative &#4294967295; In short, if x(k) and y(n) are not dependent
then Rxy(k,n) is nul , if they are dependent  Rxy(k, n) is nul.,

R is thus a measurement of the tendency of X and Y to take the same
values, i.e. to be similar.


pierre.c

On Wed, 20 Oct 2004 08:19:32 GMT, pierre.cussol@apx.fr (pierre.c)
wrote:

Ooups!


....In short, if x(k) and y(n) are not dependent
then Rxy(k,n) is nul , if they are , Rxy(k, n) is  NOTnul.,
>
>pierre.c

pierre.c

Hello Kiki,

To expand on what Stephan had stated, the cross correlation is taking
advantage of the signal containing both positive and negative values. So for
the case of proper alignment, the integrand is nonnegative, so the
integration in effect adds up all of the positive numbers. But if the
alignment is incorrect, then the integrand contains both positive and
negative vales, so the adding up totals to a small number. So you can see
the correlation yields a peaked function.

Of course this brings up the question of what kinds of functions yield
sharply peaked autocorrelation functions. With binary signals these are
called Barker (after R.H. Barker) codes. And with complex binary codes,
there is an extension to Barker's idea which uses complementary codes. The
complementary codes are neat in that while the real or imaginary part has a
sharply peaked autocorrelation function, the cross correlation between the
real and imaginary parts is almost nil.  This is quite useful in situations
with complex modulation.  The 802.11 protocol uses both Barker and
Complementary codes depending on the data rate.


IHTH,
Clay S. Turner








"kiki" <lunaliu3@yahoo.com> wrote in message
news:cl54fm$8gr$1@news.Stanford.EDU...
> Hi all,
>
> I was told the claim that the cross-correlation of two functions f(x) and
> g(x), defined as :
>
> (f & g) (x)=integrate(f(u), g(u+x), w.r.t. u from -inf to inf)
>
> reflects the similarity between the two functions f and g.
>
> After some Matlab experiments, I was convinced.
>
> But what is the intuitive(phylosophical) thought behind this
> cross-correlation function? Why it reflects the similarity between the two
> functions f and g? Can it be proved mathematically?
>
> Any thoughts?
>
> -N
>
>

"kiki" <lunaliu3@yahoo.com> wrote in message news:<cl54fm$8gr$1@news.Stanford.EDU>...
> Hi all,
> 
> I was told the claim that the cross-correlation of two functions f(x) and 
> g(x), defined as :
> 
> (f & g) (x)=integrate(f(u), g(u+x), w.r.t. u from -inf to inf)
> 
> reflects the similarity between the two functions f and g.
> 
> After some Matlab experiments, I was convinced.
> 
> But what is the intuitive(phylosophical) thought behind this 
> cross-correlation function? Why it reflects the similarity between the two 
> functions f and g? Can it be proved mathematically?

The cross correlation is an inner product in a vector space. This is 
easier to see if you use vectors instead of continuous functions:

          N
  c   =  sum x[n]y[n]                                           (1)
         n=1

where x and y are vectors with N coefficients. If you set N = 2 or 
N = 3, you will find that (1) above is just the dot product of vectors 
in basic geometry. The inner product measures the projection of x onto 
the basis y. If x and y point in the same direction ("are similar"),
the dot product has its largest possible magnitude. 

It's nothing particular about N = 2 or N = 3. The same line of arguments
work for any N, even N infinite. The case of large N is not as easy to 
visualize as for the N=2,3 cases, though. It's even more prblematic 
to visualize when the vectors are continuous functions. But the maths 
works equally well, and by the same principles.

The proof of that the inner product measures the "similarity" of two
vectors or functions consists of two parts. First, prove that the inner 
product as in (1) above, has exactly one maximum. Second, prove that 
this maximum is reached iff x==y.

You would find this type of proofs in the context of linear algebra.

Rune

You slide one function over the other, one sample at a time, and at
each slid point you:

 - multiply corresponding samples of each function
 - sum all those products

Summing the prducts is like taking the area under the resulting curve
of the products.

Now, if the signals are similar, and unslid, then their products will
be like squaring one signal - which will all be positive going, so the
area under this curve wil all add (constructive interefernce -
remember physics of waves?) and so will be big. If the signals are not
similar, or are slid, then some positive signal samples will multiply
negative signal samples, so some of the resulting product samples will
be negative, and these negative going parts of the curve will subtract
from the positive parts (destructive interference) so the area will be
less.

I think I describe this with a diagram at:

   http://www.bores.com/courses/intro/time/2_corr.htm

Chris
==================================
Chris Bore
BORES Signal Processing
chris@bores.com
www.bores.com


"kiki" <lunaliu3@yahoo.com> wrote in message news:<cl54fm$8gr$1@news.Stanford.EDU>...
> Hi all,
> 
> I was told the claim that the cross-correlation of two functions f(x) and 
> g(x), defined as :
> 
> (f & g) (x)=integrate(f(u), g(u+x), w.r.t. u from -inf to inf)
> 
> reflects the similarity between the two functions f and g.
> 
> After some Matlab experiments, I was convinced.
> 
> But what is the intuitive(phylosophical) thought behind this 
> cross-correlation function? Why it reflects the similarity between the two 
> functions f and g? Can it be proved mathematically?
> 
> Any thoughts?
> 
> -N

It's like interference between waves (eg physics, waves, ripple tanks,
etc).

If the signals are similar, then When the two signals are similar in
shape and unshifted with respect to each other, their product is all
positive. This is like constructive interference, where the peaks add
and the troughs subtract to emphasise each other. The area under this
curve gives the value of the correlation function at point zero, and
this is a large value.

As one signal is shifted with respect to the other, or when they are
not similar, the signals go out of phase - the peaks no longer
coincide, so the product can have negative going parts. This is a bit
like destructive interference, where the troughs cancel the peaks. The
area under this curve gives the value of the correlation function at
the value of the shift. The negative going parts of the curve now
cancel some of the positive going parts, so the correlation function
is smaller.

The largest value of the correlation function shows when the two
signals were similar in shape and unshifted with respect to each other
(or 'in phase'). The breadth of the correlation function - where it
has significant value - shows for how long the signals remain similar.

This is from a web page I wrote some years ago:

    http://www.bores.com/courses/intro/time/2_corr.htm

Hope it helps,

Chris
=================================================
Chris Bore
BORES Signal Processing
www.bores.com
chris@bores.com


"kiki" <lunaliu3@yahoo.com> wrote in message news:<cl54fm$8gr$1@news.Stanford.EDU>...
> Hi all,
> 
> I was told the claim that the cross-correlation of two functions f(x) and 
> g(x), defined as :
> 
> (f & g) (x)=integrate(f(u), g(u+x), w.r.t. u from -inf to inf)
> 
> reflects the similarity between the two functions f and g.
> 
> After some Matlab experiments, I was convinced.
> 
> But what is the intuitive(phylosophical) thought behind this 
> cross-correlation function? Why it reflects the similarity between the two 
> functions f and g? Can it be proved mathematically?
> 
> Any thoughts?
> 
> -N

Hi,

I think Rune has given a great explanation. Nevertheless, here is my
not-very-rigorous proof of the whole thing.


Given function f(x) and g(x). Let r(x) = f(x) - g(x) 

Without loss of generality, assume the energies of f(x) and g(x) are
both equal to E, i.e.

Integrate( f(x)*f(x) )dx = E
Integrate( g(x)*g(x) )dx = E
(I am going to omit dx from now on.)


The correlation between f(x) and g(x) is given by:

  Integrate( f(x)*g(x) ) 
= Integrate( ((g(x)+r(x)) * g(x) ) 
= Integrate( g(x)*g(x) ) + Integrate( r(x)*g(x) ) 
= E + Integrate( r(x)*g(x) ) 
.................................(A)

However, the same correlation can also be written as

  Integrate( f(x)*g(x) ) 
= Integrate( f(x) * ((f(x)-r(x)) ) 
= Integrate( f(x)*f(x) ) + Integrate( -r(x)*f(x) ) 
= E + Integrate( r(x)*(-f(x)) ) 
.................................(B)


Add up (A) and (B), you get:

  2*( correlation of f(x) and g(x) )
= 2*E + Integrate( r(x)*( g(x)-f(x) ) ) 
= 2*E + Integrate( -(r(x)^2) ) 

Since -(r(x)^2) is always <= 0, its integral is non-positive

=> 2*(correlation of f and g) <= 2*E
=> correlation of f(x) and g(x) <= E


In this process, we have proved that the correlation is maximum when
r(x)=0.
That is, when f(x)=g(x)


By this proof, we have also shown (1-normalized correlation value) is
equal to the energy of the difference between 2 functions w.r.t the
total energy. In the discrete world, correlation tells you the sum of
the squares of the difference between 2 signals, which is a very
useful parameter in many applications.


Best regards.

KD