离散群的等变子采样

在有限群等结构化域上进行采样需要额外的步骤来保留对称性并实现重构。经典采样理论使用帧和抗混叠滤波器来确保稳定性和避免频谱重叠 [1,5]。在群设置中，这些思想通过表示理论和非阿贝尔群上的傅里叶变换得到推广 [12]。本教程提供了一个在有限群上进行等变降采样和抗混叠的原理性框架，将重构保证与对称感知算子设计联系起来 [11]。

本教程旨在辅助解释“带等变抗混叠的群降采样”工作的理论框架，并提供一些额外的背景材料。要查看该理论在等变深度网络中的应用，请访问 GitHub 存储库：Group_Sampling。

---

1. 傅里叶变换与频域卷积

傅里叶变换能够将信号分解为正交的正弦分量。对于函数 $f\in L^2({\mathbb{R}}^d)f\; \backslash in\; L^2(\backslash mathbb\{R\}^d)$ (即平方可积函数集)，傅里叶变换定义为

$$\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$$∫Rd​f(x)e−2πi⟨x,ξ⟩dx

逆傅里叶变换是

$$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$$

这些正弦函数 $e^{2\pi i⟨x,\xi ⟩}e^\{2\backslash pi\; i\; \backslash langle\; x,\; \backslash xi\; \backslash rangle\}$ 构成了平方可积函数空间的基础。

卷积定理

给定 $f,g\in L^2({\mathbb{R}}^d)f,\; g\; \backslash in\; L^2(\backslash mathbb\{R\}^d)$，它们的卷积定义为

$$(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$$

其傅里叶变换满足

$$\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)$$f​(ξ)⋅g​(ξ)

这种等价性将空间域滤波与频域逐点相乘联系起来。

---

2. 均匀采样与混叠效应

为了在实践中使用函数，我们需要将其离散化为有限点集。采样是指将连续信号离散化。信号 $f(x)f(x)$ 均匀采样为

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

其中 $TT$ 是采样间隔。

混叠

在采样过程中，我们只保留了 $f(x)f(x)$ 的有限点集，并丢弃了其余部分。丢弃有关原始函数的这些信息会带来许多问题。混叠就是其中之一。

混叠是由于采样不足导致频率内容重叠而产生的失真。当连续信号被采样时，其频谱会周期性重复。

设 ${\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)$，那么

$$\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)$$

如果原始频谱 $\widehat{f}\backslash widehat\{f\}$ 不是带限的，这些副本会重叠，导致混叠。（参见 WiKi）

下图描绘了信号 $XX$[13] 的情况。其中，${\omega }_s=\frac{1}{T}\backslash omega\_s\; =\; \backslash frac\{1\}\{T\}$，即采样频率。而 ${\omega }_s\backslash omega\_s$ 指的是信号中存在的最高频率。

由于混叠，当向上采样（即我们试图从有限样本 $f[n]f[n]$ 重构原始函数 $f(x)f(x)$ 时，我们看到了意想不到的模式。这意味着由于混叠，我们的原始信号现在完全丢失了，并且现在无法将其恢复。

奈奎斯特-香农采样定理[5]

为避免混叠，信号必须是带限的。

如果对于所有 $\mathrm{\mid }\xi \mathrm{\mid }\ge \frac{1}{2T}|\backslash xi|\; \backslash geq\; \backslash frac\{1\}\{2T\}$，则 $\widehat{f}(\xi )=0\backslash widehat\{f\}(\backslash xi)\; =\; 0$ 可以从其样本 $f(nT)f(nT)$ 完美重构。

---

3. 抗混叠：动机与构建（参见 WiKi）

为了抑制混叠，在采样之前应用一个低通滤波器

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

其中 $hh$ 是一个平滑核（例如高斯核）。在傅里叶域中

$$\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)$$

通过选择 $\widehat{h}(\xi )\approx 0\backslash widehat\{h\}(\backslash xi)\; \backslash approx\; 0$ 对于 $\mathrm{\mid }\xi \mathrm{\mid }>\frac{1}{2T}|\backslash xi|\; >\; \backslash frac\{1\}\{2T\}$，高频成分会被衰减。

---

优秀抗混叠滤波器的特性

• 频率快速衰减：高斯滤波器很常见。
• 各向同性：确保在所有方向上均匀平滑。
• 信号均值保留：$\int h(x)dx=1\backslash int\; h(x)\backslash ,dx\; =\; 1$

