Surrounded by transforms

An integral transform (resp. discrete transform) $\mathcal{T}$ is a change of basis: it re-expresses a function (resp. sequence) $f$ on a domain $D$ in terms of a different set of basis functions. For a kernel $k(t, u)$,

The domain can be an interval, a ring of $N$ points, the positive reals under multiplication, the surface of a sphere. What every such domain carries is a symmetry, a group $G$ acting on $D$ under which $D$ looks the same from any of its points. The third column of the table below names it for each transform.

From Laplace in the 1780s to wavelets in the 1980s, the zoo is one idea repeated, and the idea comes from a first course in linear algebra.

A transform is the change of basis that makes the symmetry of its domain act diagonally. The variety of transforms is the variety of domains and their symmetries, and the thread frays in one predictable order as the symmetry becomes less commutative: abelian group, then Gelfand pair, then non-abelian group, then an equivariant map, where no diagonal is left at all.

The table is in the order of history, and its last column assigns each row to one of the four stages of the sentence. The sections after the table take the stages in order. Every other transform in the zoo is a child of one of these twelve rows and is listed, in the same columns, in a table at the end of its parent’s stage.

The transforms in chronological order

What a transform does

The idea is diagonalization. A unitary change of basis $A \mapsto U A U^{\ast}$ brings every normal operator to diagonal form; that is the spectral theorem.⁹ An integral transform is the $U$. Let $\tau_a$ be translation by $a$ on the real line, $(\tau_a f)(t) = f(t - a)$, and $\mathcal{F}$ the Fourier transform. Then

A multiplication operator rescales its input point by point, as a diagonal matrix rescales each coordinate. So $\mathcal{F}$ makes translation diagonal, and with it everything that commutes with translation, since commuting normal operators share an eigenbasis: $d/dt$ becomes multiplication by $i\xi$, and every convolution becomes multiplication by the transform of its kernel.⁹ This is what a transform is used for. A differential equation with constant coefficients becomes algebraic, and its solution comes back as a convolution of the data with a fixed kernel; the Coulomb potential and the heat kernel are the two classical cases, both found before the transform that explains them.¹⁰

What “diagonal” means. One point has to be fixed before the groups get bigger, because the matrix picture misleads in one respect. Translation on $\mathbb{R}$ has no eigenvectors in $L^2$: $e^{i\xi t}$ is bounded but not square-integrable. So there is no eigenbasis, and yet the display above is exact. What it says is that $\mathcal{F}$ carries $\tau_a$ to a multiplication operator, and that is the form the spectral theorem takes on an infinite-dimensional space: a normal operator is unitarily equivalent to multiplication by a function on some $L^2(\mu)$, a diagonal matrix being the case where $\mu$ is counting measure on $N$ points (multiplication-operator form). Throughout this post “diagonal” means this: after the transform, the operator is a multiplication. An eigenbasis exists when the spectrum is discrete, on a finite group, where the transform is an $N \times N$ unitary matrix and the first course applies verbatim, and on a compact group; on $\mathbb{R}$ the eigenfunctions $e^{i\xi t}$ exist but are not vectors of the space, and the diagonal is the multiplication.

Stage one: abelian groups

The setting. $G$ is a locally compact abelian group with Haar measure $dg$; when $G$ is finite, $dg$ is counting measure and every integral below is a sum. $L^2(G)$ is the space of square-integrable functions on $G$ with $\langle f, h \rangle = \int_G f \bar h\, dg$; for finite $G$ it is the space of all functions $G \to \mathbb{C}$. Translation by $g$ is $(\lambda(g) f)(x) = f(g^{-1} x)$, so that on $\mathbb{R}$, $\lambda(a) = \tau_a$; and convolution is $(f \ast h)(x) = \int_G f(g)\, h(g^{-1}x)\, dg$. The operators on $L^2(G)$ that commute with every translation are the convolutions $f \mapsto f \ast h$.¹¹

What breaks. Nothing yet. This is the stage the sentence describes verbatim, and the other three are measured against it.

