Equivariant Ideal Downsampling for Discrete Groups

Sampling over structured domains like finite groups requires care to preserve symmetries and enable reconstruction. Classical sampling theory uses frames and anti-aliasing filters to ensure stability and avoid spectral overlap. In the group setting, these ideas are generalized using representation theory and Fourier transforms on non-abelian groups. This tutorial presents a principled framework for equivariant downsampling and anti-aliasing on finite groups, linking reconstruction guarantees with symmetry-aware operator design.

This tutorial aims to aid in explaining the theoretical framework of the work "Group Downsampling with Equivariant Anti-aliasing" with some additional background materials. To see the application of this theory in equivariant deep nets, please visit the GitHub repository: Group_Sampling.

---

1. Fourier Transform and Convolution in the Frequency Domain

The Fourier Transform enables the decomposition of a signal into sinusoidal components. For a function $f\in L^2({\mathbb{R}}^d)f\; \backslash in\; L^2(\backslash mathbb\{R\}^d)$, the Fourier transform is defined by:

$$\widehat{f}(\xi )={\int }_{{\mathbb{R}}^d}f(x)e^{-2\pi i⟨x,\xi ⟩}dx\backslash widehat\{f\}(\backslash xi)\; =\; \backslash int\_\{\backslash mathbb\{R\}^d\}\; f(x)\; e^\{-2\backslash pi\; i\; \backslash langle\; x,\; \backslash xi\; \backslash rangle\}\; \backslash ,\; dx$$

The inverse Fourier transform is:

$$f(x)={\int }_{{\mathbb{R}}^d}\widehat{f}(\xi )e^{2\pi i⟨x,\xi ⟩}d\xi f(x)\; =\; \backslash int\_\{\backslash mathbb\{R\}^d\}\; \backslash widehat\{f\}(\backslash xi)\; e^\{2\backslash pi\; i\; \backslash langle\; x,\; \backslash xi\; \backslash rangle\}\; \backslash ,\; d\backslash xi$$

These sinusoidals $e^{2\pi i⟨x,\xi ⟩}e^\{2\backslash pi\; i\; \backslash langle\; x,\; \backslash xi\; \backslash rangle\}$ forms the basis of the square-integrable function space.

Convolution Theorem

Given $f,g\in L^1({\mathbb{R}}^d)f,\; g\; \backslash in\; L^1(\backslash mathbb\{R\}^d)$, their convolution is:

$$(f\ast g)(x)={\int }_{{\mathbb{R}}^d}f(y)g(x-y)dy(f\; *\; g)(x)\; =\; \backslash int\_\{\backslash mathbb\{R\}^d\}\; f(y)g(x\; -\; y)\; \backslash ,\; dy$$

and the Fourier transform satisfies:

$$\widehat{f\ast g}(\xi )=\widehat{f}(\xi )\cdot \widehat{g}(\xi )\backslash widehat\{f\; *\; g\}(\backslash xi)\; =\; \backslash widehat\{f\}(\backslash xi)\; \backslash cdot\; \backslash widehat\{g\}(\backslash xi)$$

This equivalence connects spatial-domain filtering to pointwise multiplication in the frequency domain.

---

2. Uniform Sampling and the Aliasing Effect

To work with functions in computers we need to discretize it onto a finite set of points. Sampling refers to discretizing a continuous signal. A signal $f(x)f(x)$ is uniformly sampled as:

$$f[n]=f(nT),n\in \mathbb{Z}f[n]\; =\; f(nT),\; \backslash quad\; n\; \backslash in\; \backslash mathbb\{Z\}$$

where $TT$ is the sampling interval.

Aliasing

During sampling, we only keep a finite set of points from $f(x)f(x)$ and discard the rest. Discarding this information about the original function comes with many artifacts. Aliasing in one of them.

Aliasing is the distortion resulting from overlapping frequency content due to undersampling. When a continuous signal is sampled, its spectrum is periodically repeated.

Let ${\mathcal{S}}_{T}f(x)={\sum }_{n\in \mathbb{Z}}f(nT)\delta (x-nT)\backslash mathcal\{S\}\_T\; f(x)\; =\; \backslash sum\_\{n\; \backslash in\; \backslash mathbb\{Z\}\}\; f(nT)\; \backslash delta(x\; -\; nT)$, then

$$\mathcal{F}[{\mathcal{S}}_{T}f](\xi )=\frac{1}{T}\sum _{k\in \mathbb{Z}}\widehat{f}(\xi -\frac{k}{T})\backslash mathcal\{F\}[\backslash mathcal\{S\}\_T\; f](\backslash xi)\; =\; \backslash frac\{1\}\{T\}\; \backslash sum\_\{k\; \backslash in\; \backslash mathbb\{Z\}\}\; \backslash widehat\{f\}\backslash left(\backslash xi\; -\; \backslash frac\{k\}\{T\}\backslash right)$$

If the original spectrum $\widehat{f}\backslash widehat\{f\}$ is not bandlimited, these copies overlap, causing aliasing.

Due to aliasing, when upsampled, i.e., when we try to reconstruct the original function $f(x)f(x)$ form the finite samples $f[n]f[n]$, we see unexpected patterns. That means our original signal is now completely lost due to aliasing and there now no way to get it back.

Nyquist-Shannon Sampling Theorem

