The Fourier Transform
===

## Notation
We will refer the process of obtaining the Fourier coefficients as _applying the Fourier operator_ which takes a function of time and outputs a function of frequency. The Fourier sequence (and transform) is the actual function of frequency itself not the operator.

If the support of the Fourier transform is finite, then the Fourier operator can just output the coefficients of each of the Fourier basis. Sounds quite discrete, but that's essentially what is going on in the Fourier sequence operator and the DFT.

## Fourier series (sequence, really)

Any periodic function $f \equiv f(t)$ can be equivalently represented by a discrete (often infinite) sequence of scalars $c_k$ where such that

$$
f(t) = \sum_{k = -\infty}^\infty c_k \, \exp(i 2\pi k t)
$$

where each $c_m$ is given by the inner product of $f$ with $b_m$ (the $m$-th exponential basis function)

$$
c_m = \langle f, b_m \rangle = \int_t f(t) \, \exp(-i2\pi m t) \, dt
$$

The Fourier series (or rather, Fourier sequence) is just $\mathsf{F}f \equiv \mathsf{F}f(m) = c_m$. It is a function of integers, so "discrete-time" (or rather, discrete-frequency, doesn't matter really).

## Infinite period leads to Fourier transform

An excellent discussion of how to arrive at the Fourier transform defined on the continuous frequency domain is given in [Jeremy Kun's Fourier Primer](https://jeremykun.com/2012/05/27/the-fourier-transform-a-primer/).

~~Each fourier basis function $b_k(t) = e^{i 2\pi k t}$, can be "stretched" so that their period is $T$ by simply dividing $t$ by $T$ like~~

$$
b_k(t) = e^{i 2\pi k \frac{t}{T}}
$$

For the purpose of quickly getting to some applications, we just write the Fourier transform here.

Since the Fourier transform is continuous, we will not use subscript notation like $F(m) = c_m$. Instead we write

$$
\mathsf{F} f \equiv \mathsf{F}f(s) = g(s) = \int_t f(t) \, \exp(-i 2\pi s t) \, dt
$$

The expression is exactly the same as the Fourier sequence formula except the input frequency is $s$ - a real number - not an integer. The set of basis exponential functions is uncountably infinite in the case of continuous frequency domain as you would expect.

The synthesis equation is also similar, but we must use the integral instead of sum since there are infinitely many frequencies, not just integer frequencies.

$$
f \equiv f(t) = \int_s \mathsf{F}f(s) \, \exp(i2\pi s t) \, ds
$$

Criticool.

## Identities

The usual identities -

- convolution in time domain corresponds to multiplication in freq domain.
- fourier transform of fourier transform of $f$ is $g = \text{reverse}(f)$ s.t. $g(t) = f(-t)$

## Why convolution is commutative

TODO: Maybe a good discussion. Not super related to DFT.

## DFT - Sampling rate

The _bandwidth_ $B$ of a function is such that $f(s) = 0$ for all $|s| > B$ for which its Fourier transform evaluates to a non-zero value. Fourier transform of a real valued function is always symmetric about the y axis. More on this later.

Sampling theorem says that in order to reconstruct this function (yes, the function itself, in time domain) - you need samples of the form $\langle \frac{k}{2B}, f(\frac{k}{2B}) \rangle$ as $k$ ranges over the integers. This is the Nyquist theorem. As you can see if $B$ is the maximum frequency, the sampling interval should not be more than half of $1/2B$ (the maximum "time period"). But how many samples do you need. Similar symmetrical requirement is posed when we want to reconstruct the Fourier transform - the frequency of the time domain then limits the sampling interval. See [Jeremy Kun's explanation](https://jeremykun.com/2012/06/23/the-discrete-fourier-transform/).

## DFT - Minimum samples ($n_f = n_t = n = 2BL$)

If the function is both time-limited and band-limited then the number of samples required to reconstruct the function in time domain or its Fourier transform (in frequency domain) is the same.

If the function has a finite support $[0, L]$ in time domain and a finite support of $[-B, B]$ in frequency domain, the minimum number of samples needed to recosntruct the function in either the time or frequency domains is the same. This is surprising. Also, is it always $[-B, B]$ - the Fourier transform is always symmetric?

Let number of samples needed to reconstruct in time and frequency domains be $n_t$ and $n_f$. We can write $n_t/L = B$ (_number of samples / total time period = frequency_) (this is hand wavy, maybe will inquire some time). And $n_f / B = L$. Then $n_t = n_f = n = 2BL$.

https://dsp.stackexchange.com/questions/4825/why-is-the-fft-mirrored

## DFT = `continuous_function |> sample |> fourier_operator |> sample`

Let $\delta_k(t) = \delta(t - t_k)$ denote the set of shifted impulese functions where $t_k = k/(2B)$. The result of sampling a function $f$ at every $t_k$ for $k = 1, 2, \ldots,2BL$ is a sequence. To apply the Fourier transform however we will need it to be a function of real numbers.

So if $f$ is a sequence, we can extend it to be defined for all real numbers by setting it to $f(t) = 0$ when $t$ is a non-integer. This brings us to write $f$ as

$$
f(t) = \sum_{k = 0}^n f(t_k) \, \delta_k(t - t_k)
$$
The $f(t_k)$ values are constants in the RHS of the above equation since they don't depend on $t$. We know that $\mathsf{F}\delta(s) = \exp(-2\pi i t_k s)$. Taking the Fourier transform of $f$ and using the linearity property of $\mathsf{F}$, we obtain

$$
\begin{align}
\mathsf{F}f(s) = \sum_{k = 0}^n f(t_k) \, \mathsf{F}\delta_k(s) \\
= \sum_{k = 0}^n f(t_k) \, \exp(-i2\pi t_k s)
\end{align}
$$

This is pretty much like the continuous Fourier transform, but the integral replaced with a discrete sum pretty much. It's sometimes called the "discrete-time Fourier transform".

But we have to sample this function at $n$ intervals of $1/L$ worth of frequency each. Which gives us

$$
\mathsf{DFT}f(s_j) = \sum_{k=0}^{n-1} f(t_k) \, \exp(-i\,2\pi\,t_k\,s_j)
$$

## DFT without any reference to underlying continuous function

We see no problems in directly defining DFT as an operation on lists without invoking the Fourier transform. In order to use only _indices_ instead of time and frequency in the above operations, we note that $t_k = k / 2B$ and $s_j = j/L$ then $t_k\,s_j = kj/(2BL) = kj/n$. Therefore,

$$
\mathsf{DFT}f[j] = \sum_{k=0}^{n-1} f[k] \, \exp(-i\,2\pi\,\frac{k\,j}{n})
$$

## Symmetry of Fourier transform

The DFT and FT both have the property that $\mathsf{F}f(s) = \mathsf{F}f(-s)^*$ if $f$ is a real valued function.

That is, the real part is an even function while the imaginary part is an odd function. Therefore, for the real part, $\mathsf{Re}\,\mathsf{F}$, if the bandwidth on the positive x-axis is $B$, the negative will have bandwidth $-B$, so support length is $2B$

Is the bandwidth the same for the imaginary part? Seems so intuitively. Also see that $\mathsf{Im} \, \mathsf{F}(s) = \mathsf{Re} \, \mathsf{F}(s - \pi/2)$