What replaces the character. Nothing needs to; this is the stage that has them. The convolutions commute with one another, so one change of basis makes them all multiplications, and the common eigenfunctions are the characters, the continuous homomorphisms $\chi\colon G \to \mathbb{T}$: $\chi \ast h = \hat h(\chi)\, \chi$, where $\hat h(\chi)$ is the transform below.¹² The characters are bounded functions, in $L^2(G)$ only when $G$ is compact, which is the point of the paragraph on what “diagonal” means. The group decides the kernel, and the kernel column of the table is the characters written out. In symbols,

The characters form the dual group $\hat G$, and the transform is an isometry $L^2(G) \to L^2(\hat G)$, the Plancherel theorem, carrying $f \mapsto f \ast h$ to multiplication by $\hat h$: that is the diagonalization, in the sense fixed above, and the second half of the display is its formula. Further, $\hat{\hat G} = G$ (Pontryagin duality), and in the language of Banach algebras the transform is the Gelfand transform of $L^1(G)$.¹²

DFT. $G = \mathbb Z_N$, self-dual, with characters $\chi_k(j) = e^{2\pi i jk/N}$. The transform is the $N \times N$ unitary matrix $N^{-1/2}(e^{-2\pi i jk/N})_{k,j}$, and the first course applies without change.

Fourier series. $G = \mathbb{T}$, with dual $\mathbb{Z}$ and characters $e^{in\theta}$; the group is compact and the spectrum is discrete. The transform in the other direction, on $G = \mathbb{Z}$ with dual $\mathbb{T}$, is the Fourier series read backwards, $\hat f(e^{i\theta}) = \sum_n f(n) e^{-in\theta}$.³

Fourier transform. $G = \mathbb{R}$, self-dual, with characters $e^{i\omega t}$; the group is neither compact nor discrete, and neither is the spectrum: there is no eigenbasis, and the transform diagonalizes translation in the multiplication sense only.

Mellin. $G = (\mathbb{R}^+, \times)$. The substitution $t = e^{\xi}$ carries it to $(\mathbb{R}, +)$ and the kernel to $t^{s-1}\,dt = e^{s\xi}\,d\xi$, so the Mellin transform is the Fourier transform of $f(e^\xi)$ at the complex frequency $s$; the unitary characters are the $t^{i\omega}$, on the line $\Re s = 0$.⁵

Laplace. $G = \mathbb{R}$ on functions supported in $[0, \infty)$, with the character $e^{-i\omega t}$ continued to the complex frequency $s$, $\Re s > 0$. The gain is that $e^{-st}$ decays and the result is analytic in $s$; the cost is orthogonality, since the $e^{-st}$ for real $s$ are not orthogonal and there is no Plancherel formula on the real $s$-axis. The isometry holds line by line: on $\Re s = c$ the Laplace transform of $f$ is the Fourier transform of $e^{-ct} f$.¹³

Children of stage one

Changing the field: Hartley and NTT

Two of the children keep $G = \mathbb Z_N$ and change the field of scalars from $\mathbb{C}$ to a field $\mathbb{F}$. Over $\mathbb{F}$ the circulant matrices are $\mathbb{F}[x]/(x^N-1)$, the cyclic shift is the companion matrix of $x^N - 1$, and the Frobenius normal form says how far the shift can be reduced: to one block for each irreducible factor of $x^N - 1$ over $\mathbb{F}$.

The middle row is the real spectral theorem: no real basis separates a conjugate pair of eigenvalues, so the Hartley kernel $\cos\nu x + \sin\nu x$ pairs $\nu$ with $-\nu$, and no real transform does better.⁹ The last row says that a change of field costs nothing provided $\mathbb F_q^\times$, a cyclic group of order $q - 1$, contains an element of order $N$.

Stage two: Gelfand pairs