非正式地，这意味着即使在采样之后，如果我们遵循适当的抗混叠程序，我们也可以保留原始函数 $f(x)f(x)$ 的基本特征。

在信号处理文献中，带适当抗混叠的采样称为降采样。

---

4. 完美重构

问题来了：我们如何从其样本重构连续信号？

理想情况：香农重构公式 [6]

如果 $ff$ 带限于 $[-\frac{1}{2T},\frac{1}{2T}][-\backslash frac\{1\}\{2T\},\; \backslash frac\{1\}\{2T\}]$，则

$$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)$$

其中 $\text{sinc}(x)=\frac{\sin (\pi x)}{\pi x}\backslash text\{sinc\}(x)\; =\; \backslash frac\{\backslash sin(\backslash pi\; x)\}\{\backslash pi\; x\}$。此公式称为 sinc 插值。

希尔伯特空间中的基于帧的采样与抗混叠

设 $\mathcal{H}\backslash mathcal\{H\}$ 是一个希尔伯特空间（例如 $L^2({\mathbb{R}}^d)L^2(\backslash mathbb\{R\}^d)$，或流形或图上的函数）。我们考虑使用帧理论对采样和重构进行原理性处理，其中抗混叠被实现为向由帧跨越的子空间投影，采样/重构则通过分析和合成算子公式化。

---

1. 子空间 ${\mathcal{H}}^{†}\subset \mathcal{H}\backslash mathcal\{H\}^\backslash dagger\; \backslash subset\; \backslash mathcal\{H\}$ 的帧

设 ${\mathcal{H}}^{†}\subset \mathcal{H}\backslash mathcal\{H\}^\backslash dagger\; \backslash subset\; \backslash mathcal\{H\}$ 是一个有限维子空间（例如带限函数空间）。帧 $\{{\varphi }_i{\}}_{i=1}^N\subset {\mathcal{H}}^{†}\backslash \{\; \backslash phi\_i\; \backslash \}\_\{i=1\}^N\; \backslash subset\; \backslash mathcal\{H\}^\backslash dagger$ 满足帧条件

$$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$$

其中常数 。该框架允许通过其与框架元素 ${\varphi }_i\backslash phi\_i$ 的内积来稳定地表示任何 $f\in {\mathcal{H}}^{†}f\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$ 。

---

2. 反走样作为正交投影

假设原始信号 $f\in \mathcal{H}f\; \backslash in\; \backslash mathcal\{H\}$ 可能包含子空间 ${\mathcal{H}}^{†}\backslash mathcal\{H\}^\backslash dagger$ 之外的分量。为了**防止走样**，我们应用**反走样滤波器**，将 $ff$ 正交投影到子空间上

$$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$$

其中 $\{{\psi }_j\}\backslash \{\; \backslash psi\_j\; \backslash \}$ 是 ${\mathcal{H}}^{†}\backslash mathcal\{H\}^\backslash dagger$ 的正交基。这将在采样前移除与框架跨度正交的分量。

---

3. 作为广义采样的分析算子

**分析算子** $T:{\mathcal{H}}^{†}\to {\mathbb{R}}^{N}T:\; \backslash mathcal\{H\}^\backslash dagger\; \backslash to\; \backslash mathbb\{R\}^N$ 将函数映射到其框架系数

$$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$$

这不是信号处理中常用的**点采样**：除非框架元素是狄拉克函数（Dirac evaluations），否则算子测量的是**内积**，而不是值。这些框架有时也称为**点扩散函数**。

因此，对于一般信号 (f \in \mathcal{H})，**正确的采样流程**是

$$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. 合成算子与重构

假设我们已经使用**分析算子**计算了投影函数 $f^{†}\in {\mathcal{H}}^{†}f^\backslash dagger\; \backslash in\; \backslash mathcal\{H\}^\backslash dagger$ 的**框架系数**

$$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$$

将其集合成一个向量 $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 合成算子的定义

**合成算子** $T^{\ast }:{\mathbb{R}}^N\to {\mathcal{H}}^{†}T^*:\; \backslash mathbb\{R\}^N\; \backslash to\; \backslash mathcal\{H\}^\backslash dagger$ 通过将框架元素与给定系数组合来重建函数

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

因此，我们重构了一个近似值（如果一切都理想，则是精确函数），如下所示

