从多分辨率到小波

PLAN

---

• 尺度函数（Scaling functions）
• 小波（Wavelets）
• Mallat 和 Meyer 定理的证明（Proof of the Mallat and Meyer’s theorem）

遗留问题

---

• Riesz 基没有正交性质 → 正交投影到 $P_{V_j}$ 上是不实际的。
• 如何从 Riesz 基构造一个希尔伯特基（Hilbert basis）？
• 我们希望构造一个函数序列 $\phi_{j, n}$，使得

$$P_{V_j} f = \sum_{-\infty}^{\infty}\left(f, \phi_{j, n}\right) \phi_{j, n}$$

尺度函数 Scaling functions

---

定理

---

设 $(Vj){j ∈ ℤ}$ 是一个多分辨率，并定义一个尺度函数（scaling function） $φ ∈ L^2(ℝ)$，其傅里叶变换满足：对于所有 $ω ∈ ℝ$，

$$\hat{\phi}(\omega) = \frac{\hat{\theta}(\omega)}{\left(\sum_{k=-\infty}^{+\infty} |\hat{\theta}(\omega + 2k\pi)|^2\right)^{1/2}}$$

同时定义函数

$$\phi_{j,n} = \frac{1}{\sqrt{2^j}} \phi\left(\cdot - \frac{2^j n}{2^j}\right)$$

则，对于所有 $j ∈ ℤ$，序列 $(\phi{j,n}){n ∈ ℤ}$ 是 $V_j$ 的一个希尔伯特基。

---

证明思路

根据多分辨率的定义，有：

$$\phi \in V_0 \Longrightarrow \exists\left(a_n\right)_{n \in \mathbb{Z}} \text { 使得 } \phi=\sum_{n \in \mathbb{Z}} a_n \theta(\cdot-n)$$

通过傅里叶变换可得：

$$\hat{\phi}(\omega)=\hat{a}(\omega) \hat{\theta}(\omega), \quad \omega \in \mathbb{R},$$

其中：

$$\hat{a}(\omega)=\sum_{n \in \mathbb{Z}} a_n e^{-i n \omega}$$

接下来需要在傅里叶域中表达 $(\phi(\cdot - n))_{n \in \mathbb{Z}}$ 的正交性。

定义 $\tilde{\phi}$ 使得 $\tilde{\phi}(t) = \overline{\phi}(-t)$。于是，对于所有 $(n, p) \in \mathbb{Z}^2$，有：

$$(\phi(\cdot - n), \phi(\cdot - p)) = \int_{-\infty}^\infty \phi(t - n) \overline{\phi}(t - p) \, dt = (\phi \ast \tilde{\phi})(n - p).$$

因此，$(\phi(\cdot - n))_{n \in \mathbb{Z}}$ 正交当且仅当：

$$(\phi \ast \tilde{\phi})(n) = 1_{n = 0}.$$

注意：$\phi \ast \tilde{\phi}$ 的傅里叶变换为：

$$\omega \mapsto |\hat{\phi}(\omega)|^2.$$

通过采样 $\gamma = \phi \ast \tilde{\phi}$，得到一个分布 $\gamma_1$，其傅里叶变换为：

$$\widehat{\gamma}_1(\omega)=\sum_{k=-\infty}^{\infty} \widehat{\gamma}(\omega-2 k \pi)$$

因此，正交性等价于：

$$\sum_{k = -\infty}^\infty |\hat{\phi}(\omega + 2k\pi)|^2 = 1, \quad \omega \in \mathbb{R}.$$

这意味着我们必须选择：

$$\hat{a}(\omega) = \left( \sum_{k = -\infty}^\infty |\hat{\theta}(\omega + 2k\pi)|^2 \right)^{-1/2}.$$

示例

---

分段常数多分辨率