The setting. As in stage one, except that $G$ is a locally compact group, not necessarily abelian, and the domain is not $G$ but a space $X$ on which $G$ acts transitively. $K$ is the stabilizer of a chosen base point, so that $X = G/K$ is a homogeneous space: $S^2 = SO(3)/SO(2)$, and $\mathbb{R}^n = G/K$ with $G$ the Euclidean motion group and $K = SO(n)$, so that the radial functions are the $K$-invariant functions on $X$. $G$ acts on $L^2(X)$ by the formula of stage one, $(\lambda(g) f)(x) = f(g^{-1} x)$. A unitary representation $\pi$ of $G$ on a Hilbert space $V_\pi$ is irreducible when $V_\pi$ has no proper nonzero closed invariant subspace, and $d_\pi = \dim V_\pi$; a character is the case $d_\pi = 1$.

What breaks. The domain is no longer a group. The Hankel transform acts on radial functions on $\mathbb{R}^n$ and the spherical harmonic transform on $S^2$; the sphere cannot be made a group, and $SO(3)$, which acts on it, has no invariant one-dimensional space of functions but the constants.¹⁰ So there are no characters. Yet both transforms are diagonal: the Hankel transform turns the radial Laplacian into multiplication by $-\kappa^2$,⁴ and the spherical harmonics are eigenfunctions of the Laplacian on the sphere.²

What replaces the character. The operators on $L^2(X)$ commuting with every $\lambda(g)$ form an algebra, and $(G, K)$ is a Gelfand pair when that algebra is commutative; symmetric spaces are the motivating examples. When it is, three things hold at once. The commuting operators diagonalize simultaneously, as in stage one. $L^2(X)$ splits into irreducible pieces $V_\pi$, no piece repeated: a direct sum when $G$ is compact, as for $S^2$, where the spectrum is discrete, and with a continuous spectrum for $\mathbb{R}^n$, as on $\mathbb{R}$. And each $V_\pi$ contains, up to scale, one $K$-fixed unit vector $u_\pi$; read as a function on $X$ it is the spherical function of the piece, and it plays the part of the character:

The $\phi_\pi$ are the multiplicative functionals of the commutative algebra, exactly as the characters are for $L^1(G)$; and for $f \in L^2(X)$ not $K$-invariant, $\langle f, \pi(g) u_\pi\rangle$ as a function of $gK$ is a multiple of the projection of $f$ onto $V_\pi$.²¹ Stage one is the case $K = {1}$: $(G, {1})$ is a Gelfand pair if and only if $G$ is abelian, and the spherical functions are then the characters.²¹ The hypothesis was never commutativity of $G$ but commutativity of the operators commuting with $G$, equivalently no repeated piece. This is the first place the transforms need representation theory, and for one job: to say when a transform is still diagonal.

Spherical harmonic transform. $(G, K) = (SO(3), SO(2))$, $X = S^2$. The pieces $V_\ell$ are the spherical harmonics of degree $\ell$, the spherical function of $V_\ell$ is the Legendre polynomial $P_\ell(\cos\theta)$ with $\theta$ the angle from the fixed axis, and the transform of $f \in L^2(S^2)$ is its expansion in the $Y_\ell^m$; on zonal $f$ it is the integral against $P_\ell$.² For $(SO(n), SO(n-1))$ on $S^{n-1}$ the Legendre polynomials become Gegenbauer polynomials.²²

Hankel transform. $G = \mathbb{R}^n \rtimes SO(n)$, $K = SO(n)$, $X = \mathbb{R}^n$; the spectrum is continuous, so “diagonal” is again the multiplication sense. Here the commutativity is elementary: the operators commuting with the motion group are convolutions by radial kernels, and the Fourier transform makes them multiplications by radial functions.⁴ The Hankel transform of order $(n-2)/2$ is the Fourier transform on $\mathbb{R}^n$ restricted to radial functions, which is where the Bessel function in the kernel comes from. The other orders in the table come from the other pieces of $L^2(\mathbb{R}^n)$: on $f_0(\lvert x \rvert) P(x)$ with $P$ a harmonic polynomial of degree $k$, the Fourier transform is $P$ times a Hankel transform of order $k + (n-2)/2$.²

Children of stage two

Stage three: non-abelian groups