$${\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$$

然而，除非框架是**紧的**，否则这种重构是**不精确的**。我们需要使用**框架算子**进行纠正。

---

4.2 框架算子与精确重构

将**框架算子** $S:{\mathcal{H}}^{†}\to {\mathcal{H}}^{†}S:\; \backslash mathcal\{H\}^\backslash dagger\; \backslash to\; \backslash mathcal\{H\}^\backslash dagger$ 定义为分析和合成的组合

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

那么对于任何 $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$$

这是一个**正定、自伴随**算子。因此，它是可逆的，我们可以通过以下方式从其框架系数中恢复 $f^{†}f^\backslash dagger$

$$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 对偶框架与重构公式

定义与 $T^{\ast }T^*$ 对应的**规范对偶框架** $\{{\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$ 如下

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

然后我们可以将精确重构公式写成

$$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$$

此公式始终成立，即使对于**冗余和非紧密**的框架也是如此。

---

4.4 特殊情况：紧密框架

如果框架是**紧密的**，即存在一个常数 $A>0A\; >\; 0$，使得

$$\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$$

则 $S=A\cdot \mathrm{I}\mathrm{d}S\; =\; A\; \backslash cdot\; \backslash mathrm\{Id\}$，且重构简化为

$$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$$

---

✅ 总结

• 抗锯齿算子：从空间 $\mathcal{H}\backslash mathcal\{H\}$ 投影到 ${\mathcal{H}}^{†}\backslash mathcal\{H^\backslash dagger\}$
• 分析算子：提取系数：$y_i=⟨f^{†},{\varphi }_i⟩y\_i\; =\; \backslash langle\; f^\backslash dagger,\; \backslash phi\_i\; \backslash rangle$
• 合成算子：重建：$T^{\ast }y={\sum }_i{y}_i{\varphi }_{i}T^*\; y\; =\; \backslash sum\_i\; y\_i\; \backslash phi\_i$
• 框架算子确保稳定性并允许求逆。
• 即使框架不紧密，对偶框架也能实现精确重建。
• 一个重要的启示是——即使框架不紧密，我们也可以通过将任何函数 $f\in \mathcal{H}f\; \backslash in\; \backslash mathcal\{H\}$ 投影到子空间 ${\mathcal{H}}^{†}\backslash mathcal\{H^\backslash dagger\}$ 来执行抗锯齿。我们将在开发子群采样的抗锯齿算子时利用此构造。

---

有限离散群上的表示和傅里叶分析

本节为有限非阿贝尔结构上的调和分析奠定了基础——这在现代机器学习（例如，等变网络）、信号处理和物理学中至关重要。

---

1. 群和子群

群 $GG$ 是一个带有二元运算 $\cdot \backslash cdot$ 并满足以下条件的集合：

• 封闭性：$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$
• 结合律：$(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)$
• 单位元：存在 $e\in Ge\; \backslash in\; G$，使得 $e\cdot g=g\cdot e=ge\; \backslash cdot\; g\; =\; g\backslash cdot\; e\; =\; g$
• 逆元：对于每个 $g\in Gg\; \backslash in\; G$，存在 $g^{-1}\in Gg^\{-1\}\; \backslash in\; G$，使得 $g\cdot g^{-1}=eg\; \backslash cdot\; g^\{-1\}\; =\; e$

子群 $H\le GH\; \backslash leq\; G$ 是一个在相同运算下本身也是一个群的子集。

---

2. 表示和群作用

2.1 群表示

有限群 $GG$ 的（有限维复数）表示 是一个同态映射

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

其中 $VV$ 是一个有限维复向量空间，而 $\mathrm{G}\mathrm{L}(V)\backslash mathrm\{GL\}(V)$ 是 $VV$ 上的可逆线性算子群。在固定基下，这给出了一个矩阵表示

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

我们要求

$$\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 群在集合上的作用

群在集合 $XX$ 上的作用是一个映射

$$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$$

满足

• $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$

当 $XX$ 是一个有限集时，这可以被视为一个置换表示。

---

3. 不可约表示 (Irreps)

一个表示 $\rho :G\to \mathrm{G}\mathrm{L}(V)\backslash rho:\; G\; \backslash to\; \backslash mathrm\{GL\}(V)$ 是不可约的，如果它没有真子空间、非零的 $GG$-不变子空间。也就是说，没有 $W\subset VW\; \backslash subset\; V$ 且 ，使得对于所有 $g\in Gg\; \backslash in\; G$，都有 $\rho (g)(W)\subseteq W\backslash rho(g)(W)\; \backslash subseteq\; W$。

我们将 $GG$ 的所有不等价不可约表示的集合表示为

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

重要事实：

• 不可约表示的数量等于 $GG$ 中共轭类的数量。
• $GG$ 的每个有限维酉表示都可以分解为不可约表示的直和。
• 维数满足平方和恒等式

$$\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. 有限群上的傅里叶变换

设 $f:G\to \mathbb{C}f:\; G\; \backslash to\; \backslash mathbb\{C\}$ 是群上的一个函数。$ff$ 的傅里叶变换是按不可约表示索引的矩阵集合

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

这里

• $\rho (g{)}^{\ast }\backslash rho(g)^*$ 是 $\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\}$,
• 矩阵块的总数等于 $GG$ 的不可约表示的数量。

---

4.1 傅里叶逆变换

函数 $ff$ 可以通过以下方式重建

$$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)$$

这推广了阿贝尔群的经典傅里叶逆变换公式。

---

4.2 普朗歇尔恒等式

傅里叶变换保持内积

$$⟨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. 群作用于傅里叶系数

令 $GG$ 通过左平移作用于函数

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

则傅里叶系数通过以下方式变换

$$\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)$$

