The Fourier transform in $\mathbb R^n$ maps a complex-valued function $f:\mathbb R^n \rightarrow \mathbb C$ to a function of its Pontryagin dual space (which is in this case also $\mathbb R^n$), $\ \hat f:\mathbb R^n \rightarrow \mathbb C$, given by
$$ \begin{align*} \hat f&(\boldsymbol \omega) \\&\coloneqq \int_{\mathbb R^n} f(\mathbf x) e^{-i\hspace{1pt} 2\pi \langle \boldsymbol \omega, \mathbf x\rangle} d\mathbf x\\ &= \int_{\mathbb R}\cdots\int_{\mathbb R} f(\mathbf x) \left(e^{-i \hspace{1pt}2\pi \omega^1 x^1}\cdots e^{-i \hspace{1pt}2\pi \omega^n x^n}\right) dx^1 \cdots dx^n\\ &= \cdots \left(\int_{\mathbb R}\left(\int_{\mathbb R} f(\mathbf x) e^{-i\hspace{1pt}2\pi \omega^1 x^1}dx^1 \right) e^{-i\hspace{1pt}2\pi \omega^2 x^2} dx^2 \right)\cdots \end{align*} $$That is, it performs the Fourier transform (FT) along each dimension, in succession. On compact quotients of $\mathbb R^n$, like $\mathbb T^n \cong \mathbb R^n/\mathbb Z^n$ (where each $\mathbb T\cong S^1$ is the one-dimensional torus), this becomes a Fourier series.
Discretization & Computation
Since we know that the $n$-dimensional FT is really just the one-dimensional FT iterated, let’s restrict to the latter. Consider a function $f: \mathbb R \rightarrow \mathbb C$ that has been sampled on a regularly-spaced lattice in $\mathbb R$, i.e., a set of points $(x_j)_{j\in \mathbb Z}$ with $\Delta \coloneqq(x_j - x_{j-1})$ denoting the “sampling period”. For simplicity, let $x_0 = 0$ so that $x_j = j \Delta$. The Fourier transform integral can be discretized such that the resulting summation only depends on the information we have access to:
$$ \tilde f(\omega) \coloneqq \sum_{j\in \mathbb Z} f(x_j) e^{-i\hspace{1pt}2\pi \omega x_j} \Delta \approx \int_{\mathbb R} f(x) e^{-i\hspace{1pt}2\pi \omega x}dx = \hat f(\omega). $$Now,
$$ \begin{align*} \tilde f(\omega + \tfrac{1}{\Delta}) &= \sum_{j\in \mathbb Z} f(x_j) e^{-i\hspace{1pt}2\pi \left(\omega + \tfrac{1}{\Delta} \right)j\Delta} \Delta\\ &= \sum_{j\in \mathbb Z} f(x_j) e^{-i\hspace{1pt}2\pi \omega j \Delta} \Delta \\ &= \tilde f(\omega), \end{align*} $$showing that $\tilde f$ is periodic with period $\tfrac{1}{\Delta}$. The transform $f \mapsto \tilde f$ is called the Discrete-Time Fourier Transform (DTFT). The periodicity of $\tilde f$ introduces limits in the inverse transform.
If we have only a finite number of samples $(x_i)_{i=0}^{N-1}$, then we obtain the (rather confusingly named) Discrete Fourier Transform (DFT). To do this, we assume that the samples are periodic with period $N$; either this periodicity is due to the underlying periodicity of $f$, or we naively let the function be periodic outside $[0, N\Delta] \subseteq \mathbb Z$ because we do not care about the behavior of $f$ outside of this domain. In either case,
$$ \begin{align} \tilde f(\omega) &= \sum_{j\in \mathbb Z} f(x_j) e^{-i\hspace{1pt}2\pi \omega j \Delta} \Delta \\ &= \sum_{k\in \mathbb Z}\sum_{j=0}^{N-1} f(x_j) e^{-i\hspace{1pt}2\pi \omega (k N + j) \Delta} \Delta\\ &= \sum_{j=0}^{N-1} f(x_j) \left(\sum_{k\in \mathbb Z}e^{-i\hspace{1pt}2\pi \omega k N \Delta}\right) e^{-i\hspace{1pt}2\pi \omega j \Delta}\Delta \end{align} $$Using the (rather mysterious) Poisson summation formula, we get
$$ \begin{align} \tilde f(\omega) &= \sum_{j=0}^{N-1} f(x_j) \left(2\pi \sum_{k\in \mathbb Z} \delta(\omega N \Delta + k) \right) e^{-i\hspace{1pt}2\pi \omega j \Delta}\Delta \end{align} $$Thus, the DTFT of a periodic sequence is non-zero precisely when $\omega N \Delta$ is an integer, i.e., $\omega = \ell/N\Delta$ for some $\ell \in\mathbb Z$. Since
$$\tilde f\left(\frac{\ell + N}{N\Delta}\right) = \tilde f\left(\frac{\ell}{N\Delta} + \frac{1}{\Delta}\right) = \tilde f\left(\frac{\ell}{N\Delta}\right),$$it is $N$-periodic in the Fourier domain; we only need to compute $N$ coefficients to realize this transform. In summary, the DFT can be thought of as “the DTFT of a finite sequence of samples”, as computed under the assumption that the function is periodic outside the domain of the observed samples. In turn, the DTFT is simply a discretization of the FT. I present this table from Wikipedia:
| Time/Spatial Domain | Frequency Domain | Transform Name |
|---|---|---|
| Discrete / Periodic | Discrete / Periodic | Discrete Fourier Transform (DFT) |
| Continuous / Periodic | Discrete / Aperiodic | Fourier Series |
| Discrete / Aperiodic | Continuous / Periodic | Discrete-Time Fourier Transform (DTFT) |
| Continuous / Aperiodic | Continuous / Aperiodic | Fourier Transform (FT) |
Finally, the Fast Fourier Transform (FFT) is just a way to compute the DFT efficiently by exploiting the underlying redundancy of the computations. MATLAB has a function for computing the $n$-dimensional FFT, whose documentation mentions that this is mathematically just the one-dimensional FFT iterated.
The Compact, Non-Abelian Case
So we know how the FT works on locally compact (which is colloquially used to refer to noncompact) abelian groups. Now, the theory of Pontryagin duality breaks down on non-abelian groups.1 We can nonetheless ask whether a function $f:G \rightarrow \mathbb C$ may be transformed, without loss of information, into another function $\hat f: \hat G \rightarrow \mathbb C$, where $\hat G$ is some sort of a dual space. The answer is yes, but the details are intricate.
Instead of things like $e^{-i \omega x}$, one needs to introduce the so-called irreducible unitary representations (IURs) of $G$ (in the abelian case, these are called characters and constitute a group). A representation $U:G \rightarrow GL(V)$ is a group homomorphism from $G$ to the invertible linear operators on some vector space $V$. It is said to be unitary if ($V$ comes with an inner product, and) $U(g)$ is a unitary operator for all $g \in G$. We won’t worry about what irreducible means, here, but it is a crucial ingredient in this theory. Note that $U(g^{-1}) = U(g)^{-1} = U(g)^{\dagger}$. For instance, $e^{i\omega x}$ is an IUR of $\mathbb R$, whose complex conjugate is $e^{-i\omega x}$. For $SU(2)$, the IURs act on homogeneous polynomials (which can be given a vector space structure). A subset of the $SU(2)$ IURs become the IURs for $SO(3)$ (see Unitary Representations by Mitsuo Sugiora, Thm. 7.1).
The dual space $\hat G$ is the space of all (equivalence classes of) IURs of $G$ (the details are outside of our scope). Let’s say that the equivalence classes of IURs can be parameterized by some $\lambda$, so that $\big(\hspace{1pt} U^\lambda \mathrel\vert \lambda \in \hat G \big)$ represents all the distinct IURs (i.e., does not double-count any that are equivalent). The Fourier transform of $f$ (square-integrable function on $G$) is then given by2
$$\hat f(\lambda) = \int_G f(g) U^\lambda(g^{-1}) dg= \int_G f(g) \left(U^\lambda(g)\right)^{\dagger} dg,$$where $dg$ is the Haar measure on $G$ and $\hat f(\lambda)$ is an operator. If we choose a basis $(\mathbf e_i)_{i=1}^{\textrm{dim}(V^\lambda)}$ for $V^\lambda$ (i.e., the vector space that $U^\lambda$ acts on), then we can compute the $(i,j)^{th}$ component of $\hat f(\lambda)$ as
$$\hat f(\lambda)_{ij} = \int_G f(g) \left[\left(U^\lambda(g)\right)^{\dagger}\right]_{ij} dg. $$The inverse Fourier transform (which hinges on the Peter-Weyl theorem) is given by (Thm. 8.1 of Sugiura)
$$ \begin{align} f(g) &= \sum_{\lambda \in \hat G} \textrm{dim}(V^\lambda) \left(\sum_{i,j=1}^{\textrm{dim}(V^\lambda)} \hat f(\lambda) _{ji}U^\lambda(g)_{ij}\right)\\ &= \sum_{\lambda \in \hat G} \textrm{dim}(V^\lambda) \,\mathrm{Trace}\left( \hat f(\lambda)U^\lambda(g)\right). \end{align} $$In the case of $SO(3)$, the IURs $U^\lambda(g)$ are the Wigner $D$-matrices, $\lambda$ ranges over the nonnegative integers, and $\textrm{dim}(V^\lambda) = 2\lambda + 1$. As in the case of the classical Fourier transform, compactness of the original domain implies that the IUR-space (i.e., frequency domain) is discrete.
Any representation of the group yields a corresponding representation of the Lie algebra:
$$ u^\lambda(X) \coloneqq \frac{d}{dt}U^\lambda\left(\exp(tX)\right)\bigg\vert_{t=0}. $$This object gives a commutative diagram for the actions of the left-invariant vector fields (LIVFs) on $f$. If $X^L$ is the LIVF generated by $X\in \mathfrak g$, then
$$ \widehat{X^L f}(\lambda) = u^\lambda(X)\hat f(\lambda), $$$$ \widehat{X^R f}(\lambda) = \hat f(\lambda)u^\lambda(X). $$Other classical results, like the Parseval/Plancheral identity and the convolution theorem hold, but the convolution is generally non-commutative.
The Locally Compact, Non-Abelian Case
The theory gets more complicated here, and the literature sparse. For $SE(2)$, the IURs are parametrized by the positive real numbers (i.e., $\lambda >0$). As we are no longer on a compact domain, the space of (equivalence classes of) IURs is continuous.
The IURs of $SE(2)$ act on the $L^2$ space of functions on the circle; or rather, we will think of these as functions on $SO(2)$. Letting $\phi \in SO(2)$ be a point and $\zeta\in L^2(SO(2))$ a function on the circle, respectively, we define
$$ \left[U^\lambda (g) \zeta\right](\phi)\coloneqq e^{-i \lambda \hspace{1pt}(\hspace{1pt}{\mathbf t}_x\cos \phi \hspace{1pt}+\hspace{1pt} {\mathbf t}_y \sin \phi)} \zeta(\phi - \theta) $$where $g\coloneq(\theta, \mathbf t) \in SE(2)$ is the element being represented. Here, $U^\lambda(g) \zeta$ represents the action of $U^\lambda(g)$ on $\zeta$, whose result is another function on $SO(2)$. With these definitions, the Fourier transform of $SE(2)$ looks identical to the one in the compact case. To find the component-wise description of the transform, consider the basis $(e^{ik\phi})_{k\in \mathbb Z}$ for functions on the circle (with the circle identified with $\mathbb R/2\pi\mathbb Z$), and let $\left[U^\lambda(g)\right]_{mn} = \langle e^{im\phi}, U^\lambda(g)e^{in\phi}\rangle$. The $SE(2)$ Fourier transform then becomes (see Chirikjian & Kyatkin, Sec. 11.2)
$$ \begin{align} \hat f_{mn}(\lambda) = &\int_{\mathbb R^2} \int_0^{2\pi} \int_0^{2\pi} f(\theta, \mathbf t) e^{in\phi} \nonumber \\&e^{i \lambda \hspace{1pt}(\hspace{1pt}{\mathbf t}_x\cos \phi \hspace{1pt}+\hspace{1pt} {\mathbf t}_y \sin \phi)}e^{-im(\phi - \theta)} \hspace{1pt}d\phi \hspace{1pt}d\theta \hspace{1pt}d {\mathbf t}_x d{\mathbf t}_y. \end{align} $$However, the inverse Fourier transform given above doesn’t make sense since $V^\lambda$ is infinite-dimensional. Rather, we have
$$ \begin{align} f(g) &= \int_0^\infty \left(\sum_{i,j\in \mathbb Z} \hat f(\lambda) _{ji}U^\lambda(g)_{ij}\right) \lambda\, d\lambda\\ &= \int_0^\infty \mathrm{Trace}\big(\hat f(\lambda)U^\lambda(g)\big) \lambda\, d\lambda. \end{align} $$When I first saw this, I wondered if the extra $\lambda$ in “$\lambda\,d\lambda$” was a typo!
In the $SE(3)$ case, the IURs act on functions on the sphere, which can be expanded in the basis of spherical harmonics. We incur a `$\lambda^2 d\lambda$’ term in the inverse transform. Rather than repeating the details, I recommend the tutorial article GS Chirikjian, Degenerate Diffusions and Harmonic Analysis on SE(3): A Tutorial (2015) written by my postdoc advisor.