# How to find a maximal possible value of a cross correlation

Is there any way of calculating a maximal possible value of a cross correlation of two signals whose maximal amplitude and sample rate is known?

To make things clearer, , signals in question are mostly the same signal but one is shifted in phase. So, basically I want to know what will be the output of a cross correlation if they are not shifted, but without actually shifting one back and doing the CC to find out.

• You can use normalized cross correlation and then the maximum is always 1. – ThP May 21 '16 at 17:33
• Do you know how to do that in Python? Well, or Matlab or whatever? – Dalen May 21 '16 at 17:56
• Divide the output of the cross correlation by the norms of the two signals. – ThP May 21 '16 at 19:53
• @thp : Sorry but that is unclear to me. This hints that "norms of the two signals" gives the maximum of the CC as I asked. But you didn't say what exactly you mean by "norms". First norm, second norm... How to do it, mean of two norms? Or orthogonal norm... What? I tried, really, but didn't see any sense in results. Please clarify a bit. And be so kind to write an answer so that you can be properly rewarded. – Dalen May 22 '16 at 8:33
• @thp : Well, thanks at hint to normalized CC, but the answer is to perform the following on two input vectors before correlating. for correlate(a, v) do: a = (a - mean(a)) / (std(a) * len(a)); v = (v - mean(v)) / std(v). The output for correlate(X, X) is 1. This will help me greatly. – Dalen May 22 '16 at 9:07

Yes, but only if you know the mean and variance (or standard deviation) of the signal. The maximum correlation will be the (variance of the signal + the mean-squared) times the total number of samples. If you do not already know the variance, calculating it would be similar to calculating the auto-correlation in terms of processing so nothing is really saved in that case. But in some cases you may have prior knowledge or ability to more easily estimate the variance (from a smaller sample set for example if the process is white and stationary).

To check my logic, consider what is involved to calculate correlation for a sampled signal when it is aligned with itself (for the maximum autocorrelation) compared to calculating the variance for the signal:

To correlate two signals: You multiply the two signals sample by sample, and then sum the result.

The equation to calculate the variance is similar, but you must subtract the mean from each sample before doing the product, and then you must divide by the total number of samples. (Important to note, this is not the unbiased estimate of the variance which scales by N-1, but the calculation for the 2nd Moment about the mean, which scales by N). The variance therefore is just a normalized autocorrelation at lag=0 with the mean removed.

To put very simply, CorrMax is just 1/N * the second moment. (The second moment is the average of the squares or mean-squared value). Variance is the 2nd moment with the mean removed (about the mean), so we have to add it back in as we've done above if we were starting with that particular factor known. However consider if we already know the mean-squared value, (or the square of the rms value since rms is commonly used), then the relationship is the mean-squared value times the number of samples.

Therefore in summary: To determine the maximum correlation for a sequence X that is N samples long, assuming you already have either the mean and variance (2nd moment about the mean), use:

$$CorrMax(X) = N(\sigma_X+\mu_X^2)$$

Where:

X is a vector of length N

$\sigma_X$ is the second moment of X about the mean

$\mu_X$ is the mean of X

Or alternatively calculated from the mean-squared value for the sequence,

$$CorrMax(X) = N(X_{rms}^2)$$

Where:

X is a vector of length N

$X_{rms}^2$ is the second moment of X (mean-square of X)

• It kind of works! But, the difference between real cross correlation of X with X and the calculated one is 25.859. The real CC gives 1002.297. The N is 2000 samples. The result is correct if I substract 50.292 from N. Which has no sense to me. Do you know what is happening here? Is the calculation a correct value or just the best approx? – Dalen May 21 '16 at 16:08
• It is difficult for me to understand without seeing the actual data and process you are using. A key question is if you are able to get the mean and variance of your data. If that is not known (as you mentioned only have the maximum amplitude) then you will not be able to determine the maximum autocorrelation. – Dan Boschen May 21 '16 at 21:32
• I have both signals sampled at 22050, so I can get anything I need from them. I tested your solution on a generated cosine of 100 Hz, 2000 samples long. I am doing what you said: (var(X)+mean(X))*len(X) and as I said, the result is 1028, while corellate(X, X) gives 1002. (I cut off the decimals here) – Dalen May 21 '16 at 21:44
• A key question is if you are able to get the mean and variance of your data. If that is not known (as you mentioned only have the maximum amplitude) then you will not be able to determine the maximum autocorrelation. If you know something about your waveform that will allow you to estimate what the variance is based on a peak amplitude (such as peak-average power in EE terms), then to the degree you can estimate this as well as the mean, you can estimate your maximum correlation. – Dan Boschen May 21 '16 at 21:44
• I wrote the last comment before seeing your update--- what was the actual mean and the variance; curious if there is some N-1 factor... – Dan Boschen May 21 '16 at 21:46

You cannot find the maximal value of the cross-correlation function of two signals (actually autocorrelation value of one signal) knowing only the maximal amplitude $A$ and the number of samples $N$. You can get a very crude upper bound on the maximal value as follows.

Suppose that the two (real-valued) signals are $$\mathbf x = \left(x[0], x[1], \ldots, x[N-1]\right) \quad \text{and} \quad \mathbf y = \left(y[0], y[1], \ldots, y[N-1]\right)$$ where $$\max_{0 \leq i \leq N-1} \max\left\{x[i],y[i]\right\} = A. \tag{1}$$ The aperiodic autocorrelation function is \begin{align}C_{\mathbf x, \mathbf y}[k] &= \sum_{i=0}^{N-1-k} x[i]y[i+k], &0 \leq k \leq N-1,\tag{2}\\ C_{\mathbf x, \mathbf y}[k] &= C_{\mathbf y, \mathbf x}[-k], &0 > k \leq -N+1. \tag{3}\end{align} It follows trivially from $(1)$ that $$\max C_{\mathbf x, \mathbf y}[k] \leq A^2(N-k).\tag{4}$$ For cyclic or periodic convolution $\theta_{\mathbf x, \mathbf y}[k] = C_{\mathbf x, \mathbf y}[k]+ C_{\mathbf x, \mathbf y}[N-k]$, the crude bound $(4)$ becomes $$\theta_{\mathbf x, \mathbf y}[k]\leq A^2N \ \ \text{for all } k.\tag{5}$$ These results are readily adapted for the case when $\mathbf x$ and $\mathbf y$ have different maximal amplitudes, as well as to the case when the sequences are complex-valued.

Note that this is the deterministic version of Dan Boschen's answer.

• I don't really need a 100% accurate value. Just that the formula gives the value that will be equally spaced for any signal. I have to scale the values of the cross correlation, so I do need some fixed maximum that will enable me to accurately put the calculated CC result into wanted interval. If the calculated maximum is always some 25 off from the real value it will be good. But even if it isn't just that it follows the signals CC ratios, as it should, it will also be OK. Two signals are always normalized before CC, so there should not be problems. – Dalen May 21 '16 at 17:40