The setting. As in stage two, except that the domain is the group again, $X = G$ and $K = {1}$, with $G$ finite or a compact Lie group; $\lambda$ and $\ast$ are those of stage one, $\pi$, $V_\pi$, $d_\pi$ those of stage two, and $\chi_\pi = \mathrm{tr}\pi$ is the character of $\pi$, a function on $G$.

What breaks. $G$ is not commutative, so $(G, {1})$ is not a Gelfand pair: the convolutions $f \mapsto f \ast h$ do not commute with one another and no single eigenbasis exists.

What replaces the character. An irreducible representation $\pi$ of dimension $d_\pi$. The transform of $f$ at $\pi$ is a $d_\pi \times d_\pi$ matrix, and convolution becomes matrix multiplication, block by block:

the bar being the entrywise conjugate, so that the kernel is the $\overline{\pi_{ij}(g)}$ of the table.²³ For finite $G$ the statement that this is an isomorphism of algebras, $L^2(G) \cong \bigoplus_\pi M_{d_\pi}(\mathbb{C})$, is Wedderburn’s theorem; stage one is the case where every block is $1 \times 1$.²³ Block-diagonal is not diagonal, and the following observation is what makes the transform a diagonalization after all. Let $G \times G$ act on $L^2(G)$ by translating on both sides, $f(g) \mapsto f(g_1^{-1} g g_2)$. Under this larger action the decomposition $L^2(G) = \bigoplus_\pi V_\pi \otimes V_\pi^{\ast}$ has no repeated piece, so $(G \times G, \Delta G)$ with $\Delta G = {(g, g)}$ is a Gelfand pair, and its spherical functions are $\chi_\pi / d_\pi$; this is what “character” means for a non-abelian group.²³ So the non-abelian transform diagonalizes the two-sided action, and the $d_\pi \times d_\pi$ blocks are what the one-sided action alone can see. The history ran the same way: Frobenius invented representation theory in 1897 to answer a question of Dedekind’s about group determinants, and it took until Weyl, thirty years later, for anyone to see that he had extended Fourier analysis from commutative to non-commutative groups.⁶

Fourier transform on a finite group. $G$ finite, the integral a sum. The entries $\pi_{ij}$, over all $\pi$ and all $i, j \le d_\pi$, are an orthogonal basis of $L^2(G)$, and $\lvert G \rvert = \sum_\pi d_\pi^2$; the transform is the unitary $\lvert G \rvert \times \lvert G \rvert$ matrix that expands $f$ in this basis.²³

Peter–Weyl transform. $G$ a compact Lie group such as $SO(3)$ or $SU(2)$, the integral against Haar measure. The same statement holds with countably many $\pi$: the matrix coefficients $\pi_{ij}$ are a complete orthogonal system in $L^2(G)$, which is the Peter–Weyl theorem of 1927.⁶

Cayley graphs and shuffles

Two uses of the block form. A Cayley graph on $G$ has adjacency matrix equal to convolution by the indicator $\delta_S$ of its generating set $S$, so its eigenvalues are those of the blocks $\hat\delta_S(\pi)$, each repeated $d_\pi$ times; when $G$ is abelian, or $S$ is a union of conjugacy classes, the blocks are scalars and the eigenvalues are the character sums $\frac{1}{d_\pi}\sum_{s \in S} \chi_\pi(s)$.²⁴ And a shuffle is a probability $P$ on $S_n$, $k$ shuffles is $P^{\ast k}$, so $\widehat{P^{\ast k}} = \hat P^k$, and Plancherel bounds the total-variation distance $\lVert P^{\ast k} - U \rVert = \max_A \lvert P^{\ast k}(A) - U(A) \rvert$ from the uniform distribution $U$ by a sum over representations:

For $\mathbb Z_p$, stepping by $\pm 1$, somewhat more than $p^2$ steps are needed. For $S_n$, swapping a random pair each step, $\frac12 n\log n + cn$ shuffles bring the distance below $a e^{-2c}$, while $\frac12 n \log n - cn$ leave it above $\frac1e - o(1)$: the distance drops from a constant to nearly zero in a window of width $O(n)$ around $\frac12 n \log n$, which is the cutoff phenomenon.²⁴