To avoid aliasing, the signal must be bandlimited:

If $\widehat{f}(\xi )=0\backslash widehat\{f\}(\backslash xi)\; =\; 0$ for all $\mathrm{\mid }\xi \mathrm{\mid }\ge \frac{1}{2T}|\backslash xi|\; \backslash geq\; \backslash frac\{1\}\{2T\}$, then $ff$ can be perfectly reconstructed from its samples $f(nT)f(nT)$.

---

3. Anti-Aliasing: Motivation and Construction

To suppress aliasing, one applies a low-pass filter before sampling:

$$f_{\text{smooth}}=f\ast hf\_\{\backslash text\{smooth\}\}\; =\; f\; *\; h$$

where $hh$ is a smoothing kernel (e.g., Gaussian). In the Fourier domain:

$$\widehat{f_{\text{smooth}}}(\xi )=\widehat{f}(\xi )\cdot \widehat{h}(\xi )\backslash widehat\{f\_\{\backslash text\{smooth\}\}\}(\backslash xi)\; =\; \backslash widehat\{f\}(\backslash xi)\; \backslash cdot\; \backslash widehat\{h\}(\backslash xi)$$

By choosing $\widehat{h}(\xi )\approx 0\backslash widehat\{h\}(\backslash xi)\; \backslash approx\; 0$ for $\mathrm{\mid }\xi \mathrm{\mid }>\frac{1}{2T}|\backslash xi|\; >\; \backslash frac\{1\}\{2T\}$, high frequencies are attenuated.

Properties of Good Anti-Aliasing Filters

• Rapid frequency decay: Gaussian filters are common.
• Isotropy: Ensures uniform smoothing in all directions.
• Preservation of signal mean: $\int h(x)dx=1\backslash int\; h(x)\backslash ,dx\; =\; 1$

Informally, this means even after sampling we can preserve important characteristics of the original function $f(x)f(x)$ if we follow a proper anti-aliasing procedure.

In signal processing literature sampling with appropriate alti-alasing is known as Downsampling.

---

4. Perfect Reconstruction

The question arises: how can we reconstruct the continuous signal from its samples?

Ideal Case: Shannon’s Reconstruction Formula

If $ff$ is bandlimited to $[-\frac{1}{2T},\frac{1}{2T}][-\backslash frac\{1\}\{2T\},\; \backslash frac\{1\}\{2T\}]$, then:

$$f(x)=\sum _{n\in \mathbb{Z}}f(nT)\cdot \text{sinc}\left(\frac{x-nT}{T}\right)f(x)\; =\; \backslash sum\_\{n\; \backslash in\; \backslash mathbb\{Z\}\}\; f(nT)\; \backslash cdot\; \backslash text\{sinc\}\backslash left(\backslash frac\{x\; -\; nT\}\{T\}\backslash right)$$

with $\text{sinc}(x)=\frac{\sin (\pi x)}{\pi x}\backslash text\{sinc\}(x)\; =\; \backslash frac\{\backslash sin(\backslash pi\; x)\}\{\backslash pi\; x\}$. This formula is known as sinc interpolation.

Frame-Based Sampling and Anti-Aliasing in Hilbert Spaces

Let $\mathcal{H}\backslash mathcal\{H\}$ be a Hilbert space (e.g., $L^2({\mathbb{R}}^d)L^2(\backslash mathbb\{R\}^d)$, or functions on a manifold or graph). We consider a principled approach to sampling and reconstruction using frame theory, where anti-aliasing is realized as a projection onto a subspace spanned by a frame, and sampling/reconstruction is formulated via analysis and synthesis operators.

---

1. Frame for a Subspace ${\mathcal{H}}^{†}\subset \mathcal{H}\backslash mathcal\{H\}^\backslash dagger\; \backslash subset\; \backslash mathcal\{H\}$

Let ${\mathcal{H}}^{†}\subset \mathcal{H}\backslash mathcal\{H\}^\backslash dagger\; \backslash subset\; \backslash mathcal\{H\}$ be a finite-dimensional subspace (e.g., the space of bandlimited functions). A frame $\{{\varphi }_i{\}}_{i=1}^N\subset {\mathcal{H}}^{†}\backslash \{\; \backslash phi\_i\; \backslash \}\_\{i=1\}^N\; \backslash subset\; \backslash mathcal\{H\}^\backslash dagger$ satisfies the frame condition:

$$A\mathrm{\parallel }f{\mathrm{\parallel }}^2\le \sum _{i=1}^N\mathrm{\mid }⟨f,{\varphi }_i⟩{\mathrm{\mid }}^2\le B\mathrm{\parallel }f{\mathrm{\parallel }}^2,\mathrm{\forall }f\in {\mathcal{H}}^{†}A\; \backslash |f\backslash |^2\; \backslash leq\; \backslash sum\_\{i=1\}^N\; |\backslash langle\; f,\; \backslash phi\_i\; \backslash rangle|^2\; \backslash leq\; B\; \backslash |f\backslash |^2,\; \backslash quad\; \backslash forall\; f\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$$

for constants . The frame allows stable representation of any $f\in {\mathcal{H}}^{†}f\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$ via its inner products with the frame elements ${\varphi }_i\backslash phi\_i$.

---

2. Anti-Aliasing as Orthogonal Projection

