## Fourier Transform

It was a significant discovery in mathematics that any function can be expanded as a sum of harmonic functions (sines and cosines) and the resulting expression is known as Fourier series. A harmonic of repeating signals such as sunusoidal wave is a wave with a frequency that is a positive integer multiple of the frequency of the original wave, known as the fundamental frequency. The original wave is called the first harmonic, the following harmonics are known as higher harmonics. Any function can also be expanded in terms of polynomials and the resulting expression is known as Taylor series. If the underlying forces are harmonic and there possibly exists some periodicity, then the use of harmonic series is more useful than using polynomials as it produces simpler equations. It is possible to discover a few dominating terms from such series expansion which may help identify the known natural forces with the same period.
Let the symbol $h(t)$ represent a continuous function of time. The Fourier transform is a function of
frequency $f$.

$H_T(f) = \int_{-\infty}^{\infty} h(t) e^{2 \pi i f t} dt$
$e^{2 \pi i f t} = cos(2\pi f t) + i sin(2\pi f t)$

The amplitude and the phases of the sine waves can be found from this result. Given data $h(t)$, we can find the Fourier transform $H(f)$ using Inverse Fourier transform.

$h(t) = \int_{-\infty}^{\infty} H_T(f) e^{-2 \pi i f t} dt$

The spectral power $P$ is defined as the square of the Fourier amplitude:

$P_T(f) = |H_T(f)|^2$

However, real data does not span infinite time and most likely be sampled only at a few discrete points over time. Suppose that, we received values of $h(t)$ at times $t_j$, then an estimate of the Fourier transform is made by using summation. The inverse transform is also shown using the summation.

$h_j \equiv h(t_j)$
$H(f) \equiv \sum_{j=0}^{N-1} h_j e^{2 \pi i f t_j}$

The data are desired to be sampled from equally spaced time as nice statistical properties are available in such regular case. If the interval between equally spaced data points is $\Delta t$, then the highest frequency that will appear in the fourier transform is given by the Nyquist-Shannon sampling theorem. The theorem states “If a function $f(t)$ contains no frequencies higher than $f$ Hz, then it is completely determined by giving its ordinates at a series of points spaced $\frac{1}{2f}$ seconds apart”. Therefore, the Nyquist frequency (highest frequency) is given by the following equation.

$f_N = \frac{1}{2\Delta t}$

The lowest frequency is the one that gives one full cycle in the time interval $T$. The other frequencies to evaluate is the multiples ($f_k$) of the low frequency $f_L$. And, also we can derive the symmetric pair of equations. Moreover, if $h(t)$ is band-limited (no frequencies below $f_L$ or above $f_N$), then there is a relationship between the continuous function $h(t)$ and the discrete values $H_k$.

$f_L = \frac{1}{T}$
$f_k = kf_L$
$H_k \equiv \sum_{j=0}^{N-1} h_j e^{2 \pi i jkf_L t_j}$
$h_j = \sum_{k=0}^{N-1} H_k e^{2 \pi i jkf_L t_j}$
$h(t) = \sum_{k=0}^{N-1} H_k e^{2 \pi i kf_L t}$ (when band limited)

## Periodogram

Fourier transform give us the complex numbers and the square of the absolute value of these numbers represent the periodogram. This is the first form of numerical spectral analysis and is used to estimate spectral power. Even though the data points collected are at evenly spaced specific discrete time, it is possible to evaluate periodogram at any frequencies.

## Fast Fourier Transform (FFT)

We can calculate the Fourier transform very efficiently by using FFT. It requires data at equally-spaced time points, and is most efficient when the number of points is an exact power of two. Interpolation is often used to produce the evenly-spaced data which may introduce additional bias and systematic eror. For real data consisting of $N$ data points $y_j$, each taken at time $t_j$, the power spectrum outputs a set of $N+1$ data points. The first and the last data points are the same, and they represent the power at frequency zero. The second through to the $N/2 + 1$ data points represent the power at evenly-spaced frequencies up to the Nyquist frequency. The spectral power for a given frequency is distributed over several frequency bins, therefore an optimum determination of the power requires combining these information and proper investigation of leakage. FFT, generally, calculates the amplitude for a set of frequencies. N/2 complex amplitudes are calculated at N/2 different frequencies. Because, these may not be the true frequencies present in the record, we subtract the mean from the data and then pad it with zeros to overcome this challenge.

## Aliasing

