6
$\begingroup$

I realize the two are derived using different algorithms, and the units are different, but from a conceptual standpoint of the information they provide how do they differ?

I'm thinking here about the more or less specific (yet general) case of a "representative" block of samples from a time series, where the gross statistics of the data are assumed to vary slowly relative to the block size. (I gather that's roughly what's defined as a WSS process.)

Note that I've got an intuitive understanding of Fourier transform (at least the simple 1-dimensional real version) as a "spectrum". I haven't developed an intuitive concept for autocorrelation -- that's what I'm groping for.

Update: Rather than scatter things about, I'll put this here, since it's related to my desire to understand what an autocorrelation is doing...

The following (primitive) chart is of a brute-force autocorrelation of one of my signals. (The units are largely meaningless, and 256 bins are jammed into 150 print position.) The curious thing is the bifurcated tail. What would cause this? (It so happens that I see this twin tail at the peak of a snore -- otherwise the tail is kind of fuzzy, and the peak and slope are not nearly as pronounced.) Checking the numeric data shows that every other value is about 10x different from it's immediate neighbors.

I suppose it's some sort of artifact of the sampling, but it's not obvious to me what specifically that might be.

16893892.00 :           *                                                                                                                                           
12668632.00 :             *                                                                                                                                         
9500134.00 :                                                                                                                                                       
7124095.00 :            *                                                                                                                                          
5342317.50 :                                                                                                                                                       
4006173.25 :               *                                                                                                                                       
3004206.00 :                                                                                                                                                       
2252836.75 :                *                                                                                                                                      
1689389.25 :          *                                                                                                                                            
1266863.12 :                                                                                                                                                       
950013.38 :                 *                                                                                                                                     
712409.50 :         *               *                                                                                                                             
534231.75 :              *   *    **                                                                                                                              
400617.31 :        *                 *                                                                                                                            
300420.59 :          *        *  *  * *                                                                                                                           
225283.67 :      *                      *                                                                                                                         
168938.92 :             *                **                                                                                                                       
126686.32 :               **               **  **                                                                                                                 
 95001.34 :     *   *            *           *   * *                                                                                                              
 71240.95 :                     *    *            *  * * **                                                                                                       
 53423.18 :                                           * *   *  *                                                                                                  
 40061.73 :       *                   **                     ** ** * **                                                                                           
 30042.06 :  *                *                                     *  ** ***                                                                                     
 22528.37 :                             *      *                             *** ** **  *                                                                         
 16893.89 :        *        *  *         * *               *                       *   * **** ** **                                                               
 12668.63 :   *                              *                                                  *  * ****** ****                                                  
  9500.13 :   *                             * * * *                                                             ** ****** *****  **                               
  7124.10 :      *                                    *     *    *                                                              *  *** ****** *****  **  *        
  5342.32 :                                        **           * *                                                                                *   ** * ***** 
  4006.17 :                                          *       **    ** ***                                                                                         
  3004.21 : *   *              *                         **              *** ***        *                                                                         
  2252.84 :                                            *                        *** ***  *  *                                                                     
  1689.39 :                                                                            *   * **** ** *                                                            
  1266.86 :                                                                                         * ** ****  * ***   **                                         
   950.01 :  *                                                                                               *  *   * *  *   **  ** *                   *         
   712.41 :                                                                                                               **   **    ****  ***** *****    *  *   *
   534.23 :                                                                                                                              *            *  * *   *  
   400.62 :                                                                                                                                                 *   * 
   300.42 :                                                                                                                                                       
   225.28 : *  *                  *                                                                                                                               
========= : ======================================================================================================================================================
          :  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
          :  0 0 1 2 2 3 4 4 5 5 6 7 7 8 9 9 0 0 1 2 2 3 4 4 5 5 6 7 7 8 9 9 0 0 1 2 2 3 4 4 5 5 6 7 7 8 9 9 0 0 1 2 2 3 4 4 5 5 6 7 7 8 9 9 0 0 1 2 2 3 4 4 5 5 6
          :  3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5 1 8 4 0 6 3 9 5
          :  1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6 9 1 4 6
$\endgroup$
  • 6
    $\begingroup$ The two operations are completely different. It's not really meaningful to compare them at all; they are merely two tools that are used to accomplish specific jobs. $\endgroup$ – Jason R May 30 '12 at 15:36
  • 1
    $\begingroup$ Yet both provide what is in essence a frequency spectrum. $\endgroup$ – Daniel R Hicks May 30 '12 at 15:58
  • 4
    $\begingroup$ The Fourier transform gives you a function of the frequency, the autocorrelation a function of a time lag ; so I wouldn't call the autocorrelation a "frequency spectrum". $\endgroup$ – pichenettes May 30 '12 at 16:06
  • 3
    $\begingroup$ @DanielRHicks You cannot define frequency loosely. Either everyone follows the same definition, or it stops being science. From this perspective, time is just inverse frequency makes no sense, because your can't simply invert units without a rigorous definition for inverting the quantities they describe. $\endgroup$ – Phonon May 31 '12 at 16:12
5
$\begingroup$

Ok, in the context of one specific application: If you're trying to find the frequency of a waveform, you can calculate it similarly from the position of the peak in a Fourier transform or the peak of an autocorrelation. (And the autocorrelation can be calculated efficiently using the Fourier transform, so I don't know why everyone is naysaying "they're totally different and unrelated".)