Suppose the original signal $f\in \mathcal{H}f\; \backslash in\; \backslash mathcal\{H\}$ may contain components outside the subspace ${\mathcal{H}}^{†}\backslash mathcal\{H\}^\backslash dagger$. To prevent aliasing, we apply an anti-aliasing filter that projects $ff$ orthogonally onto the subspace:

$$f^{†}:=P_{{\mathcal{H}}^{†}}f=\sum _{j=1}^d⟨f,{\psi }_j⟩{\psi }_{j}f^\backslash dagger\; :=\; P\_\{\backslash mathcal\{H\}^\backslash dagger\}\; f\; =\; \backslash sum\_\{j=1\}^d\; \backslash langle\; f,\; \backslash psi\_j\; \backslash rangle\; \backslash psi\_j$$

where $\{{\psi }_j\}\backslash \{\; \backslash psi\_j\; \backslash \}$ is an orthonormal basis for ${\mathcal{H}}^{†}\backslash mathcal\{H\}^\backslash dagger$. This removes components orthogonal to the frame span before sampling.

---

3. Analysis Operator as Generalized Sampling

The analysis operator $T:{\mathcal{H}}^{†}\to {\mathbb{R}}^{N}T:\; \backslash mathcal\{H\}^\backslash dagger\; \backslash to\; \backslash mathbb\{R\}^N$ maps a function to its frame coefficients:

$$Tf={(⟨f,{\varphi }_1⟩,\dots ,⟨f,{\varphi }_N⟩)}^{\mathrm{\top }}T\; f\; =\; \backslash left(\; \backslash langle\; f,\; \backslash phi\_1\; \backslash rangle,\; \backslash dots,\; \backslash langle\; f,\; \backslash phi\_N\; \backslash rangle\; \backslash right)^\backslash top$$

This is not the pointwise sampling commonly used in signal processing: unless the frame elements are delta functions (Dirac evaluations), the operator measures inner products, not values. These frames are sometimes also called point spread function.

Hence, the correct sampling pipeline for a general signal ( f \in \mathcal{H} ) is:

$$f\stackrel{\text{anti-aliasing}}{\to }{f}^{†}=P_{{\mathcal{H}}^{†}}f\stackrel{\text{analysis}}{\to }T{f}^{†}\in {\mathbb{R}}^{N}f\; \backslash xrightarrow\{\backslash text\{anti-aliasing\}\}\; f^\backslash dagger\; =\; P\_\{\backslash mathcal\{H\}^\backslash dagger\}\; f\; \backslash xrightarrow\{\backslash text\{analysis\}\}\; T\; f^\backslash dagger\; \backslash in\; \backslash mathbb\{R\}^N$$

---

4. Synthesis Operator and Reconstruction (Concrete Formulation)

Assume we have computed the frame coefficients of a projected function $f^{†}\in {\mathcal{H}}^{†}f^\backslash dagger\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$ using the analysis operator:

$$y_i:=⟨f^{†},{\varphi }_i⟩,\text{for }i=1,\dots ,Ny\_i\; :=\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle,\; \backslash quad\; \backslash text\{for\; \}\; i\; =\; 1,\; \backslash dots,\; N$$

Collect these into a vector $y=(y_1,y_2,\dots ,y_N{)}^{\mathrm{\top }}\in {\mathbb{R}}^{N}y\; =\; (y\_1,\; y\_2,\; \backslash dots,\; y\_N)^\backslash top\; \backslash in\; \backslash mathbb\{R\}^N$.

---

4.1 Definition of the Synthesis Operator

The synthesis operator $T^{\ast }:{\mathbb{R}}^N\to {\mathcal{H}}^{†}T^*:\; \backslash mathbb\{R\}^N\; \backslash to\; \backslash mathcal\{H\}^\backslash dagger$ reconstructs a function by combining the frame elements with the given coefficients:

$$T^{\ast }y:=\sum _{i=1}^N{y}_i{\varphi }_{i}T^*\; y\; :=\; \backslash sum\_\{i=1\}^N\; y\_i\; \backslash phi\_i$$

Thus, we reconstruct an approximation (or the exact function if everything is ideal) as:

$${\widehat{f}}^{†}:=T^{\ast }y=\sum _{i=1}^N⟨f^{†},{\varphi }_i⟩{\varphi }_i\backslash hat\{f\}^\backslash dagger\; :=\; T^*\; y\; =\; \backslash sum\_\{i=1\}^N\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle\; \backslash phi\_i$$

However, unless the frame is tight, this reconstruction is not exact. We need to correct it using the frame operator.

---

4.2 Frame Operator and Exact Reconstruction

Define the frame operator $S:{\mathcal{H}}^{†}\to {\mathcal{H}}^{†}S:\; \backslash mathcal\{H\}^\backslash dagger\; \backslash to\; \backslash mathcal\{H\}^\backslash dagger$ as the composition of analysis and synthesis:

$$S:=T^{\ast }TS\; :=\; T^*\; T$$

Then for any $f^{†}\in {\mathcal{H}}^{†}f^\backslash dagger\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$:

$$S{f}^{†}=T^{\ast }T{f}^{†}=\sum _{i=1}^N⟨f^{†},{\varphi }_i⟩{\varphi }_{i}S\; f^\backslash dagger\; =\; T^*\; T\; f^\backslash dagger\; =\; \backslash sum\_\{i=1\}^N\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle\; \backslash phi\_i$$