Stage four: equivariant maps

The setting. As in stage two, except that the transform now goes between two different spaces on which $G$ acts. For the Radon transform they are two homogeneous spaces, $X = G/K$ as before and a second one $Y = G/H$, with $H$ the stabilizer of a base point of $Y$; $\lambda_X$ and $\lambda_Y$ are the actions of $G$ on $L^2(X)$ and $L^2(Y)$ by the formula of stage one. For the wavelet and Gabor transforms the source is $L^2(\mathbb{R})$ with $G$ acting by a unitary representation $\pi$, and the target is $L^2(G)$ with the action $\lambda$ of stage one.

What breaks. The diagonal. In the three stages so far the transform was a change of basis in which the symmetry acts by scalars, or at worst by blocks; in the three remaining rows the group is still there but the target of the map is not a sum of one-dimensional pieces, and there are no scalars to be found.

What replaces the character. Nothing does; what survives is the property that made the character work. A transform $T$ from one of the two spaces to the other is an equivariant map, one that commutes with the two actions:

Stage one is the case $X = G$, $Y = \hat G$, where $\lambda_Y(g)$ is multiplication by $\overline{\chi(g)}$, a scalar at each point of $Y$.¹² The kernel of an equivariant map is still decided by the group, as it was there: the equivariant maps $L^2(G/K) \to L^2(G/H)$ correspond to the functions $\kappa$ on $G$ with $\kappa(kgh) = \kappa(g)$ for $k \in K$, $h \in H$, and that is why these three are still called transforms.⁷

Radon transform. $X$ is the set of points of the plane and $Y$ the set of lines; the group $G$ of rigid motions acts transitively on both, with $K$ the stabilizer of a point and $H$ that of a line. The Radon transform integrates $f$ over each line, and integrating over a line commutes with moving the plane, so it is equivariant; the function $\kappa$ is the incidence relation, $1$ when the point lies on the line. The finite version, with $S_n$ acting on $j$-subsets and $k$-subsets of ${1, \dots, n}$ and $\kappa$ the containment relation, is where this description is proved and inverted.⁷

Wavelet transform. $G$ is the affine group ${t \mapsto at + b : a > 0}$, acting on $L^2(\mathbb{R})$ by $(\pi(a,b) f)(t) = a^{-1/2} f((t-b)/a)$, and the transform pairs $f$ with the translates of a chosen window $\psi$:

where $\lambda$ is translation on functions of $(a,b)$, as in stage one. So $W_\psi$ is an equivariant map from $L^2(\mathbb{R})$ into functions on $G$. What survives of the diagonal is energy: an admissibility condition on $\psi$, $C_\psi = 2\pi\int \lvert \hat\psi(\omega) \rvert^2 \lvert \omega \rvert^{-1} d\omega < \infty$, makes $C_\psi^{-1/2} W_\psi$ an isometry into $L^2$ of the half-plane with the measure $db\,da/a^2$.⁸ Compare stage two, where the transform paired $f$ with the translates $\pi(g) u_\pi$ of the one $K$-fixed vector: here $\psi$ is fixed by no stabilizer at all. Dropping that invariance costs the diagonal, since there is no commutative algebra left to diagonalize, and leaves the isometry, which never depended on characters.

Gabor transform. The same construction with a window $g$ translated in time and modulated in frequency, $g_{b,\omega}(t) = g(t-b)\, e^{i\omega t}$: the transform is $\langle f, g_{b,\omega}\rangle$, the kernel in the table is $\overline{g_{b,\omega}}$, and time shifts and modulations of $f$ shift the transform in $(b, \omega)$.²⁵

Children of stage four

The four canonical forms

Classifying the elements of a matrix group up to conjugacy is the problem of canonical forms, and the four forms of a first course are all the post has used.²⁴

Where the thread ends

Two things that carry the name “transform”, or are treated alongside them, are outside the four stages, each for a different reason.

