Talk:Cross-correlation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Statistics (Rated C-class, High-importance)
WikiProject icon

This article is within the scope of the WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page or join the discussion.

C-Class article C  This article has been rated as C-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
 
WikiProject Mathematics (Rated C-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Importance
 Field: Probability and statistics
One of the 500 most frequently viewed mathematics articles.
WikiProject Telecommunications (Rated C-class)
WikiProject icon This article is within the scope of WikiProject Telecommunications, a collaborative effort to improve the coverage of Telecommunications on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the quality scale.
 ???  This article has not yet received a rating on the importance scale.
 

Old comments[edit]

This page is very difficult to follow, when expecting a form of cross correlation that isn't signal processing. Why not start with a general description? —Preceding unsigned comment added by Quatch (talkcontribs) 16:14, 2 September 2009 (UTC)

building up text to add once verified..

given a reference signal and an input signal,
sref = 01011010010110000010111101111001001011010010111000100101101111
sinp = 01111011100100111000000111110011110010011100100111100001001110
the cross-correlation of reference signal with the input signal reaches its maximum of 0.61 when the input signal is rotated to the left 5 places (\dt = -5).
Cross-correlation.gif

Waveguy 06:10, 28 Jan 2005 (UTC)


Things to cover:

  • Different variations, like the above binary signals, "regular old" digital signals like PCM audio, 2D cross-correlation of images, etc.
  • Circular cross-correlation
  • Faster calculation with the use of FFTs

- Omegatron 04:41, Mar 20, 2005 (UTC)

Move to Cross covariance[edit]

Please look at cross covariance article.

I moved the orginal definition (without dividing sigmas) to the cross covariance page. I know there is a lot of disagreement on the difference between covariance and correlation or whether there is a difference, but It seems to be the consensus of the relevant pages that correlation does involve dividing by the sigmas, while covariance does not divide by the sigmas. See Covariance matrix for a short discussion. So, since the new stuff added did not divide by the sigmas, I reverted back to the original. Here is a table I have been using for the relevant pages.

NO SIGMAS WITH SIGMAS
Covariance Correlation
Cross covariance Cross correlation see ext
Autocovariance Autocorrelation
Covariance matrix Correlation matrix
Estimation of covariance matrices

PAR 02:35, 10 July 2005 (UTC)

Discrete-Time Signal Processing by Oppenheim, Schafer, and Buck, which is the definitive textbook for DSP, defines the cross-correlation of two signals without dividing by any sigma. Numerical Recipes in C by Press et al. also defines it without dividing by sigma.
What you are calling the "cross correlation", dividing by sigma, is called the "linear-correlation coefficient" in the statistics text I happen to have on my shelf (Data Reduction and Error Analysis for the Physical Sciences by Bevington and Robinson.)
Perhaps there is a difference in usage between the statistics and signal-processing/engineering communities. Even if so, it is not Wikipedia's place to annoint one usage as the "right" one.
—Steven G. Johnson 19:13, July 10, 2005 (UTC)

I'm not annointing here, I'm just trying to clarify things. Looking at the table above, the cross-correlation was the only article that was in conflict with every other article in the table as far as the sigmas was concerned, so I changed it. If you have a better idea, lets do it. PAR 01:52, 11 July 2005 (UTC)

Please realize that the comments hear apply to every other correlation article in the table. I think that the articles should list forms both with and without sigma, probably merging the covariance/correlation articles to avoid duplication, explain the context for the different usages in signal processing and statistics, and explain the impact of the sigma. As it stands, Wikipedia is annointing one particular usage as the correct one, which is wrong. —Steven G. Johnson 15:55, July 11, 2005 (UTC)
It seems that the definition is ambiguous. - Either we need to find the dominant definition and go with that, or we have to present both. Cburnett 19:23, July 11, 2005 (UTC)

After checking 7 different statistics books, the following is unanimous:

  • The covariance of two different random variates X and Y is
Cov(X,Y)=E( (X-E(X)) (Y-E(Y)) ) where E(X) is expectation value of X.
  • The (linear) correlation coefficient is
R(X,Y) = Cov(X,Y)/(S(X) S(Y)) where S(X) is the std. deviation of X.

Oppenheim et al is the only one to define cross-covariance and cross-correlation and they do it in a very consistent way:

cross correlation \phi_{xy}  =E[ x_n\,y_{n+m}]
cross covariance \gamma_{xy}=E[ (x_n-E[x])\,(y_{n+m}-E[y])]
autocorrelation \phi_{xx}  =E[ x_n\,x_{n+m}]
autocovariance \gamma_{xx}=E[ (x_n-E[x])\,(x_{n+m}-E[x])]

I think it's clear that my moving cross-correlation to cross-covariance was wrong. It's not the sigmas that distinguish correlation from covariance, it's the subtraction of the means. The division by the sigmas is another issue. I would like to alter all articles to conform with Oppenheim's definition, and add very clearly the alternate definitions. There will be no conflict with the 7 books I mentioned, but there will be a clear conflict with the autocorrelation article as it stands. I understand that we do not want to favor a particular set of definitions if there is any controversy, but it seems that the controversy is not so bad, and we do want some clarity and predictability to these articles, rather than conflicting or missing definitons. I will make these changes in a day or two unless there is an objection. PAR 00:18, 12 July 2005 (UTC)

I have also seen "correlation function" used in physical contexts for the subtracted-mean version. The difference is also blurred because in many important cases the mean is zero. I would prefer if auto-correlation, auto-covariance, cross-correlation, and cross-covariance were all defined on a single page (with appropriate redirects). Mathematically, they are so closely related that it hardly makes sense to me to have separate pages. (I'm not sure what to do about the dividing-by-sigma variant, since I'm not so familiar with that). —Steven G. Johnson 01:37, July 12, 2005 (UTC)

OK - how about this: A page entitled "covariance and correlation" or something. It explains that there are conflicting definitions. Then it adopts Oppenheim's definitions for the sake of clarity, not because they are best, but because we need to settle on some consistent way of speaking about things. Then it redirects to the various pages, each of which is rewritten consistent with these definitions, including the important alternate definitions. They are also rewritten as if they might be subsections of the main page. If after this is all done, they look like they ought to go in the main article, we can do that. That way there's no big lump of work that needs to be done, it can all be done slowly, in pieces. PAR 02:07, 12 July 2005 (UTC)

Sounds good to me. —Steven G. Johnson 02:45, July 12, 2005 (UTC)

Ok - I put up a "starter page" at Covariance and correlation. PAR 04:06, 12 July 2005 (UTC)

By the way, I don't think there is anything wrong with an editorial policy that enforces consistent terminology. This is not at odds with NPOV: alternative definitions should be mentioned, but for the sake of coherence and consistency a common set of terms should be used. See for example groupoid vs. magma (algebra) for a precedent. --MarkSweep 16:58, 12 July 2005 (UTC)

some example[edit]

i need examples of mean,median,mode,variablity,range,variance,co-relation,standard deviation ,skewness related to marketing

f*?[edit]

The article mentions f^* in many equations but doesn't define it. What's f^*? —Ben FrantzDale 20:07, 19 December 2006 (UTC)

A superscript asterisk indicates the complex conjugate. --Abdull 21:06, 20 May 2007 (UTC)

Zero-Lag?[edit]

Could someone please add information on the zero-lag? We also need to mention that cross-correlation operation is associative, distributive but not commutative.

Cross-correlation and convolution[edit]

I don't see yet why f(t)\star g(t) = f^*(-t)*g(t). Let's simplify things to f(t) and g(t) being real functions, therefore f(t)\star g(t) = f(-t)*g(t).

As f(t) * g(t) = \int_{a}^{b} f(\tau) g(t - \tau)\, d\tau, what does f(-t)*g(t) look like expressed in integral form?

Besides, if convolution is commutative and cross-correlation is not commutative why can you say f(t)\star g(t) = f^*(-t)*g(t) at all? --Abdull 21:23, 20 May 2007 (UTC)

answer to the commutativity question:

f(t)\star g(t) = f^*(-t)*g(t)

g(t)\star f(t) = g^*(-t)*f(t)

f^*(-t)*g(t) \neq f(t)*g^*(-t)

Dangling citation[edit]

The in-text citation "(Campbell, Lo, and MacKinlay 1996)" isn't all that useful without the actual reference. Could whoever put that in please add the full citation in a "references" section?

appropriate integration limits[edit]

The article curently does not describe what the appropriate integration limits are. Can someone who knows the answer please add them? Ngchen 14:58, 7 October 2007 (UTC)

As an example of (to me) confusing integration limits, consider the convolution of two distributions X ~ Gamma( kx, tx ) and Y ~ Gamma( ky, ty ) (where ki is always >0) -- the goal being to derive a distribution for the difference d=X-Y. It took me most of an evening to realize that the answer is piecewise, with different formulas for d<0 and d>0 (because you have to make sure the arguments of the Gamma distributions are positive -- I think). I eventually figured it out :), but perhaps someone with a better understanding could clarify? Anon.

