Fourier Transforms

The Fourier transform is important in mathematics, engineering, and the physical sciences.  Its discrete counterpart, the Discrete Fourier Transform (DFT), which is normally computed using the so-called Fast Fourier Transform (FFT), has revolutionized modern society, as it is ubiquitous in digital electronics and signal processing.  Radio astronomers are particularly avid users of Fourier transforms because Fourier transforms are key components in data processing (e.g., periodicity searches) and instruments (e.g., antennas, receivers, spectrometers), and they are the cornerstores of interferometry and aperture synthesis.

The Fourier transform is a reversible, linear transform with many important properties.  For any function $f(x)$ (which in astronomy is usually real-valued, but $f(x)$ may be complex), the Fourier transform can be denoted $F(s)$, where the product of $x$ and $s$ is dimensionless.  Often $x$ is a measure of time $t$ (i.e., the time-domain signal) and so $s$ corresponds to inverse time, or frequency $\nu$ (i.e., the frequency-domain signal). 

The Fourier transform is defined by
  $$\bbox[border:3px blue solid,7pt]{F(s) \equiv \int^{\infty}_{-\infty}f(x)\,e^{-2\pi i s x}\,dx~,}\rlap{\quad \rm {(SF1)}}$$
which is usually known as the forward transform, and
$$\bbox[border:3px blue solid,7pt]{f(x) \equiv \int^{\infty}_{-\infty}F(s)\,e^{2\pi i s x}\,ds~,
}\rlap{\quad \rm {(SF2)}}$$
which is the inverse transform.  In both cases, $i \equiv \sqrt{-1}$. Alternative definitions of the Fourier transform are based on angular frequency ($\omega = 2\pi \nu$), have different normalizations, or the opposite sign convention in the complex exponential.  Since Fourier transformation is reversible, the symmetric symbol $\Leftrightarrow$ is often used to mean "is the Fourier transform of"; e.g., $F(s) \Leftrightarrow f(x)$.

The complex exponential is the heart of the transform.  A complex exponential is simply a complex number where both the real and imaginary parts are sinusoids.  The exact relation is called Euler's formula
$$\bbox[border:3px blue solid,7pt]{e^{i\phi} = \cos\phi + i\sin\phi,}\rlap{\quad \rm {(SF3)}}$$
which leads to the famous (and beautiful) identity $e^{i\pi}+1=0$ that relates five of the most important numbers in mathematics.  Complex exponentials are much easier to manipulate than trigonometric functions, and they provide a compact notation for dealing with sinusoids of arbitrary phase, which form the basis of the Fourier transform.

Complex exponentials (or sines and cosines) are periodic functions, and the set of complex exponentials is complete and orthogonal.  Thus the Fourier transform can represent any piecewise continuous function and minimizes the least-square error between the function and its representation.  There exist other complete and orthogonal sets of periodic functions; for example, Walsh functions (square waves) are useful for digital electronics.  Why do we always encounter complex exponentials when solving physical problems?  Why are monochromatic waves sinusoidal, and not periodic trains of square waves or triangular waves?  The reason is that the derivatives of complex exponentials are just rescaled complex exponentials.  In other words, the complex exponentials are the eigenfunctions of the differential operator.  Most physical systems obey linear differential equations.   Thus an analog electronic filter will convert a sine wave into another sine wave having the same frequency (but not necessarily the same amplitude and phase), while a filtered square wave will not be a square wave.  This property of complex exponentials makes the Fourier transform uniquely useful in fields ranging from radio propagation to quantum mechanics.

The Discrete Fourier Transform

