# A Survey on Change Detection and Time Series Analysis with Applications
## 2 Decomposition Methods into Frequency Domain
### Fourier Transform  
An absolutely integrable function \(f\) on \(\mathbb{R}\) is a real- or complex-valued function such that \(\int_{-\infty}^{\infty}|f(t)|\;\mathrm{d}t<\infty\). If \(f\) is an absolutely integrable function on \(\mathbb{R}\), then the Fourier transform of \(f\) for cyclic frequency \(\omega\), denoted \(\hat{f}(\omega)\) is defined as  
\[\hat{f}(\omega)=\int_{-\infty}^{\infty}f(t)e^{-2\pi i\omega t}\;\mathrm{d}t, \tag{1}\]  
where \"\(e\)\" is the Euler's number, and \"\(i\)\" stands for the imaginary number that is a solution of \(x^{2}=-1\). The spectrum of \(f\) is defined as \(s(\omega)=|\hat{f}(\omega)|^{2}\), which measures how many oscillations of cyclic frequency \(\omega\) contribute to \(f\), where for a complex number \(z\), \(|z|\) denotes its absolute value or Abs (1,2). Note that the absolute value of a complex number \(z=a+ib\) is \(|z|=\sqrt{a^{2}+b^{2}}\). A square-integrable function \(f\) on \(\mathbb{R}\) is a real- or complex-valued function such that \(\int_{-\infty}^{\infty}|f(t)|^{2}\;\mathrm{d}t<\infty\). Now if \(f\) is also a square-integrable function on \(\mathbb{R}\), e.g., an energy signal, then the [PERSON]'s theorem (1) (Chapter 2) states that  
\[\int_{-\infty}^{\infty}|f(t)|^{2}\;\mathrm{d}t=\int_{-\infty}^{\infty}|\hat{f }(\omega)|^{2}\;\mathrm{d}\omega. \tag{2}\]  
Equation (2) implies that the total energy may be determined either by integrating \(|f(t)|^{2}\) over all time or by integrating \(|\hat{f}(\omega)|^{2}\) over all cyclic frequencies. Therefore, \(|\hat{f}(\omega)|^{2}\) is interpreted as Energy Spectral Density (ESD) of \(f\). For inverse of the Fourier transform to exist, function \(\hat{f}\) should be absolutely integrable on \(\mathbb{R}\)(1) (Chapter 2). The average power \(P\) of \(f\) over all time is given by \(P=\lim_{\tau\to\infty}(1/\tau)\int_{0}^{\tau}|f(t)|^{2}\;\mathrm{d}t\). For many signals of interest, the Fourier transform does not formally exist. Therefore, one may use a truncated Fourier transform where the signal is integrated only over a finite interval:  
\[\hat{f}(\omega)=\frac{1}{\sqrt{\tau}}\int_{0}^{\tau}f(t)e^{-2\pi i\omega t}\; \mathrm{d}t, \tag{3}\]  
that is the amplitude spectral density. Then the Power Spectral Density (PSD) can be defined as \(\lim_{\tau\to\infty}\mathrm{E}[|\hat{f}(\omega)|^{2}]\), where \(\mathrm{E}[X]\) is the expected value of \(X\)(8) (Chapter 10). The PSD describes how the power of a signal is distributed over frequencies. In the Discrete-Time Fourier Transform (DTTF), the integral in Equation (1) may be replaced with the summation multiplied by a factor, see Equation (4). More precisely, suppose that \(\mathbf{f}=\big{[}f(t_{1}),\dots,f(t_{n})\big{]}\) is a time series of size \(n\). One may define \(\Delta t_{\ell}=\frac{1}{2}(t_{\ell+1}-t_{\ell-1})\) for \(1<\ell<n\), and for the two special cases \(\ell=1\) and \(\ell=n\), define \(\Delta t_{1}=t_{2}-t_{1}\) and \(\Delta t_{n}=t_{n}-t_{n-1}\), respectively. Let \(\Delta t=\sum_{\ell=1}^{n}\Delta t_{\ell}\). The forward discrete summation of the Fourier integral (after dividing by the summation range) for cyclic frequency \(\omega\) is defined as  
\[\hat{f}(\omega)=\frac{1}{\Delta t}\sum_{\ell=1}^{n}\Delta t_{\ell}f(t_{\ell}) e^{-2\pi i\omega t_{\ell}}. \tag{4}\]  
When \(t_{\ell}\) are equally spaced, \(\Delta t_{\ell}\) is independent of \(\ell\), and \(\Delta t_{\ell}/\Delta t=1/n\). The Discrete Fourier Transform (DFT) can be seen as the sampled version (in frequency-domain) of DTT output because computers can only handle a finite number of values, i.e., in DFT, thefrequencies are also discretized. The complexity of computing DFT is in the order of \(n^{2}\) floating operations or \(\mathcal{O}(n^{2})\) for a time series of \(n\) data points. The Fast Fourier Transform (FFT) is an optimized algorithm that computes DFT (for equally spaced time series) but has an order of \(n\log(n)\) floating operations or \(\mathcal{O}(n\log n)\)[1].