同样地，右平移

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

作用方式为

$$\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)^*$$

因此，群作用在傅里叶域上引起矩阵共轭，这对于设计等变操作特别有用。

---

有限群上的采样理论：框架理论的推广

在本节中，我们将该理论推广到定义在有限群上的信号，其中信号域及其结构都是代数性的。

与一般的采样框架——其中采样被定义为与所选框架相关的分析算子——不同的是，在从子群 $G^{\downarrow }\subset GG^\backslash downarrow\; \backslash subset\; G$进行下采样的情况下，采样过程由固定采样矩阵 $\mathcal{S}\backslash mathcal\{S\}$决定，该矩阵选择仅限于子群的函数值。

在这种设置下，出现了一个附加要求：采样管道中的每个操作（采样、插值和抗混叠）必须在群作用下是等变的。也就是说，这些操作必须尊重群 $GG$ 的对称结构。

为了确保这一点，我们采用了一种更抽象、更通用的方法：我们将采样、插值和抗混叠定义为线性算子，每个算子都受到代数和谱约束——例如等变性和完美重构。这种算子理论的公式使我们能够系统地设计采样管道，同时保留群对称性。

---

1. 有限群上的信号与傅里叶变换

令 $GG$ 是一个有限群，其阶为 $\mathrm{\mid }G\mathrm{\mid }=N|G|\; =\; N$。在 $GG$ 上的实值函数空间为

$$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$$

使用固定的群元素枚举 $\{g_1,\dots ,g_N\}\backslash \{g\_1,\; \backslash dots,\; g\_N\backslash \}$，我们可以将任何 $x\in X_{G}x\; \backslash in\; X\_G$ 识别为向量 $x\in {\mathbb{R}}^{N}x\; \backslash in\; \backslash mathbb\{R\}^N$，通过

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

$xx$ 在 $GG$ 上的傅里叶变换是一个矩阵变换

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

其中 $F_{G}F\_G$ 是由 $GG$ 的不可约表示形成的傅里叶基，而 $\widehat{x}\in {\mathbb{C}}^N\backslash hat\{x\}\; \backslash in\; \backslash mathbb\{C\}^N$ 是傅里叶系数的集合。逆变换为

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

矩阵 $F_{G}F\_G$ 是酉矩阵，可以解释为将基变换为 $GG$ 的不可约谐波分量。

---

2. 采样与插值的矩阵形式

令 $S\in {\mathbb{R}}^{M\times N}S\; \backslash in\; \backslash mathbb\{R\}^\{M\; \backslash times\; N\}$ 为采样矩阵，其中 ，它选择坐标的一个子集（或在子群 $G^{\downarrow }\subset GG^\backslash downarrow\; \backslash subset\; G$ 上进行评估）。令 $I\in {\mathbb{R}}^{N\times M}I\; \backslash in\; \backslash mathbb\{R\}^\{N\; \backslash times\; M\}$ 为插值矩阵。

那么，标准的多速率管道可写为

$$\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$$

完美重构要求

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

这通常不满足，除非信号 $xx$ 满足某些频谱条件。这促使我们定义子群上的带限性。

---

3. 有限群上的子群采样定理

我们寻找一个插值矩阵 $II$ 使得

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

对于通过算子 $M\in {\mathbb{C}}^{N\times M}M\; \backslash in\; \backslash mathbb\{C\}^\{N\; \backslash times\; M\}$ 指定的子空间带限的信号成立，该算子将子群傅里叶系数 ${\widehat{x}}^{\downarrow }\in {\mathbb{C}}^M\backslash hat\{x\}^\backslash downarrow\; \backslash in\; \backslash mathbb\{C\}^M$ 关联到完整系数 $\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$$

