Is the Fourier Transform a Change of Basis?
I had always heard engineers describe the Fourier transform as a change of basis. Is that actually true?
Yonder, by ever-brimming goblet’s rim, the warm waves blush like wine.
— Moby Dick, Chapter 37
This article is a sequel to a previous article, What is the Fourier Transform?, which introduces the transform in an accessible way.
This article answers a more subtle question about the mathematical place of the Fourier transform: it’s often loosely referred to as a change of basis. Explaining the exact ways in which this is true (and false!) digs into a lot of the math in the back half of Stein and Shakarchi’s four book Princeton Lectures in Analysis series, specifically in the field of functional analysis.
This article should hopefully also be accessible to anyone who has a solid background in linear algebra, but it might get slightly abstract by the end of the article, so some general “mathematical maturity” might be helpful as well.
Orthogonality and Orthonormal Maps
If you’re already familiar with orthogonality and orthonormal maps, you’re welcome to proceed directly to the next section
Orthogonality
Orthogonality describes two vectors that face in completely unrelated directions; it’s essentially the complete opposite of collinearity: where the two vectors have no common direction.
To understand why this is a desirable feature for a basis to have, consider the representation of the vector $v = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ in the standard (or elementary) basis
\[e_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix},\quad e_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\]we simply have $1e_1 + 1e_2 = v$. (Of course, all vectors are implicitly written in terms of the elementary basis!) Compare on the other hand its representation in the non-orthogonal basis:
\[b_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix},\quad b_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\]$(1/2)b_1 + (1/2)b_2 = v$ isn’t bad at all; just like with the orthogonal basis, the coefficients are even equal! However, we have a couple problems:
Coefficients are coupled. In the orthogonal basis, each coefficient is a single, self-contained dot product against one basis vector: $\alpha = v \cdot e_1 = 1$ and $\beta = v \cdot e_2 = 1$. Computing $\alpha$ has nothing to do with $e_2$, or even the dimension we’re working in. But with the basis $\left\lbrace b_1, b_2 \right\rbrace$, naive projection gives $\alpha \stackrel{?}{=} v \cdot b_1 = 1$ and $\beta \stackrel{?}{=} \frac{v \cdot b_2}{b_2 \cdot b_2} = \frac{3}{5}$, but
\[1 b_1 + \frac{3}{5} b_2 = \begin{bmatrix} 1.6 \\ 1.2 \end{bmatrix} \ne v\]that’s the wrong answer. The correct coefficients, $\alpha = \beta = \frac{1}{2}$, only fall out of solving the full system $\alpha b_1 + \beta b_2 = v$ at once, because $b_2$ has a component pointing along $b_1$, so projecting onto $b_1$ alone “sees” part of $b_2$ too.
Every coefficient in a non-orthogonal basis depends on every other basis vector; nothing can be found in isolation, because we have to force the vectors to cancel each other out. That’s exactly why the coefficient formulas above look the way they do: $a_n$, $b_n$, and $c_n$ are each a single integral of $f$ against one basis function each.
The Pythagorean theorem breaks. In the orthogonal basis, $\lVert v \rVert^2 = 1^2 + 1^2 = 2$, and $\alpha^2 + \beta^2 = 1^2 + 1^2 = 2$ as well: the squared length of $v$ splits cleanly across its coordinates. Try it with the (correct) coefficients $\alpha = \beta = \frac{1}{2}$ in the $\left\lbrace b_1, b_2 \right\rbrace$ basis: $\alpha^2 + \beta^2 = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$, nowhere near $\lVert v \rVert^2 = 2$. What’s missing is a cross term: $\alpha^2\lVert b_1 \rVert^2 + \beta^2 \lVert b_2 \rVert^2 + 2\alpha\beta (b_1 \cdot b_2) = \frac{1}{4} + \frac{5}{4} + \frac{1}{2} = 2$. Without orthogonality, there’s no way to say “this proportion of $v$’s length lives along $b_1$’s direction” without also accounting for how $b_1$ and $b_2$ overlap with each other. This matters when we want to measure how much a single note contributes to a song, for example.
Normality
Normality just describes a vector with length \(1\).
Some computer games have a bug where if we move forwards by pressing W and move sideways by pressing either A or D, then we will actually move faster than if we moved in only one direction. If this bug is present, it’s always better to just turn \(45\degree\) and run diagonally!
Why does this bug crop up?
TODO
Orthonormal Maps
Fourier Series as a Change of Basis, I
The vector space of all square-integrable $p$-periodic functions (for a fixed $p$) has an (appropriately normalized) basis given by the family of pure oscillations at every integer multiple of the fundamental frequency \(1/p\):
\[\ldots, e^{-4\pi i x/p}, \; e^{-2\pi i x/p}, \; 1, \; e^{2\pi i x/p}, \; e^{4\pi i x/p}, \ldots = \left\lbrace e^{2\pi i n x/p} \right\rbrace_{n \in \Z}\]$f$’s coordinates in this basis are the coefficients $c_n$ that we derived above: writing $f(x) = \sum_{n=-\infty}^{\infty} c_n e^{2\pi i n x/p}$ is expanding a vector in a basis, no different in kind from writing $v = \alpha e_1 + \beta e_2$ in the plane. Of course, Euler’s formula \(e^{ix} = \cos(x) + i\sin(x)\) tells us that this basis can be written in terms of sines and cosines.
The Fourier basis is appealing for several reasons, the biggest of which is that it’s orthogonal. This means that our Fourier coefficients are decoupled, and each $c_n$ tells us exactly how much each frequency contributes to \(f\).
The Mathematical Benefits of Orthogonality
For Fourier series this really is a change of basis. For the Fourier transform it isn’t strictly one, for reasons we’ll get to, but the change of basis perspective is still very helpful. For example, given that functions are vectors in this context, we can consider the operation
\[\frac{1}{p}\int_0^p \left( e^{2\pi i \textcolor{#3d8ee8}{m} x/p} \right) \overline{\left( e^{2\pi i \textcolor{#2fa84f}{n} x/p} \right)} \,dx\]which is $0$ whenever $\textcolor{#3d8ee8}{m} \ne \textcolor{#2fa84f}{n}$ and $1$ when $\textcolor{#3d8ee8}{m} = \textcolor{#2fa84f}{n}$. That’s why the coefficient formula for $c_{\textcolor{#2fa84f}{n}}$ looks like an integral against $e^{-2\pi i \textcolor{#2fa84f}{n} x/p}$ instead of a derivative: it’s literally a projection onto the $\textcolor{#2fa84f}{n}$-th basis vector! (You may remember that projections compute ordinary coordinates $\vec v \cdot e_k$ in $\R^n$, where $e_k$ is the $k$-th elementary basis vector, which has all 0 entries except for the $k$-th, which is 1.)
Hilbert Spaces
I’d like to talk about the Fourier transform on a much deeper level, as a higher-level version of a linear transformation between vector spaces. But, just like in linear algebra, there’s very little we can say about a linear transformation $T$ without first discussing its domain and codomain, which we view as vector spaces to understand $T$’s behavior. So, before discussing $\mathcal{F}$ in more depth, I’d like to introduce a clear way to think about spaces of functions.
We can think of all of these functions as living in the vector space of all functions $f: \R \to \C$. This vector space’s dimension is uncountably infinite; because any linear combination in a vector space must be a finite sum, we can’t even reasonably specify a basis.
Why doesn’t this function space have a useful basis?
You might be tempted to argue (as I once tried to) that we could form a basis in this space from the spike functions
\[b_v(x) = \begin{cases} 1 & \text{if } x = v\\ 0 & \text{otherwise}\end{cases}\]We could hopefully build any $f(x)$ with
\[f(x) = \sum_{r \in \R} f(r)b_r(x)\]where $f(r)$ is the coefficient and $b_r(x)$ is the basis vector. Unfortunately, this sum would have uncountably infinitely many terms, and the vector space axioms only cover a finite number of additions. This can be stretched to include countable additions, as in the case of our power or frequency series bases. We cannot reasonably call this a basis for the space without replacing one of the axioms.
Even if we extend as far as countably infinite linear combinations, we end up with functions that just resemble the Dirichlet function
\[1_{\Q}(x) = \begin{cases} 1 & \text{if } x \in \Q\\ 0 & \text{otherwise}\end{cases}\]This function is too nasty for the standard calculus classroom, and from a measure-theoretic perspective is essentially the same as the function that is $0$ everywhere: each of the spikes is just a point and therefore has measure $0$. With some enumeration $q_0, q_1, q_2, \ldots$ for $\Q$, we can apply countable additivity of disjoint sets to obtain
\[\sum_{i=0}^{\infty} \int_{q_i}^{q_i} 1 \, dx = \sum_{i=0}^{\infty} 0 = 0\]So any two functions we could plausibly build using only countable sums differ only by a set of measure zero, and are therefore the same (in the same equivalence class) as far as measure theory is concerned.
The only other option we’re left with is Zorn's lemma which says every vector space has a basis. But Zorn’s lemma relies on the axiom of choice, so it’s completely non-constructive. In other words, we’re hosed.
If we restrict our attention like this to spaces of functions that are well-behaved with respect to something like integration, we can study Hilbert spaces. These spaces are essentially just a vector space with two additional requirements: an inner product and completeness. The main example, and the one this article has been circling, is $L^2$, the square-integrable functions we’ve already been working with. The absolutely integrable functions $L^1$, which we met first, are not one.
Why Square-Integrable and Not Absolutely Integrable?
We met absolutely integrable functions first, and $L^1$ is enough to define Fourier coefficients and the Fourier transform. So why does everything from here on live in $L^2$? Three reasons.
$L^1$ has no inner product. Every norm that comes from an inner product satisfies the parallelogram law, $\lVert f + g \rVert^2 + \lVert f - g \rVert^2 = 2\lVert f \rVert^2 + 2\lVert g \rVert^2$ (expand both sides using $\lVert f \rVert^2 = \langle f, f \rangle$ and the cross terms cancel). The $L^1$ norm fails it: on $[0, 1]$, take $f = 1_{[0, 1/2]}$ and $g = 1_{[1/2, 1]}$, so that $\lVert f \rVert = \lVert g \rVert = 1/2$ while $\lVert f + g \rVert = \lVert f - g \rVert = 1$, giving $2 \ne 1$. So no inner product induces the $L^1$ norm, and $L^1$ is a complete normed space (a Banach space) but not a Hilbert space. The $L^2$ norm is $\sqrt{\langle f, f \rangle}$ by construction.
In $L^1$, the coefficients exist but the series can fail. Kolmogorov constructed an absolutely integrable function whose Fourier series diverges at every point, and even convergence in the $L^1$ norm fails for some $L^1$ functions: the pure oscillations are not a basis of $L^1[0, p]$ in any useful sense. In $L^2[0, p]$ they’re an orthonormal basis, the series converges in norm for every $f$, and $\sum \lvert c_n \rvert^2 = \lVert f \rVert^2$.
On $\R$, neither space contains the other. On a bounded interval $L^2 \subseteq L^1$, but on the whole real line $1/(1 + \lvert x \rvert)$ is square-integrable without being absolutely integrable, and $\lvert x \rvert^{-1/2}$ restricted to $[-1, 1]$ is absolutely integrable without being square-integrable. That’s why the Fourier transform is defined on $L^1(\R)$, where the integral makes sense, and then extended to the Hilbert space $L^2(\R)$, which is the setting for the change-of-basis story at the end of this section.
Inner Products
Inner products are essentially a way to give a mathematically rigorous definition to fuzzy concepts like the length of a vector, the angles between vectors, and so on. It’s a nice way to give extra structure to the vector space and bridge the gap between algebra (where we spend all day talking about vectors) and analysis (where we spend all day talking about distances). In finite-dimensional vector spaces, the inner product is typically the dot product:
\[\langle \vec v, \vec u \rangle = \vec v \cdot \vec u = \vec v^T \overline{\vec u}\](Of course, over the real numbers we have $\overline{\vec u} = \vec u$.)
The definition of an inner product generalizes the useful properties of the dot product:
Definition (Inner Product) Suppose $V$ is a vector space over the field $F$ (for the purposes of this article, either $\R$ or $\C$). Then an inner product on $V$ is a map
\[\langle \cdot, \cdot \rangle : V \times V \to F\]satisfying three properties for any $x, y,$ and $z$ in $V$:
Conjugate symmetry: $\langle x, y \rangle = \overline{\langle y, x \rangle}$, where $\overline{\cdot}$ denotes the (complex) conjugate. In particular, if we’re working over a real vector space, this simplifies to commutativity.
Linearity in the first argument: \(\langle ax + by, z \rangle = a\langle x, z \rangle + b\langle y, z \rangle\) for scalars $a, b$.
Positive definiteness: if $x$ isn’t the zero vector, then $\langle x, x \rangle > 0$.
The inner product induces a norm, $\lVert x \rVert = \sqrt{\langle x, x \rangle}$, which represents the length of the vector. We can then express things like:
Unit vectors as all vectors $x$ such that $\lVert x \rVert = 1$
The angle between two vectors to be $\arccos\left(\langle x, y \rangle / \lVert x \rVert \lVert y \rVert \right)$
and other convenient and familiar ideas, and we can prove things like the triangle inequality $\lVert x + y \rVert \leq \lVert x \rVert + \lVert y\rVert$. These don’t need to be strictly geometric: if you’ve taken a probability class, you’ll be familiar with expected value:
\[\E(f) = \langle x, f \rangle = \int_{-\infty}^{\infty} x f(x)\, dx\]and variance:
\[\Var(f) = \langle (x - \E(f))^2, f \rangle = \int_{-\infty}^{\infty} (x - \E(f))^2 f(x)\, dx\]These are inner products of the probability density function $f$ with respect to two different functions, measuring where $f$’s “center of mass” $\E(f)$ sits against the real line (represented simply by $x$) and how “spread out” $f$ is compared to that center of mass (represented by $(x - \E(f))^2$).
The Fourier and Laplace Transforms of a Probability Density
If $X$ is a random variable with density $f$, two classical probability tools turn out to be exactly the Fourier and Laplace transforms of $f$, just evaluated with a sign flip (and, for the Fourier case, a stray $2\pi$) baked in from convention. (A note on notation: above, $\E(f)$ took the density as its argument; here we switch to the probabilist’s $\E(X)$, the expectation of the random variable. They’re the same number, $\E(X) = \int x f(x)\, dx = \E(f)$, and $\E(g(X)) = \int g(x) f(x)\, dx$ in general.)
The characteristic function of $X$ is $\varphi(t) = \E(e^{itX}) = \int_{-\infty}^{\infty} f(x)\, e^{itx}\, dx$. Matching exponents against $\Fourier{f}(\xi) = \int f(x)\, e^{-2\pi i \xi x}\, dx$ forces $-2\pi \xi = t$, so
\[\varphi(t) = \Fourier{f}\left(-\frac{t}{2\pi}\right)\]The moment generating function of $X$ is $M(t) = \E(e^{tX}) = \int_{-\infty}^{\infty} f(x)\, e^{tx}\, dx$, which lines up with $\Laplace{f}(s) = \int f(x)\, e^{-sx}\, dx$ at $s = -t$:
\[M(t) = \Laplace{f}(-t)\]This is exactly why the characteristic function always exists (for any random variable whatsoever) while the moment generating function often doesn’t: $\lvert e^{itx} \rvert = 1$ for real $t$, so $\varphi$’s defining integral is bounded by $\int f = 1$ and converges absolutely no matter how heavy $f$’s tails are, the same reason the Fourier transform only ever needs absolute integrability. $e^{tx}$ has no such bound for real $t \ne 0$, so $M(t)$ can fail to converge at all: the Cauchy distribution’s tails are exactly heavy enough that $M(t)$ is infinite for every $t \ne 0$, yet its characteristic function is the perfectly ordinary $\varphi(t) = e^{-\lvert t \rvert}$.
Both transforms encode every moment of $X$ in their derivatives at $0$, which is the actual point of introducing them. Differentiating $M$ under the integral sign, $M^\prime(t) = \E(Xe^{tX})$ and $M^{\prime\prime}(t) = \E(X^2 e^{tX})$, so $M^\prime(0) = \E(X)$ and $M^{\prime\prime}(0) = \E(X^2)$, giving
\[\Var(X) = \E(X^2) - \E(X)^2 = M^{\prime\prime}(0) - M^\prime(0)^2\]$\varphi$ carries the same information ($\varphi^\prime(0) = i\E(X)$ and $\varphi^{\prime\prime}(0) = -\E(X^2)$, so $\Var(X) = \varphi^\prime(0)^2 - \varphi^{\prime\prime}(0)$), just with factors of $i$ threaded through the bookkeeping, which is why $M$ is the more convenient of the two whenever it actually exists.
Completeness
The second thing that a Hilbert space needs is completeness with respect to this inner product. This is the quality that distinguishes the real numbers as a superior setting to the rationals for doing calculus: a Hilbert space has no “gaps”. More rigorously, there are certain kinds of sequences called Cauchy sequences, whose terms get arbitrarily close together as the sequence continues. We would expect that these sequences converge, but this only happens in complete spaces; in spaces like $\Q$ that fail to be complete, the limits of these sequences disappear like a coin falling into a storm drain. For example, the sequence that counts out the digits of $\pi$
\[3, 3.1, 3.14, 3.141, 3.1415, \ldots\]is a perfectly valid sequence of only rational numbers, because every term in this sequence has a finite terminating decimal representation.
We would expect this sequence to converge: for any $\epsilon > 0$, you can go far out enough in the sequence that the difference between any later terms will be smaller than $\epsilon$. So intuitively the sequence “stops changing”, so we’d expect it to converge. (That’s what a Cauchy sequence is.)
In the real numbers, this sequence does converge, and the limit is $\pi$. The real numbers are complete because any Cauchy sequence of real numbers converges to a real number.
But even though the sequence is made up of only rational numbers, it fails to converge in $\Q$ because the limit is $\pi$ which isn’t a rational number. It’s as if the rationals have “gaps”, and this sequence slipped through the cracks.
The sequence of locations of a coin at some discrete time frame is roughly analogous to a Cauchy sequence: we expect that the coin will eventually converge to some position in the center (which would be the limit of the sequence), but instead of landing at some point in the center, each coin just disappears.
Most of the theorems in calculus are premised on Cauchy sequences converging — that is, on the space we’re working in being complete.
So far we’ve set up a lot of definitions that do nothing really new or interesting. The point is that Hilbert spaces provide us enough structure to talk about spaces of functions from, for example, $\R \to \R$. The next section cashes that structure in, and finally makes good on the promise to say what $\mathcal{F}$ really is.
Linear Functionals
We’ve actually been using an inner product on functions since the change of basis section. On $p$-periodic functions, define
\[\langle f, g \rangle = \frac{1}{p}\int_0^p f(x)\, \overline{g(x)}\, dx\]This satisfies all three axioms above (conjugate symmetry and linearity are inherited from the integral, and positive definiteness holds once we agree, as measure theory insists, that two functions differing only on a set of measure zero are the same function). It’s the direct analogue of the dot product: multiply matching components and add them up, except now the “components” are the values $f(x)$ and the sum is an integral. Two functions are orthogonal when $\langle f, g \rangle = 0$, and the computation from earlier says exactly that the pure oscillations form an orthonormal set:
\[\left\langle e^{2\pi i m x/p}, e^{2\pi i n x/p} \right\rangle = \begin{cases} 1 & \text{if } m = n \\ 0 & \text{otherwise} \end{cases}\]With this notation the Fourier coefficient formula is a one-liner, $c_n = \langle f, e^{2\pi i n x/p} \rangle$: the projection onto the $n$-th basis vector, just as promised.
Now fix $g$ and think of $\langle \cdot, g \rangle$ as a machine that eats a function and spits out a number. It’s linear in its input, which makes it a linear functional:
Definition (Linear Functional) Let $V$ be a vector space over $F$. A linear functional is a linear map $\phi: V \to F$. If $V$ has a norm, $\phi$ is bounded if there is a constant $C$ with $\lvert \phi(x) \rvert \le C \lVert x \rVert$ for all $x \in V$.
Boundedness is the functional-analysis word for continuity: a bounded functional can’t send nearby inputs to wildly different outputs. Every functional in this article is linear, and every one of them has the same shape, an integral of $f$ against one fixed kernel $g$:
\[\phi_g(f) = \int f(x)\, \textcolor{#d946ef}{g(x)}\, dx\]| Operation | Formula | Kernel $\textcolor{#d946ef}{g(x)}$ |
|---|---|---|
| Inner product against $h$ | $\displaystyle \int f(x)\, \textcolor{#d946ef}{\overline{h(x)}}\, dx$ | $\textcolor{#d946ef}{\overline{h(x)}}$ |
| Fourier coefficient $c_n$ | $\displaystyle \int\limits_0^p f(x)\, \textcolor{#d946ef}{\frac{1}{p} e^{-2\pi i n x/p}}\, dx$ | $\displaystyle \textcolor{#d946ef}{\frac{1}{p} e^{-2\pi i n x/p}}$ |
| Fourier transform at $\xi$ | $\displaystyle \int f(x)\, \textcolor{#d946ef}{e^{-2\pi i \xi x}}\, dx$ | $\textcolor{#d946ef}{e^{-2\pi i \xi x}}$ |
| Laplace transform at $s$ | $\displaystyle \int f(x)\, \textcolor{#d946ef}{e^{-sx}}\, dx$ | $\textcolor{#d946ef}{e^{-sx}}$ |
| Expected value | $\displaystyle \int f(x)\, \textcolor{#d946ef}{x}\, dx$ | $\textcolor{#d946ef}{x}$ |
| Variance | $\displaystyle \int f(x)\, \textcolor{#d946ef}{(x - \E(f))^2}\, dx$ | $\textcolor{#d946ef}{(x - \E(f))^2}$ |
The Laplace transform is new here: a close cousin of the Fourier transform with a real exponent in place of an imaginary one, which sees a lot of use solving linear ordinary differential equations. (The version used for initial-value problems integrates over $[0, \infty)$ only; the two-sided version in the table is the one that matches the moment generating function from the probability aside.) Because a real exponential grows on one side, $\Laplace{f}(s)$ only exists for $f$ that decays fast enough to beat it, the same reason moment generating functions sometimes fail to exist.
In inner product notation, $\phi_g(f) = \langle f, \overline{g} \rangle$, so every row of the table is an inner product against a fixed function. The catch, and it matters for what comes next, is that the kernel isn’t always in the space. On $[0, p]$ everything is fine. On all of $\R$, the functions $x$, $e^{-sx}$, and $e^{-2\pi i \xi x}$ aren’t square-integrable, so those rows are inner products in form only.
Why They All Take the Same Form
Every object in this section (the inner product itself, the Fourier transform, the Laplace transform, expected value, variance) takes the same shape: pair $f$ against some fixed kernel and integrate. That’s not a coincidence dressed up to look tidy. It’s forced, by a single theorem, applied twice in two different ways.
Theorem (Riesz Representation) Let $H$ be a Hilbert space over $F$. Every bounded linear functional $\phi: H \to F$ has the form $\phi(f) = \langle f, v \rangle$ for a unique $v \in H$.
Any reasonable, bounded and linear, way of turning a function into a number already is an inner product against some fixed function; there’s no other shape available. The mechanism is completeness doing real work: a closed subspace $N \subseteq H$ splits as $H = N \oplus N^\perp$, because the parallelogram law makes “closest point in $N$” a strictly convex problem, and completeness is what guarantees the minimizing sequence for that problem actually converges rather than escaping toward a missing limit point. Apply that splitting to $N = \ker\phi$, and $N^\perp$ collapses to one dimension, exactly enough room to solve for $v$. That’s the direct half: every bounded functional on a Hilbert space of functions is an inner product against a fixed function, and on $L^2$ the inner product is $\int f\bar g$.
The indirect half explains expected value and variance. A probability density is a Radon-Nikodym derivative, $f = dP/dm$ against Lebesgue measure, and the cleanest proof that such a derivative exists (due to von Neumann) invokes Riesz representation as a lemma: form $\lambda = P + m$, note that $g \mapsto \int g\, dP$ is a bounded functional on $L^2(\lambda)$, apply Riesz representation there to get a representing function, and a short argument turns it into $f$ itself. So $\E(g(X)) = \int g(x) f(x)\, dx$ has its integral shape for the same underlying reason as $\langle f, v \rangle$, just one theorem removed.
Fourier and Laplace are a different story: $e^{2\pi i \xi x}$ and $e^{sx}$ aren’t themselves square-integrable, they don’t decay, so $\hat f(\xi) = \langle f, e^{2\pi i \xi x}\rangle$ isn’t literally an instance of Riesz representation the way $\langle f, v\rangle$ is. What earns exponentials their place as the kernel here is a separate fact: they’re the joint eigenfunctions of every translation-invariant linear operator, shifting and differentiating included, which is exactly what turns a differential equation into an algebraic one and makes the transform worth computing at all, not just well-defined.
So the resemblance splits cleanly into two mechanisms doing the same job. Riesz representation, directly and then again as a lemma inside Radon-Nikodym, is why the inner product and expectation/variance have to look like $\int f \cdot (\text{kernel})$. Being the shared eigenfunctions of translation is why Fourier and Laplace look like each other, and happen to fall into that same shape too, for an unrelated reason.
Every bounded linear map between Hilbert spaces, functionals included, comes with a partner running the other way:
Definition (Adjoint) Let $T: H_1 \to H_2$ be a bounded linear map between Hilbert spaces. The adjoint of $T$ is the unique bounded linear map $T^\ast: H_2 \to H_1$ with $\langle Tx, y \rangle = \langle x, T^\ast y \rangle$ for all $x \in H_1$ and $y \in H_2$.
For matrices this is the conjugate transpose. Existence and uniqueness are given by the Riesz representation theorem. A functional $\phi_g = \langle \cdot, \overline{g} \rangle$ is a map into the one-dimensional Hilbert space $F$, and its adjoint runs backward, $\phi_g^\ast(c) = c\, \overline{g}$: analysis against a kernel one way, synthesis from that kernel the other. The same thing happens one level up. The analysis map $f \mapsto (c_n)$ that reads off Fourier coefficients has adjoint $(c_n) \mapsto \sum c_n e^{2\pi i n x/p}$, the synthesis map that reassembles $f$. And taking the adjoint of an integral operator flips its kernel to its conjugate transpose, $k(\xi, x) \mapsto \overline{k(x, \xi)}$, so the adjoint of the Fourier transform has kernel $e^{2\pi i \xi x}$, exactly the kernel of the inverse transform. That the adjoint is also the inverse is what the next section makes precise.
The Fourier Transform as a Change of Basis, II
We can finally explain the precise sense in which $\mathcal{F}$ is a change of basis. Suppose we’re working in \(L^2(\R)\), the Hilbert space of square-integrable functions.
Theorem (Plancherel) The Fourier transform is unitary on \(L^2(\R)\).
In other words, the inner product $\langle f, g \rangle$ for any two functions $f$ and $g$ in \(L^2(\R)\) stays the same after we take the Fourier transform:
| $\langle \hat f, \hat g \rangle = \int_{-\infty}^\infty | f(x) | g(x) | \, dx = \int_{-\infty}^\infty | \hat f(\xi) | \hat g(\xi) | \, d\xi = \langle f, g \rangle$ |
In a finite-dimensionsal vector space, unitary maps are matrices that represent changing to an orthonormal basis. Unitary maps preserve preserve geometric information like lengths and angles (represented by the inner product; this is the “normal” part of orthonomal) and the inverse of a unitary map is the adjoint of that map (for matrices, this means $M^{-1} = M^T$; this is the “orthogonal” part of orthonormal).
So, despite the “basis vectors” $e^{2\pi i \xi x}$ not being in $L^2(\R)$, $\mathcal{F}$ still retains all the nicest properties a change of basis could possibly have — with the exception that the basis we change to isn’t a basis at all.
Conclusion
Onions have layers! [The Fourier transform has] layers! — Shrek (paraphrased)
There are several more layers in which we can look at the Fourier transform. (If you’ve taken abstract algebra, take a look at Pontryagin duality.) However, for all the talk at the very start about applying the Fourier transform to the real world, I haven’t actually talked much about how that’s done in practice.
The main implementation — and the motivating reason for me to write this article in the first place — is known as the Fast Fourier Transform, an efficient algorithm for calculating Fourier transforms on discrete data, like bits over an internet connection or readings taken from a microphone. I’ll discuss these things and more in What is the Fast Fourier Transform?