The time series consists of measurements made at a discrete, equally spaced, set of times on some phenomenon that is actually evolving continuously, or at least on a much finer time scale. For example, samples of Greenland Ice represent the temperature every 100 years, but if the sampling is not precisely spaced by a year, we will sometimes measure winter ice, and other times measure summer ice. Even without the existence of long-term variation in the temperature, fluctuations (jumping up and down) in the data can be noticed. So, there can be frequencies higher than the Nyquist frequency associated with the sampling interval. Thus a peak in the true spectrum at a frequncy beyond the Nyquist frequency may be strong enough to be seen(aliased) in the spectrum which may give the impression that a frequency is significant when it is not. Or, a peak may partly obscure another frequency of interest. This phenomenon is known as aliasing.

## Tapering

Fourier transform is defined for a function on a finite interval and the function needs to be periodic. But with the real data set, this requirment is not met as the data end suddenly at t=0 and t=T and can have discontinuities. This discontinuity introduces distortions (known as Gibbs phenomenon) in fourier transform and generates false high frequency in the spectrum. Tapering (using data window) is used to reduce these artificial presence. The data $y=f(t)$ is multiplied by a taper function $g(t)$ which is a simple, slowly varying function, often going towards zero
near the edges. Some of the popular tapers are:

1. Sine taper $g(t) = sin(\pi t/T)$
2. Hanning (offset cosine) taper $g(t) = \frac{1}{2}(1-cos(2\pi t/T))$
3. Hamming taper $g(t) = 0.54 - 0.46cos(2 \pi t/T)$
4. Parzen or Bartlett (triangle) window $g(t) = 1 - (t - T/2)/(T/2)$
5. Welch (parabolic) window $g(t) = 1 - (t - T/2)^2/(T/2)^2$
6. Daniell (untapered or rectangular) window $g(t) = 1$

The frequency resolution in the spectrum of the tapered data is degraded. If the primary interest is the resolution of peaks, then the untapered periodogram is superior. However, tapering significantly reduces the sidelobes and also the bias applied to other nearby peaks by the sidelobes of a strong peak. Because, the taper functions are broad and slowly varying and their fourier transform FT(g) are narrow. The effect of tapering the data is to convolve the fourier transform of the data with the narrow fourier transform of the taper function which amounts to smoothing the spectral values.

$FT(fg) = FT(f) * FT(g)$

<

p style=”text-align:justify;”> // Sine taper t <- seq(0,1, by=0.01) T <- 1 g <- sin(pi * t * T) plot(t, g, t='l', col=1, ylab='g(t)')

// Hanning (offset cosine) taper
g2 <- 1/2 * (1-cos(2*pi*t/T))
lines(t, g2, t=’l’, col=2)

// Hamming
g3 <- 0.54 – 0.46 * cos(2*pi*t/T)
lines(t, g3, t=’l’, col=3)

// Parzen or Bartlett (triangle) window
g4 0.5, 1 – (t-T/2)/(T/2), 2*t)
lines(t, g4, t=’l’, col=4)

// Welch (parabolic) window
g5 <- 1 – (t-T/2)^2/(T/2)^2
lines(t, g5, t=’l’, col=5)

// Daniell window
g6 <- rep(0.5, length(t))
g6 <- ifelse(t <= 0.2, 0, g6)
g6 = 0.8, 0, g6)
lines(t, g6, t=’l’, col=6)

legnd = c(‘Sine’, ‘Hanning’, ‘Hamming’, ‘Bartlett’, ‘Welch’, ‘Daniell(20%)’)
legend(‘topleft’, legend=legnd ,col=1:6, lty=1, cex=0.75)

## Multitaper Analysis

We apply taper or data window to reduce the side lobes of the spectral lines. Basically we want to minimize the leakage of power from the strong peaks to other frequencies. In multitaper method, several different tapers are applied to the data and the resulting powers then averaged. Each data taper is multiplied element-wise by the signal to provide a windowed trial from which one estimates the power at each component frequency. As each taper is pairwise orthogonal to all other tapers, the windowed signals provide statistically independent estimates of the underlying spectrum. The final spectrum is obtained by averaging over all the tapered spectra. D. Thomson chose the Slepian or discrete prolate spheroidal sequences as tapers since these vectors are mutually orthogonal and possess desirable spectral concentration properties. Multitaper method can suppress sidelobes but have higher resolution. If we use few tapers, the resolution won’t be degraded, but then sidelobe reduction won’t happen much. So, there is a trade-off which is often misunderstood.