这意味着

$$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$$

由于 ${\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$，我们得到

$$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$$

因此，如果插值矩阵选择为

$$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. 子群带限条件

令

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

为到 $MM$ 的列空间的正交投影。那么，如果 $\widehat{x}\in \text{Im}(\bar{M})\backslash hat\{x\}\; \backslash in\; \backslash text\{Im\}(\backslash bar\{M\})$，即 $\widehat{x}=\bar{M}\widehat{x}\backslash hat\{x\}\; =\; \backslash bar\{M\}\; \backslash hat\{x\}$，信号 $xx$ 位于由 $MM$ 定义的带限子空间中，并且

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

因此，信号可以从其采样值中通过以下方式重建：

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

---

5. 抗混叠算子和 $MM$ 的优化

设 $P_M=B(B^{†}B{)}^{-1}{B}^{†}P\_M\; =\; B\; (B^\backslash dagger\; B)^\{-1\}\; B^\backslash dagger$ 为空间 $\text{Span}(B)\backslash text\{Span\}(B)$ 上的**投影算子**。那么，这个算子可以看作是**理想的抗混叠滤波器**：将任何信号投影到完美重建成立的子空间中。

我们在傅里叶空间中定义抗混叠算子为：

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

我们的目标是**设计 $MM$**，使得

1. $P_{M}P\_M$ 在群作用下是等变的，
2. 所选子空间是平滑的（低变异），
3. 完美重建成立：$F_{G^{\downarrow }}^{-1}=S{F}_G^{-1}MF^\{-1\}\_\{G^\backslash downarrow\}\; =\; S\; F\_G^\{-1\}\; M$

---

5.1 $MM$ 设计的优化目标

我们通过约束优化来制定 $M\in {\mathbb{C}}^{N\times M}M\; \backslash in\; \backslash mathbb\{C\}^\{N\; \backslash times\; M\}$ 的学习：

$$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)$$

受以下约束：

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

• $\bar{T}\backslash bar\{T\}$ 是**雷诺算子**，它将线性映射投影到群作用下的等变空间中。
• $LL$ 是 $GG$ 的凯莱图的**图拉普拉斯算子**，用于衡量平滑度。
• 第一项强制**等变性**
• 第二项惩罚**非平滑子空间**

---

5.2 通过雷诺算子实现等变约束

${\widehat{P}}_M\backslash hat\{P\}\_M$ 在群作用下的等变性由以下条件强制执行：

$$\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)$$

其中 $\bar{T}\backslash bar\{T\}$ 是与**张量积表示**相关联的雷诺算子。

$${\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$$

这确保了抗混叠投影 $P_{M}P\_M$ 在傅里叶域中与群作用可交换。

---

📘 参考文献

1. Vetterli, M., Marziliano, P., & Blu, T. (2014). 采样具有有限创新率的信号。IEEE Signal Processing Magazine。

2. Chen, X., Sandryhaila, A., Moura, J. M. F., & Kovacevic, J. (2015). 图上的信号恢复：变异最小化。IEEE Transactions on Signal Processing。

3. Mouli, S. C., & Ribeiro, A. (2021). 用于群结构数据的等变下采样。Advances in Neural Information Processing Systems (NeurIPS)。

4. Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). 图信号处理的新兴领域：将高维数据分析扩展到网络和其他不规则域。IEEE Signal Processing Magazine。

5. Shannon, C. E. (1949). 有噪声通信。Proceedings of the IRE。

6. Unser, M. (2000). 采样——香农之后50年。Proceedings of the IEEE。

7. Pesenson, I. (2008). 组合图上的Paley–Wiener空间采样。Transactions of the American Mathematical Society。

8. Coifman, R. R., & Maggioni, M. (2006). 扩散小波。Applied and Computational Harmonic Analysis。

9. Belkin, M., & Niyogi, P. (2002). 用于降维和数据表示的拉普拉斯特征映射。Advances in Neural Information Processing Systems (NeurIPS)。

10. Doy, M. N., & Vetterli, M. (1995). 拉普拉斯金字塔的帧重建。In Proceedings of ICASSP。

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

12. Folland, Gerald B. A course in abstract harmonic analysis. CRC press, 2016。

13. Moschytz, G.S. (2019). 采样定理和混叠