This is a positive-definite, self-adjoint operator. Therefore, it is invertible, and we can recover $f^{†}f^\backslash dagger$ from its frame coefficients by:

$$f^{†}=S^{-1}{T}^{\ast }T{f}^{†}=S^{-1}{\widehat{f}}^{†}f^\backslash dagger\; =\; S^\{-1\}\; T^*\; T\; f^\backslash dagger\; =\; S^\{-1\}\; \backslash hat\{f\}^\backslash dagger$$

---

4.3 Dual Frame and Reconstruction Formula

Define the canonical dual frame $\{{\tilde{\varphi }}_i{\}}_{i=1}^N\subset {\mathcal{H}}^{†}\backslash \{\; \backslash tilde\{\backslash phi\}\_i\; \backslash \}\_\{i=1\}^N\; \backslash subset\; \backslash mathcal\{H\}^\backslash dagger$ corresponding to $T^{\ast }T^*$ as:

$${\tilde{\varphi }}_i:=S^{-1}{\varphi }_i\backslash tilde\{\backslash phi\}\_i\; :=\; S^\{-1\}\; \backslash phi\_i$$

Then we can write the exact reconstruction formula as:

$$f^{†}=\sum _{i=1}^N⟨f^{†},{\varphi }_i⟩{\tilde{\varphi }}_{i}f^\backslash dagger\; =\; \backslash sum\_\{i=1\}^N\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle\; \backslash tilde\{\backslash phi\}\_i$$

This formula always holds, even for redundant and non-tight frames.

---

4.4 Special Case: Tight Frames

If the frame is tight, i.e., there exists a constant $A>0A\; >\; 0$ such that:

$$\sum _{i=1}^N\mathrm{\mid }⟨f,{\varphi }_i⟩{\mathrm{\mid }}^2=A\mathrm{\parallel }f{\mathrm{\parallel }}^2,\mathrm{\forall }f\in {\mathcal{H}}^{†}\backslash sum\_\{i=1\}^N\; |\backslash langle\; f,\; \backslash phi\_i\; \backslash rangle|^2\; =\; A\; \backslash |f\backslash |^2,\; \backslash quad\; \backslash forall\; f\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$$

then $S=A\cdot \mathrm{I}\mathrm{d}S\; =\; A\; \backslash cdot\; \backslash mathrm\{Id\}$, and the reconstruction simplifies to:

$$f^{†}=\frac{1}{A}{T}^{\ast }T{f}^{†}=\frac{1}{A}\sum _{i=1}^N⟨f^{†},{\varphi }_i⟩{\varphi }_{i}f^\backslash dagger\; =\; \backslash frac\{1\}\{A\}\; T^*\; T\; f^\backslash dagger\; =\; \backslash frac\{1\}\{A\}\; \backslash sum\_\{i=1\}^N\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle\; \backslash phi\_i$$

Tight frames are especially convenient in applications like wavelets, STFTs, and some spectral basis such as irreps for discrete groups.

---

✅ Summary

• The anti-aliasing operator: Project from space $\mathcal{H}\backslash mathcal\{H\}$ to ${\mathcal{H}}^{†}\backslash mathcal\{H^\backslash dagger\}$
• The analysis operator: extracts coefficients: $y_i=⟨f^{†},{\varphi }_i⟩y\_i\; =\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle$
• The synthesis operator: reconstructs: $T^{\ast }y={\sum }_i{y}_i{\varphi }_{i}T^*\; y\; =\; \backslash sum\_i\; y\_i\; \backslash phi\_i$
• The frame operator ensures stability and allows inversion
• The dual frame yields an exact reconstruction even when the frame is not tight

---

Representations and Fourier Analysis on Finite Discrete Groups

This section provides a foundation for harmonic analysis on finite non-abelian structures—essential in modern machine learning (e.g., equivariant networks), signal processing, and physics.

---

1. Group and Subgroup

A group $GG$ is a set with a binary operation $\cdot \backslash cdot$ satisfying:

• Closure: $g_1,g_2\in G\Rightarrow g_1\cdot g_2\in Gg\_1,\; g\_2\; \backslash in\; G\; \backslash Rightarrow\; g\_1\; \backslash cdot\; g\_2\; \backslash in\; G$
• Associativity: $(g_1\cdot g_2)\cdot g_3=g_1\cdot (g_2\cdot g_3)(g\_1\; \backslash cdot\; g\_2)\; \backslash cdot\; g\_3\; =\; g\_1\; \backslash cdot\; (g\_2\; \backslash cdot\; g\_3)$
• Identity: There exists $e\in Ge\; \backslash in\; G$ such that $e\cdot g=g\cdot e=ge\; \backslash cdot\; g\; =\; g\backslash cdot\; e\; =\; g$
• Inverses: For each $g\in Gg\; \backslash in\; G$, there exists $g^{-1}\in Gg^\{-1\}\; \backslash in\; G$ with $g\cdot g^{-1}=eg\; \backslash cdot\; g^\{-1\}\; =\; e$

A subgroup $H\le GH\; \backslash leq\; G$ is a subset that is itself a group under the same operation.

---

2. Representations and Group Actions

2.1 Group Representation

A (finite-dimensional, complex) representation of a finite group $GG$ is a homomorphism:

