# Fourier Transform

## Contents

The Fourier and inverse Fourier transforms convert a time-series into a power spectrum and vice versa. These are well-known functions used for many applications including finding and characterizing periodicities in time-series analysis and regression, fast convolution and de-convolution, transfer functions for solving systems of differential equations, Bayesian analysis using characteristic functions, and signal filtering.

The discrete Fourier transform involves a time domain and a frequency domain, each with a corresponding index. The points in the time index are equally spaced at intervals of Δt. The points in the frequency index are equally spaced at ΔF . Both indexes have npoints. The interval spacings are related as:

$\Delta t =\frac{1}{n \Delta t}$

The quantity 1/(Δt) is termed the sampling frequency. It should be at least twice the smallest frequency that is present in the underlying continuous signal. See FFT for additional details.

## FFT(x, t, freq)

Computes the Discrete Fourier Transform (DFT) of the time-series «x», indexed by «t», and returns the discrete frequency spectrum as a complex array indexed by «freq». It performs this calculation using the Fast Fourier Transform (FFT) algorithm. The indexes «t» and «freq» must have the same length. This is a complex-valued function -- even if «x» is real-valued, the result in general will be an array of complex numbers. You can apply the Abs() function to the result to obtain the magnitude of the frequency component if you are not interested in the phase. The discrete Fourier transform is defined as

$H_k = \sum_{t=0}^{n-1} x_{t}e^{2j\pi t k /n}$

The computation is fastest when the length of the indexes is a power of 2. It is also reasonably efficient when all the prime factors of the length of the index is small. So, for example, it is fairly efficient when the indexes are a power of 10, since the length factors to powers of 2 and 5, both of which are still small. The computation time increases approximately quadratically with the square of the largest factor.

Examples: For usage examples, please see FFT.

## FFTInv(x, freq, t)

Computes the inverse Discrete Fourier Transform (DFT) using the Fast Fourier Transform (FFT) algorithm. The frequency spectrum, «x», is indexed by «freq», and typically consists of complex numbers encoding both the magnitude and phase of each frequency. Returns the time-series with the indicated spectrum, indexed by «t». The indexes «freq» and «t» must have the same length. See FFTInv().

The inverse DFT is defined as

$H_t = \sum_{k=0}^{n-1} x_{k}e^{-2j\pi t k /n}$

The efficiency of FFTInv() is the same as for FFT(), maximally efficient when the length of the indexes is a power or 2.