$\theta=\mathbb{1}_{[0,1[ }$， 导致 Riesz 基 $(\theta(\cdot - n)){n \in \mathbb{Z}}$ 是正交的。

因此，$\phi = \theta$，并且生成的函数 $\phi_{j,n}$ 形成 $V_j$ 的希尔伯特基，如前所示。

Shannon 多分辨率

$\theta : t \mapsto \frac{\sin(\pi t)}{\pi t}$， 导致 $(\theta(\cdot - n))_{n \in \mathbb{Z}}$ 是正交 Riesz 基。

因此，设 $\phi = \theta$。

样条多分辨率

通过卷积/乘积规则计算傅里叶变换，并应用上述定理。

---

$$\tilde{\theta}_m(\omega) = \left( \frac{\sin(\omega/2)}{\omega/2} \right)^{m+1} \exp \left( -i \varepsilon \frac{\omega}{2} \right),$$

其中：

$$\varepsilon = \begin{cases} 1, & m \text{ 为偶数}, \\ 0, & m \text{ 为奇数}. \end{cases}$$

---

$$\hat{\phi}(\omega) = \frac{\exp \left( -i \varepsilon \frac{\omega}{2} \right)}{\omega^{m+1} \sqrt{S_{2,m+2}(\omega)}},$$

其中：

$$S_m(\omega) = \sum_{\ell = -\infty}^\infty \frac{1}{(\omega + 2\ell\pi)^m}.$$

具体示例：对于 $S_8(2\omega)$，有：

$$S_8(2\omega) = \frac{5 + 30 \cos^2(\omega) + 30 \sin^2(\omega) \cos^2(\omega)}{105 \cdot 2^8 \sin^8(\omega)} + \frac{70 \cos^4(\omega) + 2 \sin^4(\omega) \cos^2(\omega) + \frac{2}{3} \sin^6(\omega)}{105 \cdot 2^8 \sin^8(\omega)}.$$

总结

---

• 多分辨率

  多分辨率是一系列希尔伯特子空间 $(Vj){j \in \mathbb{Z}}$，用于描述在尺度 $2^j$ 下的函数。

• 子空间的特性

  每个 $Vj$ 由 $V_0$ 的一个 Riesz 基 $(\theta(\cdot - n)){n \in \mathbb{Z}}$ 所表征，例如分段常数、样条等。

• 尺度函数

  通过对 $(\theta(\cdot - n)),{n \in \mathbb{Z}}$ 进行正交化，我们可以导出一个尺度函数 $\phi$，它生成 $Vj$ 的希尔伯特基 ${\phi{j,n}}_{n \in \mathbb{Z}}$。这些基函数由 $\phi$ 通过尺度和平移得到：

  $$\phi_{j,n} = \frac{1}{\sqrt{2^j}} \phi\left(\cdot - \frac{2^j n}{2^j}\right).$$

• 多分辨率的意义

  多分辨率的概念使得我们可以在不同尺度下构建 $f$ 的近似层次结构，从而保证无信息丢失。但这对压缩有何用处？

小波 Wavelets

---

主要思想 main idea

---

对于 $j \in \mathbb{Z}$，构造一个 Hilbert 子空间 $W_{j+1}$，使得

$$V_{j+1} \oplus W_{j+1} = V_j$$

因此，对于任意 $f \in L^2(\mathbb{R})$，满足

$$P_{V_j}f = P_{V_{j+1}}f + P_{W_{j+1}}f$$

即，$P{W{j+1}}f$ 包含了 $f$ 在尺度 $2^j$ 存在但在尺度 $2^{j+1}$ 消失的细节信息。

事实上，我们可以理解为：

• $P{V{j+1}}f$ 对应于通过低通滤波器 (low-pass filter) 对 $P_{V_j}f$ 进行滤波。
• $P{W{j+1}}f$ 对应于通过高通滤波器 (high-pass filter) 对 $P_{V_j}f$ 进行滤波。

共轭镜像滤波器 Conjugate Mirror Filter

---

定义

令 $\phi \in L^2(\mathbb{R})$ 是一个尺度函数。对所有 $n \in \mathbb{Z}$，定义：

$$h_n = \left( \frac{1}{\sqrt{2}} \phi(\cdot / 2), \phi(\cdot - n) \right)$$

这些是 $\frac{1}{\sqrt{2}} \phi(\cdot / 2)$ 在 $V_1$ 上投影到 $V_0$ 的系数：

$$\frac{1}{\sqrt{2}} \phi(\cdot / 2) = \sum_n h_n \phi(\cdot - n)$$

序列 $(hn){n \in \mathbb{Z}}$ 是一个低通滤波器 (low-pass filter) 的冲激响应，称为共轭镜像滤波器 (conjugate mirror filter)。

---

注记

$$\frac{1}{\sqrt{2}} \phi(\cdot / 2) = \sum_n h_n \phi(\cdot - n) \implies \sqrt{2} \widehat{\phi}(2\omega) = \widehat{\phi}(\omega) \cdot \left( \sum_n h_n e^{-i n \omega} \right), \quad \omega \in \mathbb{R} \tag{1}$$

• 通过对两边取傅里叶变换，考虑傅里叶级数

  $$\widehat{h}(\omega) = \sum_n h_n e^{-i n \omega}, \quad \omega \in \mathbb{R}$$

• 傅里叶级数是 $2\pi$-周期的)。

• 我们可以将 $(1)$ 重写为：

$$\widehat{\phi}(2\omega) = \widehat{\phi}(\omega) \frac{\widehat{h}(\omega)}{\sqrt{2}}, \quad \omega \in \mathbb{R}$$

---

示例

1. Shannon 多分辨率 (Shannon Multiresolution):

   • $\widehat{\phi} = \mathbf{1}_{[-\pi, \pi]}$。

   • 因此，$\forall \omega \in [-\pi, \pi]$：

     $$\mathbb{1}_{[-\pi / 2, \pi / 2]}=\mathbb{1}_{[-\pi, \pi]} \widehat{h}(\omega) / \sqrt{2}$$

   • 由此可得，$\forall \omega \in [-\pi, \pi]$：

     $$\widehat{h}(\omega) = \sqrt{2} \cdot \mathbf{1}_{[-\pi/2, \pi/2]}(\omega).$$

2. 分段常值多分辨率 (Piecewise Constant Multiresolution):

   • $\phi = \mathbf{1}_{[0, 1]}$。

   • 由

     $$h_n = \left( \frac{1}{\sqrt{2}} \phi(\cdot / 2), \phi(\cdot - n) \right),$$

   • 得

     $$h_n = \begin{cases} 2^{-1/2}, & \text{如果 } n = 0, 1, \\ 0, & \text{其他情况}. \end{cases}$$

   • 这有时被称为局部平均 (local average)。

3. 样条多分辨率 (Spline Multiresolution):

   • 对于 $m$ 阶 box 样条， $\widehat{\phi}$ 的表达式

     $$\hat{\phi}(\omega) = \frac{\exp \left( -i \varepsilon \frac{\omega}{2} \right)}{\omega^{m+1} \sqrt{S_{2,m+2}(\omega)}},$$

   • 代入$\widehat{\phi}(2\omega) = \widehat{\phi}(\omega) \frac{\widehat{h}(\omega)}{\sqrt{2}}, \quad \omega \in \mathbb{R}.$

   • 得，$\forall \omega \in \mathbb{R}$：

     $$\widehat{h}(\omega) = \exp\left(-\frac{i \omega}{2}\right) \sqrt{\frac{S_{2m+2}(\omega)}{2^{m+1} S_{2m+2}(2\omega)}}.$$

高通滤波器的构造

---

• 令 $\phi \in L^2(\mathbb{R})$ 为一个尺度函数，$(hn){n \in \mathbb{Z}}$ 为相应的共轭镜像滤波器。
• 定义一个滤波器 $(gn){n \in \mathbb{Z}}$，其傅里叶变换满足以下条件：

$$\widehat{g}(\omega) = e^{-i\omega} \widehat{h}(\omega + \pi), \quad \forall \omega \in \mathbb{R}.$$

---

注记

• 根据傅里叶变换的性质：

$$g_n = (-1)^{1-n} h_{1-n}, \quad \forall n \in \mathbb{Z}.$$

• $(g_n)$ 是一个高通滤波器 (high-pass filter)，因为：

  $$|\widehat{g}(\omega)| = |\widehat{h}(\omega + \pi)|,$$

  且 $\widehat{h}$ 是 $2\pi$-周期函数。

Mallat-Meyer定理

---

令 $\phi \in L^2(\mathbb{R})$ 为一个尺度函数，$(gn){n \in \mathbb{Z}}$ 为对应的滤波器（如前述定义）。考虑函数 $\psi \in L^2(\mathbb{R})$，称为小波函数 (wavelet function)，其傅里叶变换满足：

$$\widehat{\psi}(2\omega) = \frac{\widehat{\phi}(\omega) \widehat{g}(\omega)}{\sqrt{2}}, \quad \forall \omega \in \mathbb{R}.$$

此外，对于所有 $(j, n) \in \mathbb{Z}^2$，定义：

$$\psi_{j, n}(t) = \frac{1}{\sqrt{2^j}} \psi \left( \frac{t - 2^j n}{2^j} \right).$$

则，对于任意 $j \in \mathbb{Z}$ 和对应的尺度 $s = 2^j$，集合 ${\psi{j, n}}{n \in \mathbb{Z}}$ 是子空间 $W_j$ 的一个Hilbert 基。

此外，对于整体尺度范围，集合 ${\psi{j, n}}{(j, n) \in \mathbb{Z}^2}$ 是 $L^2(\mathbb{R})$ 的一个称为小波基 (wavelet basis) 的 Hilbert 基。

---

1. $\psi(\cdot / 2) \in W_1 \subset V_0$，因此存在 $(g_n){n \in \mathbb{Z}}$ 使得：

   $$\frac{1}{\sqrt{2}} \psi(\cdot / 2) = \sum{n = -\infty}^\infty g_n \phi(\cdot - n),$$

   其中：

   $$g_n = \left( \frac{1}{\sqrt{2}} \psi(\cdot / 2), \phi(\cdot - n) \right).$$

2. 取傅里叶变换：

   $$\widehat{\psi}(2\omega) = \frac{\widehat{\phi}(\omega) \widehat{g}(\omega)}{\sqrt{2}}, \quad \omega \in \mathbb{R}.$$

---

示例

Haar 小波 (Haar Wavelets)

1. 尺度函数 (Scaling Function):

   $$\phi = \mathbf{1}_{[0, 1]}$$

2. 共轭镜像滤波器 (Conjugate Mirror Filter):

   $$h_n = \begin{cases} 2^{-1/2}, & \text{if } n = 0, 1, \\ 0, & \text{otherwise.} \end{cases}$$

3. 滤波器 $(g_n)$:

   $$g_n = \begin{cases} -2^{-1/2}, & \text{if } n = 0, \\ 2^{-1/2}, & \text{if } n = 1, \\ 0, & \text{otherwise.} \end{cases}$$

4. 小波函数 (Wavelet):

   $$\psi(t) = \begin{cases} -1, & \text{if } 0 \leq t < 1/2, \\ 1, & \text{if } 1/2 \leq t < 1, \\ 0, & \text{otherwise.} \end{cases}$$

Shannon 小波 (Shannon Wavelets)

1. 尺度函数 (Scaling Function):

   $$\phi(t) = \frac{\sin(\pi t)}{\pi t}$$

2. 共轭镜像滤波器 (Conjugate Mirror Filter):

   $$\widehat{h}(\omega) = \sqrt{2} \cdot \mathbf{1}_{[-\pi/2, \pi/2]}(\omega)$$

3. 滤波器 $(g_n)$:

   $$\widehat{g}(\omega) = \begin{cases} e^{-i\omega/2}, & \text{if } \omega \in [-2\pi, \pi] \cup [\pi, 2\pi], \\ 0, & \text{otherwise.} \end{cases}$$

4. 小波函数 (Wavelet):

   $$\psi(t) = \frac{\sin(2\pi(t - 1/2))}{\pi(t - 1/2)} - \frac{\sin(\pi(t - 1/2))}{\pi(t - 1/2)}.$$

Battle-Lemarié / Cubic Spline 小波

$L^2(\mathbb{R})$ 的分解

---

Parseval 等式:
对于 $f \in L^2(\mathbb{R})$，

$$f = \sum_{j \in \mathbb{Z}} P_{W_j}f = \sum_j \sum_n \langle f, \psi_{j,n} \rangle \psi_{j,n}.$$

$f$ 是通过不同尺度的子空间 $W_j$ 分解成多个分量的和。

---

另一种 Hilbert 空间分解

• Hilbert 空间的表达:

  $$L^2(\mathbb{R}) = V_J \oplus \bigoplus_{j=J}^{\infty} W_j,$$

  其中 $J$ 是某个粗略尺度。

• 对于任意 $f \in L^2(\mathbb{R})$，

  $$\begin{aligned} f & =P_{V_J} f+\sum_{j=-\infty}^J P_{W_j} f \\ & =\sum_{n=-\infty}^{\infty}\left(f, \phi_{J, n}\right) \phi_{J, n}+\sum_{j=-\infty}^J \sum_{n=-\infty}^{\infty}\left(f, \psi_{j, n}\right) \psi_{j, n} \end{aligned}$$

Mallat-Meyer定理的证明

---

定理1

对于共轭镜像滤波器 $(hn){n \in \mathbb{Z}}$，其傅里叶变换（傅里叶级数形式）表示为：

$$\widehat{h}(\omega) = \sum{n} h_n e^{-i n \omega}, \quad \omega \in \mathbb{R},$$

满足以下性质：

1. 对于任意 $\omega \in \mathbb{R}$：

   $$|\widehat{h}(\omega)|^2 + |\widehat{h}(\omega + \pi)|^2 = 2.$$

2. $\widehat{h}(0) = \sqrt{2}.$

---

定理 2

反之，令 $\widehat{h}$ 是一个 $2\pi$-周期函数，并满足以下条件：

1. $\widehat{h} \in C^1$ 在零点邻域中连续可导；
2. 在 $\omega \in [-2\pi, 2\pi]$ 内有 $\inf |\widehat{h}(\omega)| > 0$；

3. 对于任意 $\omega \in \mathbb{R}$：

   $$|\widehat{h}(\omega)|^2 + |\widehat{h}(\omega + \pi)|^2 = 2;$$

4. $\widehat{h}(0) = \sqrt{2}.$

则傅里叶变换为

$$\widehat{\phi}(\omega) = \prod_{j=1}^\infty \frac{\widehat{h}(2^{-j}\omega)}{\sqrt{2}}, \quad \omega \in \mathbb{R},$$

的函数 $\phi \in L^2(\mathbb{R})$ 是一个尺度函数。

---

证明

• 假设 $(h_n)$ 是一个共轭镜像滤波器：

  $$\widehat{\phi}(2\omega) = \frac{\widehat{\phi}(\omega) \widehat{h}(\omega)}{\sqrt{2}}, \quad \omega \in \mathbb{R}.$$

• 对任意 $p \in \mathbb{Z}$，有：

$$\widehat{\phi}(2^{p+1}\omega) = \frac{\widehat{\phi}(2^p\omega)\widehat{h}(2^p\omega)}{\sqrt{2}}.$$

• 反复迭代，得到

$$\widehat{\phi}(\omega) = \prod_{p=1}^K \frac{\widehat{h}(2^{-p}\omega)}{\sqrt{2}} \cdot \widehat{\phi}(2^{-K}\omega).$$

• 当 $K \to \infty$ 时，$\widehat{\phi}(2^{-K}\omega) \to 1$，因此：

$$\widehat{\phi}(\omega) = \prod_{p=1}^\infty \frac{\widehat{h}(2^{-p}\omega)}{\sqrt{2}}.$$

---

Hilbert 基的正交归一性

• 归一性关系

$$\sum_{k=-\infty}^\infty |\widehat{\phi}(\omega + 2k\pi)|^2 = 1, \quad \omega \in \mathbb{R}.$$

• 该公式表达了 $(\phi(\cdot - n))_{n \in \mathbb{Z}}$ 的 Hilbert 基正交归一性。

• 带入 $\widehat{\phi}(2\omega) = \frac{\widehat{\phi}(\omega)\widehat{h}(\omega)}{\sqrt{2}}$:

  $$\sum_{k=-\infty}^\infty \left| \widehat{h}\left(\frac{\omega}{2} + k\pi\right) \right|^2 \cdot \left| \widehat{\phi}\left(\frac{\omega}{2} + k\pi\right) \right|^2 = 2.$$

• 使用 $k = 2p$ 或 $k = 2p+1$ 进行拆分，重新排列得到：

$$\left|\widehat{h}\left(\frac{\omega}{2}\right)\right|^2 \sum_{p=-\infty}^\infty \left|\widehat{\phi}\left(\frac{\omega}{2} + 2p\pi\right)\right|^2 + \left|\widehat{h}\left(\frac{\omega}{2} + \pi\right)\right|^2 \sum_{p=-\infty}^\infty \left|\widehat{\phi}\left(\frac{\omega}{2} + (2p+1)\pi\right)\right|^2 = 2.$$

• 再次带入

  对 $\omega’ = \frac{\omega}{2}$ 或 $\omega’ = \frac{\omega}{2} + \pi$，最终得到：

  $$|\widehat{h}(\omega')|^2 + |\widehat{h}(\omega' + \pi)|^2 = 2.$$

---

• 结论 $|\widehat{h}(\omega)|^2 + |\widehat{h}(\omega + \pi)|^2 = 2$ 是 $(\phi(\cdot - n))_{n \in \mathbb{Z}}$ 成为 Hilbert 基的必要条件。
• 它对应于正交归一要求，保证尺度函数 $\phi$ 的构造正确。

---

Hilbert 基的构造

为了证明 $(\psi(\cdot - n))_{n \in \mathbb{Z}}$ 是 $W_0$ 的 Hilbert 基，需要使用以下引理。

引理

• 序列 $(\psi{j,n}){n \in \mathbb{Z}}$ 是 $W_j$ 的 Hilbert 基，当且仅当以下两个条件成立：

  1. $\widehat{g}(\omega)$ 满足归一性：

     $$|\widehat{g}(\omega)|^2 + |\widehat{g}(\omega + \pi)|^2 = 2.$$

  2. $\widehat{g}(\omega)$ 与 $\widehat{h}(\omega)$ 的正交性条件：

     $$\widehat{g}(\omega) \widehat{h}^*(\omega)+\widehat{g}(\omega+\pi) \widehat{h}^*(\omega+\pi)=0$$

• 解释：

  • 条件 (i) 对应于 $(\psi(\cdot - n))_{n \in \mathbb{Z}}$ 的正交归一性。
  • 条件 (ii) 保证 $W_0$ 与 $V_0$ 正交，即 $(\psi, \phi(\cdot - n)) = 0$ 对于所有 $n \in \mathbb{Z}$。

---