Operators a transform diagonalizes. The Hilbert transform is convolution with $1/\pi t$ on the line, so it commutes with translation and the Fourier transform diagonalizes it, as multiplication by $-i \mathrm{sgn} \xi$.²⁶ The Stieltjes transform is the Laplace transform applied twice, $\int_0^\infty f(t)\,dt/(t+x)$; its kernel depends on $t$ and $x$ only through $t/x$, up to the factor $1/x$, so it commutes with dilations and the Mellin transform diagonalizes it, as multiplication by $\pi/\sin \pi p$.²⁷ The Weyl fractional integral is of the same kind, a Mellin multiplier.²⁷ These are not changes of basis but the kind of operator a change of basis is for, and that is why they have no row.

No basis at all. Let $A \subset \mathbb Z_N$ have density $\alpha$. The fraction of three-term arithmetic progressions $x + y = 2z$ with all three terms in $A$ is $\sum_r \hat A(r)^2 \hat A(-2r)$, which is $\alpha^3$, the random share, plus an error of at most $\alpha \max_{r \ne 0} \lvert \hat A(r) \rvert$; so either $A$ has its random share or a character correlates with it, and iterating on the progressions where that character is nearly constant is Roth’s theorem of 1953.²⁸ The Gowers norms (1998) are where this stops. On $\mathbb Z_N$ with $N$ odd the function $e^{2\pi i x^2/N}$ has every Fourier coefficient of modulus $N^{-1/2}$, as flat as Plancherel allows, yet it and three companions have four-term progression count $1$, the largest possible: the transform is blind to the quadratic phases. There are $N^2$ of them against $N$ characters, so they are no basis, and no quadratic transform or inversion formula exists. What survives is the $U^3$ norm, an average over cubes, and an inverse theorem: a function with large $U^3$ norm correlates with a phase built from a two-step nilpotent group, a Heisenberg group once more.²⁹ Nothing is being diagonalized, so the thread does not fray here; it ends.

One idea from a first course in linear algebra reaches across two and a half centuries into number theory, tomography, image compression and quantum computation. Representation theory is what one reaches for where it stops, and it works there because diagonalization was one of its tools and never the whole of it.

Sources

An AI slop. Brought to you by Anthropic Claude Opus 5.

• Lokenath Debnath and Dambaru Bhatta, Integral Transforms and Their Applications, 3rd ed., CRC Press, 2015.
• Audrey Terras, Fourier Analysis on Finite Groups and Applications, LMS Student Texts 43, Cambridge, 1999.
• Walter Rudin, Fourier Analysis on Groups, Interscience, 1962.
• Elias M. Stein and Guido Weiss, Introduction to Fourier Analysis on Euclidean Spaces, Princeton Mathematical Series 32, Princeton, 1971.
• Paul R. Halmos, Finite-Dimensional Vector Spaces, 2nd ed., Springer UTM.
• Benjamin Steinberg, Representation Theory of Finite Groups: An Introductory Approach, Springer Universitext, 2012.
• Tullio Ceccherini-Silberstein, Fabio Scarabotti and Filippo Tolli, Harmonic Analysis on Finite Groups, Cambridge, 2008 (cited as CST 2008).
• Tullio Ceccherini-Silberstein, Fabio Scarabotti and Filippo Tolli, Discrete Harmonic Analysis, Cambridge, 2018 (CST 2018).
• Persi Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes 11, 1988.
• David A. Levin and Yuval Peres, with Elizabeth L. Wilmer, Markov Chains and Mixing Times, 2nd ed., AMS, 2017 (LPW).
• Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge.
• George W. Mackey, Harmonic analysis as the exploitation of symmetry: a historical survey, Bull. AMS 3 (1980), 543–698.
• Louis Auslander and Richard Tolimieri, Is computing with the finite Fourier transform pure or applied mathematics?, Bull. AMS (N.S.) 1 (1979), no. 6, 847–897 (cited as AT).
• W. T. Gowers, Generalizations of Fourier analysis, and how to apply them, Bull. AMS (N.S.) 54 (2017), no. 1, 1–44.