The continuous Fourier transform converts a time-domain signal of infinite duration into a continuous spectrum composed of an infinite number of sinusoids.  In astronomical observations we deal with signals that are discretely sampled, usually at constant intervals, and of finite duration or periodic.  For such data, only a finite number of sinusoids is needed and the Discrete Fourier Transform (DFT) is appropriate.  For almost every Fourier transform and property, there is a related theorem or property for the DFT.  The DFT of $N$ uniformly sampled data points $x_j$ (where $j = 0,\dots,N-1$) and its inverse are defined by
$$\bbox[border:3px blue solid,7pt]{X_k = \sum_{j=0}^{N-1}x_j\,e^{-2\pi i j k/N}}\rlap{\quad \rm {(SF4)}}$$ and
$$\bbox[border:3px blue solid,7pt]{x_j = \frac{1}{N}\sum_{k=0}^{N-1}X_k\,e^{2\pi i j k/N}~.}\rlap{\quad \rm {(SF5)}}$$
Once again, sign and normalization conventions may vary, but our definition is the most common.  The continuous variable $s$ has been replaced by the discrete variable (usually an integer) $k$.

The result of the DFT of an N-point input time series is an N-point frequency spectrum, with Fourier frequencies $k$ ranging from $-(N/2-1)$, through the 0-frequency or so-called "DC" component, and up to the highest Fourier frequency N/2.  Each bin number represents the integer number of sinusoidal periods present in the time series.  The amplitudes and phases represent the amplitudes $A_k$ and phases $\phi_k$ of those sinusoids.  In summary, each bin can be described by $X_k = A_k\,e^{i\phi_k}$.

For real-valued input data, however, the resulting DFT is hermitian—the real-part of the spectrum is an even function and the imaginary part is odd, such that $X_{-k} = \overline{X_k}$, where the bar represents complex conjugation.  This means that all of the "negative" Fourier frequencies provide no new information.  Both the k=0 and k=N/2 bins are real-valued, and there is a total of N/2+1 Fourier bins, so the total number of independent pieces of information (i.e. real and complex parts) is $N$, just as for the input time series.  No information is created or destroyed by the DFT.

Other symmetries exist between time- and frequency-domain signals as well:

Usually the DFT is computed by a very clever (and truly revolutionary) algorithm known as the Fast Fourier Transform or FFT.  The FFT was discovered by Gauss in 1805 and re-discovered many times since, but most people attribute its modern incarnation to James W. Cooley and John W. Tukey ("An algorithm for the machine calculation of complex Fourier series," Math. Comput. 19, 297–301) in 1965.  The key advantage of the FFT over the DFT is that the operational complexity decreases from $O(N^2)$ for a DFT to $O(N\log_2(N))$ for the FFT.  Modern implementations of the FFT (such as FFTW) allow $O(N\log_2(N))$ complexity for any value of $N$, not just those that are powers of two or the products of only small primes.

Sampling Theorem

For a DFT to represent a function accurately, the original function must be sampled at a sufficiently high rate.  The appropriate rate for a uniformly sampled time series is determined by the Nyquist-Shannon Theorem or Sampling Theorem.  This theorem states that any continuous baseband signal (signal extending down to zero frequency) may be identically reconstructed if the signal is bandwidth limited and the sampling frequency is at least twice the bandwidth of the signal (the highest frequency of a baseband signal).  That critical sampling frequency is known as the Nyquist frequency
$$\bbox[border:3px blue solid,7pt]{\nu_{\rm N} =
1/(2\,\Delta t)~,}\rlap{\quad \rm {(SF6)}}$$
where $\Delta t$ is the time between successive samples.

In a DFT, where there are $N$ samples spanning a total time $T = N\,\Delta t$, the frequency resolution is $1/T$.  Each Fourier bin number $k$ represents exactly $k$ sinusoidal oscillations in the original data $x_j$, and therefore a frequency $\nu = k/T$ in Hz.  The Nyquist frequency corresponds to bin $k_{\rm N} = \nu_{\rm N}T = T/(2\,\Delta T) = NT/(2T) = N/2$.  If the signal is not bandwidth limited and higher-frequency components [with $k > N/2$ or $\nu > N/(2T)$ Hz] exist, those frequencies will show up in the DFT aliased back into lower frequencies $f_{\rm a} = N/T - \nu$, assuming that $N/(2T) < \nu < N/T$.  Such aliasing can be avoided by filtering the input data to ensure that it is properly band-limited.