$$\rho :G\to \mathrm{G}\mathrm{L}(V)\backslash rho:\; G\; \backslash to\; \backslash mathrm\{GL\}(V)$$

with $VV$ a finite-dimensional complex vector space, and $\mathrm{G}\mathrm{L}(V)\backslash mathrm\{GL\}(V)$ the group of invertible linear operators on $VV$. In a fixed basis, this gives a matrix representation:

$$\rho (g)\in {\mathbb{C}}^{d_{\rho }\times d_{\rho }},\text{where }{d}_{\rho }=\dim V\backslash rho(g)\; \backslash in\; \backslash mathbb\{C\}^\{d\_\backslash rho\; \backslash times\; d\_\backslash rho\},\; \backslash quad\; \backslash text\{where\; \}\; d\_\backslash rho\; =\; \backslash dim\; V$$

We require:

$$\rho (gh)=\rho (g)\rho (h),\rho (e)=I\backslash rho(g\; h)\; =\; \backslash rho(g)\; \backslash rho(h),\; \backslash quad\; \backslash rho(e)\; =\; I$$

2.2 Group Action on a Set

A group action on a set $XX$ is a map:

$$G\times X\to X,(g,x)\mapsto g\cdot xG\; \backslash times\; X\; \backslash to\; X,\; \backslash quad\; (g,\; x)\; \backslash mapsto\; g\; \backslash cdot\; x$$

satisfying:

• $e\cdot x=xe\; \backslash cdot\; x\; =\; x$
• $g\cdot (h\cdot x)=(gh)\cdot xg\; \backslash cdot\; (h\; \backslash cdot\; x)\; =\; (g\; h)\; \backslash cdot\; x$

This can be viewed as a permutation representation when $XX$ is a finite set.

---

3. Irreducible Representations (Irreps)

A representation $\rho :G\to \mathrm{G}\mathrm{L}(V)\backslash rho:\; G\; \backslash to\; \backslash mathrm\{GL\}(V)$ is irreducible if it has no proper, nonzero, $GG$-invariant subspace. That is, no $W\subset VW\; \backslash subset\; V$ with such that $\rho (g)(W)\subseteq W\backslash rho(g)(W)\; \backslash subseteq\; W$ for all $g\in Gg\; \backslash in\; G$.

We denote the set of all inequivalent irreducible representations of $GG$ by:

$$\widehat{G}=\{{\rho }^{(1)},\dots ,{\rho }^{(n)}\}\backslash widehat\{G\}\; =\; \backslash \{\; \backslash rho^\{(1)\},\; \backslash dots,\; \backslash rho^\{(n)\}\; \backslash \}$$

Important facts:

• The number of irreps equals the number of conjugacy classes in $GG$.
• Every finite-dimensional unitary representation of $GG$ decomposes as a direct sum of irreps.
• The dimensions satisfy the sum-of-squares identity:

$$\sum _{\rho \in \widehat{G}}{d}_{\rho }^2=\mathrm{\mid }G\mathrm{\mid }\backslash sum\_\{\backslash rho\; \backslash in\; \backslash widehat\{G\}\}\; d\_\backslash rho^2\; =\; |G|$$

---

4. Fourier Transform on Finite Groups

Let $f:G\to \mathbb{C}f:\; G\; \backslash to\; \backslash mathbb\{C\}$ be a function on the group. The Fourier transform of $ff$ is a collection of matrices indexed by irreps:

$$\widehat{f}(\rho ):=\sum _{g\in G}f(g)\rho (g{)}^{\ast },\text{for each }\rho \in \widehat{G}\backslash widehat\{f\}(\backslash rho)\; :=\; \backslash sum\_\{g\; \backslash in\; G\}\; f(g)\; \backslash rho(g)^*,\; \backslash quad\; \backslash text\{for\; each\; \}\; \backslash rho\; \backslash in\; \backslash widehat\{G\}$$

Here:

• $\rho (g{)}^{\ast }\backslash rho(g)^*$ is the conjugate transpose of $\rho (g)\backslash rho(g)$,
• $\widehat{f}(\rho )\in {\mathbb{C}}^{d_{\rho }\times d_{\rho }}\backslash widehat\{f\}(\backslash rho)\; \backslash in\; \backslash mathbb\{C\}^\{d\_\backslash rho\; \backslash times\; d\_\backslash rho\}$,
• The total number of matrix blocks equals the number of irreps of $GG$.

---

4.1 Inverse Fourier Transform

The function $ff$ can be reconstructed via:

$$f(g)=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}\sum _{\rho \in \widehat{G}}{d}_{\rho }\cdot \mathrm{T}\mathrm{r}(\widehat{f}(\rho )\cdot \rho (g))f(g)\; =\; \backslash frac\{1\}\{|G|\}\; \backslash sum\_\{\backslash rho\; \backslash in\; \backslash widehat\{G\}\}\; d\_\backslash rho\; \backslash cdot\; \backslash mathrm\{Tr\}\; \backslash left(\; \backslash widehat\{f\}(\backslash rho)\; \backslash cdot\; \backslash rho(g)\; \backslash right)$$

This generalizes the classical Fourier inversion formula from abelian groups.

---

4.2 Plancherel Identity

The Fourier transform preserves inner products:

