Conceptually, how does a Fourier transform differ from an autocorrelation?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.