2
$\begingroup$

What I'm trying to do is, given some experimental data and it's (magnitude normalized to 1) FFT, match the FFT with one of say 1000 other (magnitude normalized to 1) FFT plots. Please note that the experimental/generated plots all have the same bin width/count.

Initially what I'm doing is taking the normalized cross correlation between the experimental FFT plot and each of the generated FFT plots, and then saving only the zero lag value. Then the highest of these values is found at the end which tells which plot correlated best..

This actually works pretty well, but it doesn't seem like something that is done often.. so

  1. Does this make sense? Is it something that's ever done in the DSP community? Are there better methods of doing this which I'm oblivious to? (Note I have tried an MSE metric with limited success).
  2. If what I'm doing is okay, are there any improvements I can make to it. I have two small problems. The first is computational time, I can compute the zero lag correlation by hand in Matlab as sum(x.*y)/scalefactor (scalefactor = sqrt(sum(x.^2).*sum(y.^2)) ) or I can use xcorr(x,y,0,'coeff') to grab the zero lag value. I'm not sure if these are optimized as well as they could be... The second issue is that if any of the set of generated FFT's are large, say a constant 1 over f=0 to 0.5, the cross correlation metric will be large despite the experimental FFT being much "different". This actually makes me think cross correlation is not the right metric to use, so, any thoughts?

UPDATE: So thinking about this some more, I determined what I was doing was equivalent to just taking the two sequences and performing a circular convolution on them and saving the maximum value. This is the same as computing the FFT of the sequences and then cross correlating them and saving the zero lag value.

With this method I end up doing something like ifft(fft(x).*conj(fft(y))) to do the circular correlation quickly, although I'm still trying to determine if this is more efficient than what i was doing before...

$\endgroup$
  • $\begingroup$ "and then saving only the zero lag value" Then why are you calculating the other lag values? :) elementwise multiplication and sum is the same thing. Oh I see you tried that already. Does matlab have a "timeit"-like function for testing which method is faster? $\endgroup$ – endolith Jul 24 '13 at 23:59
  • $\begingroup$ Indeed, Matlab has a handy "tick" and "tock" to place around code and time it, it "seems" like the xcorr(x,y,0,'coeff') function was faster than doing the x.*y/scalefactor , not always though haha... I guess I need to look closer at how the xcorr function works, I know it uses fft's do it $\endgroup$ – user67081 Jul 25 '13 at 4:53
3
$\begingroup$

Regarding the problem with high correlation values, this happens when both signals are not zero-mean.

Assume two signals $x[k]$ and $y[k]$ of length $N$ each. Each signal can be decomposed into the sum of a constant and a mean-free signal as follows:

$$x[k] = \overline{x} + x_0[k]$$

with $\overline{x}$ being the mean

$$\overline{x} = \frac{1}{N} \sum_{k=0}^{N-1}x[k]$$

and $x_0[k] = x[k] - \overline{x}$. Do the same to get

$$y[k] = \overline{y} + y_0[k]$$

Correlating both sequences at zero lag yields (ignoring scaling here, but this does not change the issue)

$$c = \sum_{k=0}^{N-1}x[k] \cdot y[k] = \sum_{k=0}^{N-1}\overline{x} \cdot \overline{y} + \overline{x} \cdot y_0[k] + \overline{y} \cdot x_0[k] + x_0[k] \cdot y_0[k]$$

Since $x_0[k]$ and $y_0[k]$ are zero-mean, the cross-terms cancel out so the final result is

$$c = N \cdot \overline{x} \cdot \overline{y} + \sum_{k=0}^{N}x_0[k] \cdot y_0[k]$$

So if both correlated signals are not mean-free, the correlation will always contain the product of both means times the amount of samples. If you don't want this and the mean is not relevant, you should subtract it prior to correlating.

Regarding the Matlab question. You can pack all reference signals next to each other in a matrix and then correlate with all at once at zero-lag. If you have $M$ reference signals of length $N$ each, you could do (assuming 'signal' as a column vector and the reference signals saved in columns of 'ref' as well)

c = sum(repmat(signal, 1, M) .* ref)

to obtain a vector row vector c containing the correlations of your experimental signal with all the reference signals ref. No need to calculate the whole correlation or convolutions which is indeed a huge overhead. If you do not want to use repmat, you can also have a look at bsxfun which can achieve the same result and is generally interesting when you want to do element-wise operations with a vector on each row or column of a matrix.

$\endgroup$
-1
$\begingroup$

If the signals do not have any dominating harmonics in them and they all look similar in envelope and smooth enough, maybe you can try sampling the FFTs and performing the same(correlation metrics). It might save you some amount of computation.

And as for your question as to if you're doing something out of the ordinary, I don't think so. Cross correlation at zero lag is the best metric that can give you the closest answer.

$\endgroup$
  • 1
    $\begingroup$ The question doesn't make it sound like the asker has access to any but the original signal, only their FFT's, so I am not sure about your first statement regarding whether the signals "look similar... and smooth enough." As well, simply saying "sample the FFT's and [perform]... correlation metrics" really doesn't provide any insight into what good correlation metrics might be, or why. $\endgroup$ – Sam Maloney Jul 29 '13 at 22:07
  • $\begingroup$ I was talking about the Transforms being similar and smooth enough(without any dominating harmonics). If that condition is satisfied, you can get a cheaper version of the same correlation than if you had performed on the whole set of the samples of FFTs. In case the FFTs are not similar and vary widely, Zero Lag Correlation Metric won't make any sense. This was just to reduce the computation part. $\endgroup$ – Sudarsan Jul 30 '13 at 2:50
  • $\begingroup$ Also I reiterate from my original answer that this can even be a metric to decide if the 2 signals are equivalent. 2 phase shifted signals still have the same magnitude spectrum. I reiterate from my answer that Frequency Domain cross-correlation of Magnitude plot is even a metric to determining the fit in time domain. $\endgroup$ – Sudarsan Jul 30 '13 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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