Possible split[edit]

I think that the usage and terminology in "signal processing" and in "statistics" are so different that a split into articles specific to each is required. Melcombe (talk) 11:47, 26 March 2008 (UTC)

Things to add (but not by me)[edit]

Can someone please add some words about cross-correlating in the frequency domain, a basic description, its advantages (computing economy), disadvantages (only circular correlation unless periods are lengthened and high-pass is used), etc.

Can someone also add a few words about multidimensional correlation and how it reduces to sets of linear correlation?

Fleem (talk) 11:13, 26 September 2008 (UTC)

Another thing that might be included here or in a disambiguation page is the computing definition of the term. Here is a brief def : A cross-correlator is a generic name for a process that compares usually two input streams and usually produces 'summing' or 'difference' streams. All streams will follow their own defined rules and 'summing' and 'difference' are generic labels rather than mathematical terms. The centre of the definition is that it is about feature comparison. Common examples might include text searching algorithms in word processors or database analysis, or various levels in image processing. Lucien86 (talk) 16:22, 13 May 2009 (UTC)

Confusing Definition[edit]

For some reason when working with cross-correlations, the notation for the time-lag "t" and time variable "tau" are switched from the usual convention--little "t" as time and "tau" as a temporal shift. I think the definition could be substantially improved if the the time lag is stated explicitly as "t", as is done in "Numerical Recipes in C", 2nd Ed, on page 498, Eq 12.0.10. I will not change the page, however, because I am not in the habit of changing pages before I get feedback from others.