$$⟨f_1,f_2⟩=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}\sum _{g\in G}{f}_1(g)\overline{f_2(g)}=\sum _{\rho \in \widehat{G}}\frac{1}{d_{\rho }}\cdot \mathrm{T}\mathrm{r}(\widehat{f_1}(\rho {)}^{†}\widehat{f_2}(\rho ))\backslash langle\; f\_1,\; f\_2\; \backslash rangle\; =\; \backslash frac\{1\}\{|G|\}\; \backslash sum\_\{g\; \backslash in\; G\}\; f\_1(g)\; \backslash overline\{f\_2(g)\}\; =\; \backslash sum\_\{\backslash rho\; \backslash in\; \backslash widehat\{G\}\}\; \backslash frac\{1\}\{d\_\backslash rho\}\; \backslash cdot\; \backslash mathrm\{Tr\}\; \backslash left(\; \backslash widehat\{f\_1\}(\backslash rho)^\backslash dagger\; \backslash widehat\{f\_2\}(\backslash rho)\; \backslash right)$$

---

5. Group Action on Fourier Coefficients

Let $GG$ act on functions via left translation:

$$(L_{h}f)(g)=f(h^{-1}g)(L\_h\; f)(g)\; =\; f(h^\{-1\}\; g)$$

Then the Fourier coefficients transform via:

$$\widehat{L_{h}f}(\rho )=\rho (h)\cdot \widehat{f}(\rho )\backslash widehat\{L\_h\; f\}(\backslash rho)\; =\; \backslash rho(h)\; \backslash cdot\; \backslash widehat\{f\}(\backslash rho)$$

Similarly, right translation:

$$(R_{h}f)(g)=f(gh)(R\_h\; f)(g)\; =\; f(g\; h)$$

acts by:

$$\widehat{R_{h}f}(\rho )=\widehat{f}(\rho )\cdot \rho (h{)}^{\ast }\backslash widehat\{R\_h\; f\}(\backslash rho)\; =\; \backslash widehat\{f\}(\backslash rho)\; \backslash cdot\; \backslash rho(h)^*$$

Thus, group actions induce matrix conjugation on the Fourier side, making it particularly useful for designing equivariant operations.

---

Sampling Theory on Finite Groups: A Generalization from Frame Theory

In this section, we extend this theory to signals defined on finite groups, where both the signal domain and its structure are algebraic.

Unlike the general sampling framework—where sampling is defined as the analysis operator associated with a chosen frame—in the case of subsampling from a subgroup $G^{\downarrow }\subset GG^\backslash downarrow\; \backslash subset\; G$, the sampling process is determined by a fixed sampling matrix $\mathcal{S}\backslash mathcal\{S\}$, which selects function values restricted to the subgroup.

In this setting, an additional requirement arises: each operator in the sampling pipeline (sampling, interpolation, and anti-aliasing) must be equivariant under the group action. That is, the operations must respect the symmetry structure of the group $GG$.

To ensure this, we adopt a more abstract and general approach: we define sampling, interpolation, and anti-aliasing as linear operators, each subject to algebraic and spectral constraints—such as equivariance and perfect reconstruction. This operator-theoretic formulation allows us to systematically design the sampling pipeline while preserving group symmetry.

---

1. Signals on Finite Groups and Fourier Transform

Let $GG$ be a finite group with $\mathrm{\mid }G\mathrm{\mid }=N|G|\; =\; N$. The space of real-valued functions on $GG$ is:

$$X_G:=\{x:G\to \mathbb{R}\}\cong {\mathbb{R}}^{N}X\_G\; :=\; \backslash \{\; x\; :\; G\; \backslash to\; \backslash mathbb\{R\}\; \backslash \}\; \backslash cong\; \backslash mathbb\{R\}^N$$

Using a fixed enumeration $\{g_1,\dots ,g_N\}\backslash \{g\_1,\; \backslash dots,\; g\_N\backslash \}$ of group elements, we can identify any $x\in X_{G}x\; \backslash in\; X\_G$ with a vector $x\in {\mathbb{R}}^{N}x\; \backslash in\; \backslash mathbb\{R\}^N$ via:

$$x[i]:=x[g_i]x[i]\; :=\; x[g\_i]$$

The Fourier transform of $xx$ over $GG$ is a matrix transform:

$$\widehat{x}:=F_{G}x\backslash hat\{x\}\; :=\; F\_G\; x$$

where $F_{G}F\_G$ is the Fourier basis formed from irreducible representations of $GG$, and $\widehat{x}\in {\mathbb{C}}^N\backslash hat\{x\}\; \backslash in\; \backslash mathbb\{C\}^N$ is the collection of Fourier coefficients. The inverse transform is:

$$x=F_G^{-1}\widehat{x}x\; =\; F\_G^\{-1\}\; \backslash hat\{x\}$$

The matrix $F_{G}F\_G$ is unitary and can be interpreted as a change of basis into the irreducible harmonic components of $GG$.

---

2. Matrix Form of Sampling and Interpolation

Let $S\in {\mathbb{R}}^{M\times N}S\; \backslash in\; \backslash mathbb\{R\}^\{M\; \backslash times\; N\}$ be a sampling matrix with , selecting a subset of the coordinates (or evaluating at a subgroup $G^{\downarrow }\subset GG^\backslash downarrow\; \backslash subset\; G$). Let $I\in {\mathbb{R}}^{N\times M}I\; \backslash in\; \backslash mathbb\{R\}^\{N\; \backslash times\; M\}$ be the interpolation matrix.

