Statistics and Algorithms / Spectral Analysis /

Fourier Transforms

The Finite Fourier transform of the series \(\{ X(t),t = 1, \ldots ,T\} \) is

\begin{equation} \tilde X\left( {{{2{\kern 1pt} {\kern 1pt} \pi {\kern 1pt} j} \mathord{\left/ {\vphantom {{2{\kern 1pt} {\kern 1pt} \pi {\kern 1pt} j} T}} \right. } T}} \right) = \sum\limits_{t = 1}^T {X\left( t \right)\exp \left( {{{ - 2\pi {\kern 1pt} ij{\kern 1pt} {\kern 1pt} \left( {t - 1} \right)} \mathord{\left/ {\vphantom {{ - 2\pi {\kern 1pt} ij{\kern 1pt} {\kern 1pt} \left( {t - 1} \right)} T}} \right. } T}} \right)} \end{equation}

The frequencies run from 0 to \(2\pi {{\left( {T - 1} \right)} \mathord{\left/{\vphantom {{\left( {T - 1} \right)} T}} \right.} T}\) by increments of \({{2\pi } \mathord{\left/{\vphantom {{2\pi } T}} \right.} T}\).

Note that this is sometimes defined using a \(1/\sqrt T \) multiplier (and \(1/\sqrt T \) also on the inverse transform). We have found that the formula above (with a \(1/T\) multiplier on the inverse) is more convenient as a different scale than \(1/\sqrt T \) often ends up being needed. The instruction FFT computes the Fourier transform and IFT computes its inverse.

RATS uses a Fast Fourier transform algorithm which can transform series of any length, although it is much faster for lengths which are products of powers of two, three and five. It's a general complex FT, so you can apply it to any series, not just real-valued series.

Frequency and Entry Mappings

Different ways of mapping entries to frequencies and back are used in spectral analysis packages. We have chosen the above because our primary interest is in (one-sided) time series data. It means, however, that if you are interested in two-sided sequences (such as the covariogram, or a two-sided distributed lag), you have to do some rearranging.

The two-sided finite sequence

\(\left\{ {x_{ - N} ,x_{ - N + 1} , \ldots ,x_{ - 1} ,x_0 ,x_1 , \ldots ,x_N } \right\}\)

is represented in this mapping as the one-sided series

\(\left\{ {x_0 ,x_1 , \ldots ,x_N ,x_{ - N} ,x_{ - N + 1} , \ldots ,x_{ - 1} } \right\}\)

This is true whether you are inputting the sequence to FFT or getting output from IFT. For instance, if you compute a covariogram by inverse transforming the periodogram, lag 0 (the variance) will be in entry 1, lag 1 in entry 2, etc., and lag –1 (which is identical to lag 1) will be in the last entry, lag –2 in the second to last, etc. The procedure @CSERIESSYMM can be used to properly symmetrize a series. For instance, this sets up a triangular window by defining the front end, then symmetrizing:

cset 2 1 320 = %if(t<=k,1-(t-1)/k,0.0)

@cseriessymm 2

Preparation of Data

Most data used in spectral analysis are prepared in the time domain and then copied to the frequency domain using the instruction RTOC (Real TO Complex). Frequency domain techniques are among the fussiest of all time series techniques concerning data preparation. Applying FFT and IFT in succession will reproduce any series, no matter how non-stationary, but almost any real work done in the frequency domain will require some calculations which are sensitive to improper differencing or detrending.

There are two technical reasons for this:

•Finite Fourier methods treat the data (in effect) as being periodic with period T, where T is the number of data points. Thus, the point “before” entry 1 is entry T. Clearly, if a series has a trend, it can’t be reasonably represented in such a fashion.

•The statistical properties of spectral estimators break down when the series does not have a well-behaved spectral density.

Thus, whenever the method you are using requires you to take the spectrum of a series, you should make sure:

•the series is properly differenced (usually with DIFFERENCE or SET) or detrended.

•the series has a mean of zero, or close to it.

Padding

The length on the FREQUENCY instruction is usually chosen to be a convenient number of frequencies for Fourier analysis. The extra length beyond the actual number of data points is the padding. These extra entries are set to zero when you transfer data using RTOC. There are two considerations in choosing length:

•The exact seasonal frequencies are included if the number of frequencies is a multiple of the number of periods per year. For example, with quarterly data, make sure you use a number divisible by 4, with monthly, divisible by 12, with business day, divisible by 5.

•The Fourier transforms (instructions FFT, IFT and TRFUNC) are much faster for series lengths which have small prime factors (2,3 and 5) than for lengths which are products of large primes. For instance, applying FFT to length \(1024 = 2^{10} \) is roughly 40 times faster than applying it to \(1023 = 3 \times 11 \times 31\). Given the speed of modern computers, this is only a minor consideration if you are just applying the Fourier transform a few times. However, if the Fourier transform is part of a function evaluation for non-linear estimation, a timing gap like that can be quite significant.

You can use the function %FREQSIZE(n) to get a recommended size for \(n\) actual data points. It returns the smallest integer of the form \(2^m S\) which is greater than or equal to \(n\). (\(S\) is the number of periods per year).

For procedures that require filtering in the frequency domain, the series must be padded, preferably to at least double length. To get a recommended length in that case, use 2*%FREQSIZE(n).

Missing values in a data set are replaced by zeros when they are copied to the frequency domain. Thus, you don’t have to concern yourself about undefined elements at the ends of your series, since they will just become part of the padding.

RATS provides the instruction TAPER for applying a taper to a data set prior to Fourier transforming it. A taper scales the ends of the actual data (not the padded series) with a graduated series so that it merges smoothly with the zeros in the padding.

Example

linreg logx 1977:1 2018:7 resids

# constant trend

frequency 1 768 Pad 497 monthly to 768=(12)(64)

rtoc

# resids

# 1