Bjf624 (talk) 17:07, 18 February 2009 (UTC)

I agree, usually "tau" is used for the lag, and "t" for the dummy variable in the integration. --98.201.96.169 (talk) 23:29, 30 January 2011 (UTC)

Help please[edit]

Is there any accepted definition of when a cross correlation can be rated as "good". Assuming any given normalized cross-correlation, a correlation coefficient of 1/-1 points to identical functions / inverted identical functions while the coefficient being 0 clearly defines a "non-correlation" (or orthogonal correlation). But what about the values inbetween? Is 0.8 a good correlation, or would 0.9 do the job? Is there a general classification of coefficients in terms of correlation quality? Or does that very much depend on the subject of application? I understand that the whole approach of cross-correlation is a statiscal one. Hence there may even be research into that field, describing correlation quality (cross-correlation coefficients) by statistical values such as standard deviation? Could someone knowledgeable maybe give some references and include information in the article? Thank you! --194.246.46.15 (talk) 16:13, 1 July 2009 (UTC) Thank you

No. Sometimes an apple is just an apple. --Drizzd (talk) 11:55, 4 July 2009 (UTC)
Yes, there is more that could be said about that. It depends a lot on your signal-to-noise ratio and on the frequency of your expected signal. If you have zero noise, then 1 means perfect alignment and anything else is imperfect alignment. If you have band-limited (no infinite spatial frequencies) then values near 1.0 mean near-perfect alignment. SNR means you can never expect 1.0 for perfect alignment, and the worse the SNR, the lower the maximum expected correlation value. So yes, the value means something but no it isn't directly interpretable. e.g., a maximum correlation of 0.99 doesn't mean there is a 99% chance that that is the correct correlation. You have to think about what could cause less-than perfect correlation values. —Ben FrantzDale (talk) 19:42, 6 July 2009 (UTC)
Intermediate values of correlation have an interpretation in terms of how well one series can be predicted from another in the sense that one minus the square of the correlation says what proportion of the variance of one series would be left as an error variance if a simple shift and scale is applied optimally from one series to the other. But in signal processing you could hope to do better than than this by using an optimally filtered version of one series to predict the other. Ideas about prewhitening both series could come in here. But even a small amount of correlation could be important depending on what is being predicted ... even a small improvement in predictive power might be important.Otherwise iy may be worth looking at other related articles such as correlation function and correlation. Melcombe (talk) 16:03, 7 July 2009 (UTC)

Incorrect formulation of normalised cross-correlation[edit]

The formula given for the normalised cross-correlation is wrong/misleading. The normalisation varies over the convolution, and is calculated based on the current template position. Refer to Lewis's paper (http://scribblethink.org/Work/nvisionInterface/nip.pdf) for more information. --StefanVanDerWalt (talk) 09:50, 6 December 2009 (UTC)

Known properties of cross-correlation should be added[edit]

I would suggest that all useful properties such as distributivity etc. are listed in an way analogous to how it is done in the convolution article. Furthermore, the notation with "h(-)" as used in the properties section was new to me. I didn't find a definition anywhere. Cheers, Jo. —Preceding unsigned comment added by 129.132.71.148 (talk) 07:40, 6 April 2010 (UTC)

different asterisks[edit]

>> If either f or g is Hermitean, then f*g=f*g.

At first glance, this seems to be a trivial identity which holds for _any_ f and g. At a closer look, you notice the difference between the fivefold and the sixfold asterisk. I think this can easily lead to confusion. Should we use a different notation? DrBaumeister (talk) 01:31, 24 April 2011 (UTC)