Then, the standard multi-rate pipeline is written as:

$$\text{Sampling:}{x}^{\downarrow }=Sx\backslash text\{Sampling:\}\; \backslash quad\; x^\backslash downarrow\; =\; Sx$$ $$\text{Interpolation:}{x}^{\uparrow }=I{x}^{\downarrow }=ISx\backslash text\{Interpolation:\}\; \backslash quad\; x^\backslash uparrow\; =\; I\; x^\backslash downarrow\; =\; I\; S\; x$$

Perfect reconstruction requires:

$$x=ISxx\; =\; I\; S\; x$$

which is generally not satisfied unless the signal $xx$ satisfies certain spectral conditions. This motivates the definition of bandlimitedness over subgroups.

---

3. Subgroup Sampling Theorem on Finite Groups

We seek an interpolation matrix $II$ such that:

$$x=ISxx\; =\; I\; S\; x$$

holds for signals that are bandlimited to a subspace specified by an operator $M\in {\mathbb{C}}^{N\times M}M\; \backslash in\; \backslash mathbb\{C\}^\{N\; \backslash times\; M\}$, which relates the subgroup Fourier coefficients ${\widehat{x}}^{\downarrow }\in {\mathbb{C}}^M\backslash hat\{x\}^\backslash downarrow\; \backslash in\; \backslash mathbb\{C\}^M$ to the full coefficients $\widehat{x}\in {\mathbb{C}}^N\backslash hat\{x\}\; \backslash in\; \backslash mathbb\{C\}^N$:

$$\widehat{x}=M{\widehat{x}}^{\downarrow }\backslash hat\{x\}\; =\; M\; \backslash hat\{x\}^\backslash downarrow$$

This implies:

$$x=F_G^{-1}\widehat{x}=F_G^{-1}M{\widehat{x}}^{\downarrow }x\; =\; F\_G^\{-1\}\; \backslash hat\{x\}\; =\; F\_G^\{-1\}\; M\; \backslash hat\{x\}^\backslash downarrow$$

and since ${\widehat{x}}^{\downarrow }=F_{G^{\downarrow }}{x}^{\downarrow }=F_{G^{\downarrow }}Sx\backslash hat\{x\}^\backslash downarrow\; =\; F\_\{G^\backslash downarrow\}\; x^\backslash downarrow\; =\; F\_\{G^\backslash downarrow\}\; S\; x$, we obtain:

$$x=F_G^{-1}M{F}_{G^{\downarrow }}Sx=B{F}_{G^{\downarrow }}Sx=ISxx\; =\; F\_G^\{-1\}\; M\; F\_\{G^\backslash downarrow\}\; S\; x\; =\; B\; F\_\{G^\backslash downarrow\}\; S\; x\; =\; I\; S\; x$$

Thus, perfect reconstruction is achieved if the interpolation matrix is chosen as:

$$I:=B{F}_{G^{\downarrow }},\text{where }B:=F_G^{-1}MI\; :=\; B\; F\_\{G^\backslash downarrow\},\; \backslash quad\; \backslash text\{where\; \}\; B\; :=\; F\_G^\{-1\}\; M$$

---

4. Subgroup Bandlimitedness Condition

Let:

$$\bar{M}:=M(M^{†}M{)}^{-1}{M}^{†}\backslash bar\{M\}\; :=\; M(M^\backslash dagger\; M)^\{-1\}\; M^\backslash dagger$$

be the orthogonal projector onto the column space of $MM$. Then, if $\widehat{x}\in \text{Im}(\bar{M})\backslash hat\{x\}\; \backslash in\; \backslash text\{Im\}(\backslash bar\{M\})$, i.e., $\widehat{x}=\bar{M}\widehat{x}\backslash hat\{x\}\; =\; \backslash bar\{M\}\; \backslash hat\{x\}$, the signal $xx$ lies in the bandlimited subspace defined by $MM$, and:

$$x=B{\widehat{x}}^{\downarrow }\in \text{Span}(B)x\; =\; B\; \backslash hat\{x\}^\backslash downarrow\; \backslash in\; \backslash text\{Span\}(B)$$

Thus, the signal can be reconstructed from its sampled values via:

$$x=I{x}^{\downarrow }=B{F}_{G^{\downarrow }}Sxx\; =\; I\; x^\backslash downarrow\; =\; B\; F\_\{G^\backslash downarrow\}\; S\; x$$

---

5. Anti-Aliasing Operator and Optimization of $MM$

Let $P_M=B(B^{†}B{)}^{-1}{B}^{†}P\_M\; =\; B\; (B^\backslash dagger\; B)^\{-1\}\; B^\backslash dagger$ be the projection operator onto the space $\text{Span}(B)\backslash text\{Span\}(B)$. Then, this operator can be seen as the ideal anti-aliasing filter: projecting any signal onto the subspace where perfect reconstruction holds.

We define the anti-aliasing operator in Fourier space as:

$${\widehat{P}}_M:=F_G{P}_M{F}_G^{-1}\backslash hat\{P\}\_M\; :=\; F\_G\; P\_M\; F\_G^\{-1\}$$

Our goal is to design $MM$ such that:

