# Fast Fourier Transform

The Fast Fourier Transform is one of the most used algorithms that are used to compute the Discrete Fourier Transform.
The Fourier Transform is used in many applications given its ability to transform a time-series into its equivalent frequency representation.

The Fourier Transform X(k) of the time-series x(k)

x(k) = x0, x1, x2, ..., xk, ..., xN-1

is the following expression:

X(n) = 1/N * ∑k=0 N-1 x(k) e-jk2πn/N

The Fourier Transform has several interesting properties:
The first value of the transformed series X(0) is the average of the time-series (DC component).
The highest frequency sample is called the Nyquist frequency. This is the maximum frequency that can be represented using a Fourier Transform. This frequency is also the maximum that must be present in the time-series in order for the signal to be reconstructed exactly from the transform.

Before applying the Fourier Transform to your data yu should cosider detrending it. Leaving a trend in place puts a lot of energy at the lowest frequencies and adds a DC component. This normally impaires the frequency estimate (see below).
The Fourier Transform has several other interesting mathematical properties:

Linearity: a xk + b yk transforms into: a Xk + b Y k
Scaling: xk/a transforms into: a Xa k
Shifting: xk+a transforms into: X k e -2 j π a k
Duality: 1/N xN-k transforms into: Xk
Convolution: xk * yk transforms into: Xk Yk

These are sample Fourier Transforms of well known signals:
 Sinusoidal Sinusoidal Sinusoidal and Trend Sinusoidal, Trend and Noise

References:

Cooley, James W., and John W. Tukey, 1965, "An algorithm for the machine calculation of complex Fourier series"
H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, 1987, "Real-valued fast Fourier transform algorithms"

# Read More Articles on Time-series Forecasting

Forecasting Methods.
Time Series Forecasting.
Forecasting Concepts.
Error Statistics.
Fast Fourier Transform.
Kernel Smoothing.
Savitsky-Golay Smoothing.
Digital Signal Processing.
Curve Analysis.
Markowitz Optimal Portfolio.
Holt Winter's, Series Decomposition and Wavelet Benchmarks.
Use of the Moving Average in Time-series Forecasting.
Denoising Techniques.
Computational Performance.
Moving Averages.
Active Moving Average.
Fractal Projection.
Multiple Regression.
Principal Component Analysis.
Options Pricing with Black-Scholes.
Time-series preprocessing.