x(n)={1,2,3,4,8,-1,-7,-6} find

  a)auto correlation of x[n]
  b)cross correlation of x[n] with {-6,-7,-1,8,4,3,2,1}  — Preceding unsigned comment added by 14.139.128.15 (talk) 10:48, 12 July 2011 (UTC) 

Implementation of Circular Cross-Correlation via FFTs[edit]

When implementing a cross-correlation in digital logic, it often useful to implement the algorithm as a circular cross-correlation through the use of FFTs.

In the following days, I plan to produce an Algorithms Section, including a description, and implementation of the FFt-based approach.

I will also include an implementation of the "shift, multiply and sum" implementation. Does anyone know if there is a formal name for what I am calling the "Shift, multiply, and sum" approach?

Also: does anyone know of any other algorithms?

Kyle.drerup (talk) 05:26, 25 January 2012 (UTC)

Since cross-correlation is equivalent to convolution with a sign flip in the function argument, every fast convolution algorithm gives a fast correlation algorithm. See Convolution#Fast convolution algorithms. (Unfortunately, that section needs a lot of work. It doesn't even mention the Karatsuba algorithm or the Toom-Cook algorithm, and those algorithms in turn are described in their articles as "multiplication algorithms" when in fact they can be used for any convolution problem.) — Steven G. Johnson (talk) 14:41, 25 January 2012 (UTC)

Hermitian properties[edit]

>> If either f or g is Hermitian, then:  f\star g = f*g.

The same statement can also be found in the Hermitian page.

Is that true? I think only if f is Hermitian then f\star g = f*g.Can anyone show the proof of f\star g = f*g if g is Hermitian? -Clarafly (talk) 07:23, 17 June 2012 (UTC)

I agree that this statement is incorrect. Counterexample: f anything not Hermitian, g is the Dirac impulse. Then f \star g = f^*(-t) * g(t) = f^*(-t) and f(t) * g(t) = f(t). --Drizzd (talk) 13:59, 17 June 2012 (UTC)

Visual comparison graphs are offset[edit]

The "Visual comparison" picture is a great idea, but the lines that represents f*g, f♦g and f♦f (where I'm using "♦" for correlation since I can't find a star symbol) are offset. Assuming f(t) and g(t) use the same time scale, f*g should be shifted right and f♦g and f♦f should be shifted left. To be a bit more precise, and for the sake of simplicity assuming f(t) and g(t) are nonzero between t=0 and t=1 (i.e., defining t=0 at the leading edges of f and g, and t=1 at the falling edge of f and where g(t) goes to zero again), f*g is zero for t<0 and maximum when t=1; whereas f♦g and f♦f are zero for t>1 and maximum when t=0. It's also really easy to read the wrong thing into the graphs of the overlapping functions, but on the other hand there's a lot of intuitive value in it as well, so I'm not sure I would change that. But if there's a way to change the picture to shift the black lines, it would be a lot clearer. — Preceding unsigned comment added by Gdlong (talkcontribs) 20:56, 15 November 2013 (UTC)

Problem with Nonlinear Section[edit]

"This problem arises because some moments can go to zero and this can incorrectly suggest that there is little correlation between two signals when in fact the two signals are strongly related by nonlinear dynamics."

If the moments go to zero, and the correlation becomes zero, then it isn't incorrect to suggest that there is little correlation between two signals. The writer seems to be confusing "correlation" with "connection" or some other word that means a relationship exists. The problem arises, because correlation is a measurement of linear dependence, so it makes sense for nonlinear dependencies to circumvent the measurement. A Wikipedia article itself describes this for random variables (and stochastic processes are simply a series of random variables, so it applies just as well): http://en.wikipedia.org/wiki/Correlation_and_dependence — Preceding unsigned comment added by 71.80.79.67 (talk) 09:40, 6 February 2014 (UTC)

Error in Time series Analysis Section[edit]

The writer says, correctly, that in time series the cross correlation is the normalized covariance function (i.e. the Pearson's correlation coefficient). It then shows in Latex the definition of the regular covariance function without normalization by the variances of the two random variables. — Preceding unsigned comment added by 71.80.79.67 (talk) 05:10, 9 February 2014 (UTC)

Zero Lag Peak Statement is Slightly Incorrect[edit]

"there will always be a peak at a lag of zero unless the signal is a trivial zero signal."

Peak here means "highest point in the signal", so even for the trivial zero signal, there is still a peak at a lag of 0 (equal to 0). — Preceding unsigned comment added by 96.38.109.155 (talk) 13:11, 14 March 2014 (UTC)