1. $P_{M}P\_M$ is equivariant under group action,
2. The selected subspace is smooth (low variation),
3. Perfect reconstruction holds: $F_{G^{\downarrow }}^{-1}=S{F}_G^{-1}MF^\{-1\}\_\{G^\backslash downarrow\}\; =\; S\; F\_G^\{-1\}\; M$

---

5.1 Optimization Objective for Designing $MM$

We formulate the learning of $M\in {\mathbb{C}}^{N\times M}M\; \backslash in\; \backslash mathbb\{C\}^\{N\; \backslash times\; M\}$ via the constrained optimization:

$$M^{\ast }=\arg \underset{M}{\min }{\parallel \mathrm{v}\mathrm{e}\mathrm{c}({\widehat{P}}_M)-\bar{T}\mathrm{v}\mathrm{e}\mathrm{c}({\widehat{P}}_M)\parallel }_2^2+\lambda \cdot {\mathbf{1}}^{\mathrm{\top }}\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}((F_G^{-1}{)}^{†}L{F}_G^{-1}M\mathrm{\mid }\cdot \mathrm{\mid })M^*\; =\; \backslash arg\backslash min\_M\; \backslash left\backslash |\; \backslash mathrm\{vec\}(\backslash hat\{P\}\_M)\; -\; \backslash bar\{T\}\; \backslash ,\; \backslash mathrm\{vec\}(\backslash hat\{P\}\_M)\; \backslash right\backslash |\_2^2\; +\; \backslash lambda\; \backslash cdot\; \backslash mathbf\{1\}^\backslash top\; \backslash mathrm\{Diag\}\backslash left(\; (F\_G^\{-1\})^\backslash dagger\; L\; F\_G^\{-1\}\; M\; |\backslash cdot|\; \backslash right)$$

subject to:

$$F_{G^{\downarrow }}^{-1}=S{F}_G^{-1}MF^\{-1\}\_\{G^\backslash downarrow\}\; =\; S\; F\_G^\{-1\}\; M$$

• $\bar{T}\backslash bar\{T\}$ is the Reynolds operator, projecting onto the space of equivariant linear maps under the group action
• $LL$ is the graph Laplacian of the Cayley graph of $GG$, measuring smoothness
• The first term enforces equivariance
• The second term penalizes non-smooth subspaces

---

5.2 Equivariance Constraint via Reynolds Operator

Equivariance of ${\widehat{P}}_M\backslash hat\{P\}\_M$ under group action is enforced by the condition:

$$\mathrm{v}\mathrm{e}\mathrm{c}({\widehat{P}}_M)=\bar{T}\mathrm{v}\mathrm{e}\mathrm{c}({\widehat{P}}_M)\backslash mathrm\{vec\}(\backslash hat\{P\}\_M)\; =\; \backslash bar\{T\}\; \backslash ,\; \backslash mathrm\{vec\}(\backslash hat\{P\}\_M)$$

where $\bar{T}\backslash bar\{T\}$ is the Reynolds operator associated with the tensor product representation:

$${\widehat{\rho }}_{X_G}\otimes {\widehat{\rho }}_{X_G},\bar{T}:=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}\sum _{g\in G}\widehat{\rho }(g)\otimes \widehat{\rho }(g^{-1}{)}^{\mathrm{\top }}\backslash hat\{\backslash rho\}\_\{X\_G\}\; \backslash otimes\; \backslash hat\{\backslash rho\}\_\{X\_G\},\; \backslash quad\; \backslash bar\{T\}\; :=\; \backslash frac\{1\}\{|G|\}\; \backslash sum\_\{g\; \backslash in\; G\}\; \backslash hat\{\backslash rho\}(g)\; \backslash otimes\; \backslash hat\{\backslash rho\}(g^\{-1\})^\backslash top$$

This ensures that the anti-aliasing projection $P_{M}P\_M$ commutes with group action in the Fourier domain.

---

📘 References

1. Vetterli, M., Marziliano, P., & Blu, T. (2014). Sampling signals with finite rate of innovation. IEEE Signal Processing Magazine.

2. Chen, X., Sandryhaila, A., Moura, J. M. F., & Kovacevic, J. (2015). Signal recovery on graphs: Variation minimization. IEEE Transactions on Signal Processing.

3. Mouli, S. C., & Ribeiro, A. (2021). Equivariant subsampling for group-structured data. Advances in Neural Information Processing Systems (NeurIPS).

4. Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine.

5. Shannon, C. E. (1949). Communication in the presence of noise. Proceedings of the IRE.

6. Unser, M. (2000). Sampling—50 Years after Shannon. Proceedings of the IEEE.

7. Pesenson, I. (2008). Sampling in Paley–Wiener spaces on combinatorial graphs. Transactions of the American Mathematical Society.

8. Coifman, R. R., & Maggioni, M. (2006). Diffusion wavelets. Applied and Computational Harmonic Analysis.

9. Belkin, M., & Niyogi, P. (2002). Laplacian Eigenmaps for dimensionality reduction and data representation. Advances in Neural Information Processing Systems (NeurIPS).

10. Doy, M. N., & Vetterli, M. (1995). Frame reconstruction of the Laplacian pyramid. In Proceedings of ICASSP.

11. Rahman, Md Ashiqur, and Raymond A. Yeh. "Group Downsampling with Equivariant Anti-aliasing." ICLR 2025.