The Fourier transform shows you all the individual frequency components of the signal. If the fundamental frequency happens to be the biggest, you can just pick it out of the spectrum and the position of that peak will be the fundamental frequency of the waveform. If the peaks are harmonically related, but missing the fundamental, there won't be a peak at the fundamental, and you'll have to use some special processing of the positions of the harmonics to find it.

The autocorrelation shows you periodicities of the entire waveform. The position of the peak will be the fundamental period of the waveform, which can easily be converted to frequency. If the fundamental is missing, the autocorrelation will still find it (GCD of the harmonics).

Note: If the waveform is not perfectly repetitive, the autocorrelation peak will be shifted and inaccurate. The sound of the human voice and bowed string instruments will work fine, for instance, while plucked string instruments will be slightly high, due to inharmonicity making the harmonics slightly high. On the other hand, the human-perceived pitch is slightly higher than the true fundamental, too, so one or the other method might be more appropriate, depending on what kind of signal you're processing and what you want to get out of it.

$\endgroup$
  • $\begingroup$ Side note: I am actually using the auto-correlation method to find the fundamental frequency currently in an application I have been working on, although for signals where the (periodic) pulses have varying amplitudes, autocorrelation starts to struggle. :-/ Good post nonetheless! :-) $\endgroup$ – Spacey May 31 '12 at 16:01
  • $\begingroup$ Yeah, what I'm trying to get at is what can you glean from one that you can't from the other (at least not as easily)? $\endgroup$ – Daniel R Hicks May 31 '12 at 17:34
  • $\begingroup$ @DanielRHicks: the fundamental frequency of a waveform $\endgroup$ – endolith May 31 '12 at 17:50
  • 1
    $\begingroup$ @DanielRHicks From my (recent) experience, like endolith also mentions, I believe the autocorr is better at gleaning the fundamental frequency than the DFT. The DFT will give you all the harmonics which might or might not be of comparable amplitudes to the fundamental, whereas the autocorr will simply give you the position of the next highest peak off center, which corresponds to your fundamental. (There are ways to use FFT nicely to ascertain fundamental, as mentioned here ccrma.stanford.edu/~pdelac/154/m154paper.htm , but they require more processing). $\endgroup$ – Spacey May 31 '12 at 18:44
7
$\begingroup$

For starters, autocorrelation is a function of the relative time only for WSS processes, otherwise it depends on the absolute times: $\mathrm R_X(t_1,t_2) \equiv \mathbb E[X(t_1)^* X(t_2)]$

Secondly, it is wrong to say "time is just inverse frequency" because frequency is a characteristic of periodic processes. The autocorrelation is not generally a periodic process, however one may find a periodic approximation (extension) of it.

Finally, a great many functions besides the autocorrelation have a Fourier transform; why identify it with the autocorrelation, which is merely a particular function? Note that the Fourier transform is not inherently associated with stochasticity; any nice, absolutely integrable function has a Fourier transform. In the case of periodic functions, you can consider the Fourier series.

I haven't developed an intuitive concept for autocorrelation -- that's what I'm groping for.

The autocorrelation is a measure of how similar a signal at different lags is to itself. This is useful in investigating potential periodic behavior. If your signal is periodic, shifting it by multiples of the period will yield a perfect match. If it is not but has periodic or quasi-periodic components, the autocorrelation will determine their energy.

$\endgroup$
  • 4
    $\begingroup$ +1. Minor quibble- a function doesn't have to be periodic to have a Fourier transform, it just has to be periodic to have a Fourier series. $\endgroup$ – Jim Clay May 30 '12 at 19:52
  • 1
    $\begingroup$ Yeah, seems to me that ANY time series has (or can have) a Fourier transform. Doesn't have to be periodic. Likewise for autocorrelation -- an autocorrelation can be performed on any time series. The question is about what the results "mean" -- the information about the signal that can be derived from either. $\endgroup$ – Daniel R Hicks Jun 2 '12 at 11:09
5
$\begingroup$

For a time limited window of sampled data, you can derive the autocorrelation from the DFT, but not vice-versa. Therefore the DFT contains more information about that time window of data.

$\endgroup$
1
$\begingroup$

I realize the two are derived using different algorithms

Well, you can also get to the autocorrelated signal by taking the Fourier transform of the power spectrum, so I geuss you can say that the 2 are related by by doing 1 algorithm twice with some squaring in the middle :)

If you think more deeply about what that means, you realise that if you have a harmonic signal, its frequency spectrum will have 'periodic' spikes. Taking the fourier transform once more will summarise this information into a potentially more useful form for further computation. Hope that adds another angle of thought for you.

$\endgroup$
  • $\begingroup$ It sure would be nice if we could transform our raw data to get a "summary", and then apply that same transform to the summary data to get a higher-level summary. Alas, the Fourier transform doesn't actually do that -- applying it a second time (to the frequency data) gives you the original time-series data back. This is the surprising-to-me "duality property" of the Fourier transform. $\endgroup$ – David Cary Jun 15 '12 at 19:20
  • $\begingroup$ Your statement does not hold if you apply a non linear operation to the signal in the frequency domain. In this case, you squre the data to get to the power spectrum before performing the second stage transform en.wikipedia.org/wiki/Wiener–Khinchin_theorem. $\endgroup$ – learnvst Jun 16 '12 at 8:41
  • $\begingroup$ Another example of this non-linear "fft sandwich" processing is the cepstrum en.wikipedia.org/wiki/Cepstrum $\endgroup$ – learnvst Jun 16 '12 at 8:44

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.