## Blackman-Tuckey Method

Blackman and Tuckey prescribed some techniques to analyze a continuous spectrum that was biased by the presence of sidelobes of strong peaks in the ordinary periodogram. Blackman-Tuckey(BT) method was developed before 1958, prior to the FFT(Fast Fourier Transform) method. A discrete fourier transform of N points would
require the calculation of $N^2$ sines and cosines. With the slower computer in the pre-FFT days, the calculation of fourier transform was thus expensive. BT method has reduced the time by reducing the size of the dataset by a factor of the lag in the autocorrelation calculation. BT method is based on a fundamental theorem of Fourier transform that the Fourier transform of a correlation is equal to the product of the Fourier transforms. The correlation of two functions $g(t)$ and $h(t)$ is given by the first equation below.

$C(\tau)=g\otimes h= \int_{-\infty}^{\infty} g(t) h(t+\tau) d\tau$
$FT(g\otimes h) = FT(g) FT(h)$

When g = h, it is called Wiener-Khintchine theorem. Here, P is the spectral power.

$FT(g\otimes g) = |FT(g)|^2 = P$

The algorithm in BT method calculates partial autocorrelation function, defined by

$A_{BT}(\tau) = \int_{0}^{N/l} f(t+\tau)f(t) dt$

Here, N is the length of the data set but we integrate only upto $N/l$. $l$ is associated with the lag. When $l=3$ (recommended by Blackman and Tuckey) is used, we say that “a lag of 1/3” is used. Now the fourier transform of partial autocorrelation function $A_{BT}$ gives us the spectral power. Moreover, the symmetric property of the partial autocorrelation function $(A(-\tau) = A(\tau))$ saves half of the computation time.

$FT(A_{BT}) = \int_{-\infty}^{\infty} e^{2\pi i ft } A_{BT}(\tau) d \tau = P_{BT}(f)$
$P_{BT}(f) = 2 \int_{0}^{\infty} cos(2\pi f) A_{BT}(\tau)$

If $l=1$, then it is basically the full autocorrelation function $A(\tau)$ and gives the same answer as the ordinary periodogram.

$P(f) = 2 \int_{0}^{\infty} cos(2\pi f) A(\tau) = FT(A)$

Because we are using partial correlation function instead of the full correlation, the spectral power function gets smoother. Therefore, we lose resolution in the BT method. However, it averages the sidelobes into the main peak, and thereby gives a better estimate of the true power. The smoothing in BT method is different from the smoothing when we use a taper. With a taper, the fourier transform is smoothed, where as with Blackman-Tukey, it is the spectral power which gets smoothed. A spectral amplitude that is rapidly varying will be averaged to zero with a taper. But in BT method, a rapidly varying amplitude does not necessarily average to zero, since the process of squaring can make the function positive over the region of smoothing. The tapering does not
average the sidelobes into the main peak. Because, shift in the time scale behaves like phase modulation. The sidelobes, when tapering is applied, will not have the same phase, and if averaged in amplitude, they can reduce the strength of the peaks. A major challenge in the BT method is that we will have to estimate the proper lag to use before doing all the calculations. Blackman and Tukey recommended starting with the value 1/3 for the lag.

## Lomb-Scargle Periodogram

The classic periodogram requires evenly spaced data, but we frequently encounter with unevenly spaced data in paleoclimatic research. Lomb and Scargle showed that if the cosine and sine coefficients are normalized separately, then the classic periodogram can be used with unevenly spaced data. If we have a data set $(t_k, y_k)$, we first calculate the mean and variance:

$\bar{y} = \frac{1}{N} \sum_{k=1}^{N}y_k$
$\sigma^2 = \frac{1}{N-1} \sum_{k=1}^{N}[y_k - \bar{y}]^2$

For every frequency f, a time constant $\tau$ is defined by

$\tau = \frac{ \sum_{k=1}^{N}sin(4\pi f t_k)}{\sum_{k=1}^{N}cos(4\pi f t_k)}$

Then the Lomb-Scargle periodogram of the spectral power $P(f)$ at frequency f is given by

$P(f) = \frac{1}{2\sigma^2}\frac{ \sum_{k=1}^{N}(y_k – \bar{y} ) [cos(2\pi f (t_k-\tau))]^2}{\sum_{k=1}^{N}cos^2(2\pi f (t_k-\tau))} + \frac{ \sum_{k=1}^{N}(y_k – \bar{y} ) [sin(2\pi f (t_k-\tau))]^2}{\sum_{k=1}^{N}cos^2(2\pi f (t_k-\tau))}$

With evenly spaced data, two signals of different frequencies can have identical values which is known as Aliasing. That is why the classic periodogram is usually shown with the frequency range from 0 to 0.5, as the rest is a mirrored version. But with Lomb-Scargle periodogram, the aliasing effect can be significantly reduced.

## Maximum Likelihood Analysis

In maximum likelihood method, we adjust the parameter of the model and ultimately find the parameters with which our model have the maximum probability/likelihood of generating the data. To estimate the spectral power, we first select a false alarm probability and calculate the normalized periodogram. We identify the maximum peak and test it against the false alarm probability. If the maximum peak meets the false alarm test, we determine the amplitude and phase of the sinusoid representing the peak. Then we subtract the sinusoidal curve from the data which also removes the annoying sidelobes associated with that peak. After peak removal, the variance in the total record is also reduced. Now, with the new subtracted data, we continue finding the other stronger peaks following the same procedure. We stop when a peak does not meet the false alarm test. We need to carefully choose the false alarm probability, as if it is too low, we can miss some significant peaks; it is too low, we can mislabel noise as peaks.

## Maximum Entropy Method

It is assumed that the true power spectrum can be approximated by an equation which has a power series. This method finds the spectrum which is closest to white noise (has the maximum randomness or “entropy”) while still having an autocorrelation function that agrees with the measured values – in the range for which there are measured values. It yields narrower spectral lines. This method is suitable for relatively smooth spectra. With noisy input functions, if very high order is chosen, there may occur spurious peaks. This method should be used in conjuction with other conservative methods, like periodograms, to choose the correct model order and to avoid getting false peaks.

## Cross Spectrum and Coherency

If a climate proxy $a(t)$ is influenced or dominated by a driving force $b(t)$, we can use cross spectrum to see if their amplitudes are similar. Cross spectrum is given by the product of the fourier transform.

$C(f) = A(f) B^*(f)$

where A is the Fourier transform of a and B is the complex conjugate of the fourier transform of b. If we want to know whether two signals are in phase with each other, regardless of amplitude, then we can take the cross spectrum, square it, and divide by the spectral powers of individual signals using the following equation for coherency. Coherency measures only the phase relationship and is not sensitive to amplitude which is a big drawback.

$c(f) = \frac{|C(f)|^2}{P_a(f) P_b(f)}$

Coherency is valuable if two signals that are varying in time, stay in phase over a band of frequencies instead of a single frequency. Therefore, a band of adjacent frequancies are used in the averaging process to compute coherency:

$coherency(f) = \gamma^2(f) = \frac{||^2}{ }$

## Bispectra

In bispectra, coherency relationship between several frequencies are used. A bispectrum shows a peak whenever (1) three frequencies $f_1$, $f_2$ and $f_3$ are present in the data such that $f_1 + f_2 = f_3$ and (2) the phase relationship between the three frequencies is coherent for at least a short averaging time for a band near these frequencies. If the nonlinear processes in driving force (e.g. eccentricity or inclination of the orbit of earth) has coherent frequency triplets, then the response (i.e. climate) is likely to contain same frequency triplet. For example, $\delta ^{18}O$ is driven by eccentricity, we should be able to find eccentricity triplet. Thus, by comparing the bispectrum plot of climate proxy with the bispectrum plot of the driving forces, we can verify the influences of driving forces.

## Monte Carlo Simulation of Background
Monte carlo simulation is extremely useful to answer the questions like whether the data is properly tuned or not, whether the timescale is incorrect, whether some spectral power is being leaked to adjacent frequencies, whether the peak has real structure and also to understand the structures near the base of the peak (a shoulder) in a spectral analysis. Generally monte carlo simulation is run multiple times. For each simulation, a real signal(sinusoidal wave) is generated, then random background signal is added, then the spectral power is calculated to look for shoulders. In this way, the frequency of the shoulder occurence can be measured and the randomness can be realized. It is important to create background that behaves similarly to the background in real data. Dissimilar background will cause false conclusion. We also need to estimate the statistical significance of the peaks very carefully.

(This article is a quick review of the fourier spectral analysis from the book “Ice Ages And Astronomical Causes- (Data, Spectral Analysis and Mechanics) by Richard A. Muller and Gordon J. MacDonald