多分辨率分析
前言——浅谈内积与正交性
还记得本学期开始上课的时候，老师就在不断强调“内积”这个概念的重要性，说是学会了内积，剩下的都是细节。当差不多学到了尾声，回头看看可能这句话也没有那么言过其实。从引入正题的傅里叶级数起，每一次信号处理实质上都是求内积的过程。老师特别喜欢挂在嘴边的的一句话是“内积表示相似性”，不管是前面的傅里叶变换、窗口傅里叶变换，还是后面将要讲的小波变换、小波包、提升小波，实质上都是在空间上找一组标准正交基，再用我们的信号去和每一个基函数去做内积，去得到它们之间的相似性。\(f=\sum\langle f,e_i\rangle e_i\)。重新观察这个式子，信号与基函数越接近，就在构造其时在该基函数上乘上越大的系数再组合起来。我们整学期课程学习的信号处理在某种程度上就可以理解为将信号变为一串系数列，通过某种阈值筛选之后再重新组合起来。
上次最后说要找正交小波，其实正交性的作用在上面的叙述之后也逐渐变得明朗起来，正是正交性保证了上面的重构公式的存在性。如果只有基性质没有正交性，虽然理论上求出系数也是可行的，但是需要通过求解大型线性方程组，这就意味着大量开销与不可避免的误差。有了正交性，系数就可以通过内积计算，本质上就是加法和乘法，计算的开销会小得多，误差也更容易控制。
多分辨率分析(MRA)
1988年，Mallat创造性地将多分辨率分析的概念与构造正交小波基结合起来，从空间的概念上形象地给出了一个构造正交小波基函数的通用框架。
定义
设\(\{V_j\}\)是\(L^2(\mathbb{R})\)的一个闭子空间系列，\(\{V_j\}\)称为\(L^2(\mathbb{R})\)的一个多分辨率分析，如果满足 \[ V_j\subset V_{j+1} \tag{1} \]
\[ \overline{\bigcup V_j}=L^2(\mathbb{R}) \tag{2} \]
\[ \bigcap V_j=\{0\} \tag{3} \]
\[ f(t)\in V_j \iff f(2t)\in V_{j+1} \tag{4} \]
\[ f(t)\in V_0\iff f(t-k)\in V_0 \tag{5} \]
\[ \exists \phi \in V_0,\{\phi(t-k)\}构成V_0标准正交基 \tag{6} \]
前三条实质上只是指出了一个嵌套的关系，第四条指出函数伸缩性，第五条指出其平移不变性，第六条是一个核心的性质，\(\phi\)为尺度函数真正刻画了空间的模样。
容易看出有结论 \[ \{\phi_{j,k}(t)=2^{j/2}\phi(2^j t-k)\} \] 为\(V_j\)的标准正交基。
一个例子
上课时候通过这些性质直接进行理论推导确实没什么感觉，所以先举个例子来直观感受一下。
之前提到过一个最简单的小波例子——haar小波
它所对应的尺度函数\(\phi(x)=I_{[0,1)}\)，生成的多分辨率分析为 \[ V_j=\{f(x)\in L^2(\mathbb{R})|f(x)=c_k\in[\frac{n}{2^j},\frac{n+1}{2^j})\} \] 这就是用一串不断加细节的趋向于\(L^2\)的空间。
haar小波为 \[ \psi (t)= \begin{cases} 1,&0\le t<1/2\\ -1,&1/2\le t<1\\ 0,&else \end{cases} \] 做内积直观上就是算两部分函数的差。如果将信号看成一张图片，那么一块像素点的平均值，或者说它们的和性质是刻画了它们的整体特征；而像素点之间的差性质则是刻画了局部的细节轮廓。使用小波函数其实就是不断将信号分成整体与细节两部分，尺度函数就对应整体的部分，而小波函数对应细节的部分，两者结合则给出了信号的全部信息。
双尺度方程
时域描述
由空间的嵌套性，我们有\(\phi(t)\in V_1\)则存在系数使得 \[ \phi(t)=\sum_k h_k\phi(2t-k) \] 这里的系数\(\{h_k\}\)就称为双尺度系数
由\(\{\phi(2t-k)\}\)的标准正交性可以得到\(h_k\)的计算公式 \[ h_k=2\int_\mathbb{R}\phi(t)\overline{\phi(2t-k)}dt \]
容易验证双尺度系数满足以下性质 \[ \begin{aligned} &\sum h_{k-2n}\overline{h_{k-2m}}=2\delta_{m,n}\\ &\sum |h_k|^2=2\\ &\sum h_k = 2\\ &\sum h_{2k}=\sum h_{2k+1}=1 \end{aligned} \]
频域描述
对双尺度方程\(\phi(t)=\sum_k h_k\phi(2t-k)\)两边做傅里叶变换可得 \[ \hat{\phi}(\lambda)=\frac{1}{2}\sum_k h_k e^{-\frac{ik\lambda}{2}}\hat{\phi}(\frac{\lambda}{2}) \] 令\(H(\lambda)=\frac{1}{2}\sum_k h_k e^{-ik\lambda}\)，则\(\hat{\phi}(\lambda)=H(\frac{\lambda}{2})\hat{\phi}(\frac{\lambda}{2})\)
这即为双尺度方程的频域表示。
一个重要的定理
假设\(\phi\in L^2(\mathbb{R})\)，则\(\{\phi(t-k)\}\)是标准正交集的充要条件是 \[ \sum|\hat{\phi}(\lambda+2k\pi)|^2=\frac{1}{2\pi} \] 此定理证明就是把标准正交条件写出来，两边作傅里叶变换即可，技术上很容易想到。它的重要性在于它不仅给出了一种验证标准正交性的方式，更是给出了一种构造的方式。
事实上只要令 \[ \hat{\phi}^*(\lambda)=\frac{\hat{\phi}(\lambda)}{(2\pi \sum |\hat{\phi}(\lambda+2k\pi)|^2)^{1/2}} \] 则可以通过频域上的伸缩变换给出一个满足标准正交性的尺度函数。
此外有性质 \[ |H(\lambda)|^2+|H(\lambda + \pi)|^2=1 \]
小波滤波器
引入\(g_k=(-1)^k\bar{h}_{1-k}\)，并类似地记\(G(\lambda)=\frac{1}{2}\sum g_ke^{-ik\lambda}\)，则其有以下性质： \[ \begin{aligned} &\sum g_{k-2n}\overline{g_{k-2m}}=2\delta_{m,n}\\ &\sum h_{k-2n}\overline{g_{k-2m}}=0\\ &\sum h_{n-2k}\overline{h_{m-2k}}+g_{n-2k}\overline{g_{m-2k}}=2\delta_{m,n}\\ &G(\lambda)=-e^{-i\lambda}\overline{H(\lambda+\pi)}\\ &|G(\lambda)|^2+|G(\lambda + \pi)|^2=1\\ &H(\lambda)\overline{G(\lambda)}+H(\lambda + \pi)\overline{G(\lambda + \pi)}=1 \end{aligned} \]
小波子空间和\(L^2\)空间的正交分解
令\(\psi(x)=\sum g_k\phi(2x-k)\)
\(Thm\) 记\(W_j\)是函数系列\(\{\psi_{j,k}(x)=\psi(2^j-k)\}\)张成的空间，则\(W_j\)是\(V_{j+1}\)中\(V_j\)的正交补空间，并且\(\psi_{j,k}(x)\)为\(W_j\)的一个标准正交基。
这是一个非常优美的结论。此定理从理论上证明了前面说的所谓整体性质与细节的分解的可行性，大空间包含的信息恰好是较小的空间与一个“细节空间”所能包含信息的和！至此，有空间的分解 \[ V_j=V_{j-1}\oplus W_j=V_{j-2}\oplus W_{j-1}\oplus W_{j}=\cdots \]
构造正交小波通用方法
整理一下上面的步骤。首先找到多分辨率序列\(\{V_j\}\)以及其尺度函数\(\phi(x)\)，求出对应的双尺度函数\(h_k\)，接着就可以得到正交小波基函数\(\psi(x)=\sum (-1)^k\overline{h_{1-k}}\phi(2x-k)\)
常见小波
Haar小波： \[ V_j=\{f(x)\in L^2(\mathbb{R})|f(x)=c_k\in[\frac{n}{2^j},\frac{n+1}{2^j})\} \]
\[ \psi (t)= \begin{cases} 1,&0\le t<1/2\\ -1,&1/2\le t<1\\ 0,&else \end{cases} \]
Shannon小波： \[ V_j=\{f(x)\in L^2(\mathbb{R})|supp(\hat{f}(\lambda))\in[-2^j\pi,2^j\pi] \} \]
\[ \psi(t)= \begin{cases} 1,&t=0\\ \frac{\sin(\pi x)}{\pi x},&else \end{cases} \]
Haar小波光滑性太差，Shannon小波虽然光滑性好，但是支集太大，处理时也会差生较大误差。于是希望构造一个连续又紧支的小波函数。
线性样条小波（Battle-Lemarie小波）： \[ V_j=\{f(x)\in L^2(\mathbb{R})\cap C^1(\mathbb{R})|f(x)=c_k x+d_k,x\in[\frac{n}{2^j},\frac{n+1}{2^j})\} \]
\[ \psi (t)= \begin{cases} t+1,&-1\le t\le 0\\ 1-t,&0< t\le 1\\ 0,&else \end{cases} \] 这样的函数满足刚才提出的希望条件，但是不满足正交性，可以用之前介绍的方式通过频域上的变换使之正交化即可。这样产生的小波函数和尺度函数都很快趋于零。
分解重构算法
正如前言所说，我们对于信号的处理本质上就是分解重构。下面介绍在多分辨率分析下的小波的分解与重构算法。
初始化
由原始信号投影到某个\(V_j\)空间上。由于我们不能处理直接无限的信号信息，首先应当选取一个合适的空间，将信号转化为若干基函数的线性组合，再对系数作操作。
分解
这是多分辨率分析的核心，将空间\(V_j\)上的信号分解到\(V_{j-1}\)与\(W_{j-1}\)上。每一步都从当前主要信息中提取整体信息和细节信息。 \[ \begin{aligned} f_j(x)&=\sum c_{j,k}\phi_{j,k}(x)\\ f_{j-1}(x)&=\sum c_{j-1,k}\phi_{j-1,k}(x)\\ w_{j-1}(x)&=\sum d_{j-1,k}\phi_{j-1,k}(x) \end{aligned} \]
要做的就是根据系数\(\{c_{j,k}\}\)计算\(\{c_{j-1,k}\}\)与\(\{d_{j-1,k}\}\)。 \[ f_j(x)=f_{j-1}(x)+w_{j-1}(x) \] 则 \[ c_{j-1,l}=\sum c_{j,k}\langle \phi_{j,k},\phi_{j-1,l}\rangle \] 又双尺度方程 \[ \phi(t)=\sum h_k\phi(2t-k) \] 可推出 \[ \phi_{j-1,l}(t)=2^{-1/2}\sum h_{k-2l}\phi_{j,k}(t) \] 于是
\[ c_{j-1,l}=2^{-1/2}\sum c_{j,k}\overline{h_{k-2l}} \] 同理由小波方程可得 \[ d_{j-1,l}=2^{-1/2}\sum c_{j,k}\overline{g_{k-2l}} \]
重构
分解完即可对这些系数信息进行一定的调整以达到去噪增强等效果，之后按原样组合起来。重构算法即根据系数\(\{c_{j-1,k}\}\)与\(\{d_{j-1,k}\}\)计算\(\{c_{j,k}\}\)。
由于 \[ \begin{aligned} \phi_{j-1,l}(t)=2^{-1/2}\sum h_{k-2l}\phi_{j,k}(t)\\ \psi_{j-1,l}(t)=2^{-1/2}\sum g_{k-2l}\phi_{j,k}(t) \end{aligned} \] 可得 \[ c_{j,l}=2^{-1/2}\sum c_{j-1,k}h_{l-2k}+2^{-1/2}\sum d_{j-1,k}g_{l-2k} \] 即可
小波滤波器
上面这样的操作过程可以有更简洁的离散滤波器的形式来表现。
定义下采样算子 \[
D:(\cdots,x_{-1},x_0,x_1,\cdots)\to (\cdots,x_{-2},x_0,x_2,\cdots)
\] 则分解算法即 \[
\begin{cases}
c^{j-1}=D(c^j*\bar{h}^*)\\
d^{j-1}=D(c^j*\bar{g}^*)
\end{cases}
\] 其中 \[
\begin{aligned}
\bar{h}^*=\{\frac{1}{\sqrt2}\bar{h}_{-k} \}\\
\bar{g}^*=\{\frac{1}{\sqrt2}\bar{g}_{-k} \}
\end{aligned}
\] 重构算法类似，引入上采样算子 \[
U:(\cdots,x_{-1},x_0,x_1,\cdots)\to (\cdots,x_{-1},0,x_0,0,x_1,\cdots)
\] 则 \[
c^j=Uc^{j-1}*h+Ud^{j-1}*g
\] 其中 \[
\begin{aligned}
h=\{\frac{1}{\sqrt2}h_k \}\\
g=\{\frac{1}{\sqrt2}g_k \}
\end{aligned}
\] 
大致流程图如上。
尺度函数的迭代构造
上面根据尺度空间张成的多分辨率分析嵌套空间，我们构造出了一组正交小波，那么尺度函数本身应该如何构造呢。
\(Thm\) 假设\(\phi\)是一个具有紧支集的连续函数，并且满足标准正交化条件、标准化条件（积分为1）、双尺度方程（只有有限个\(h_k\)非零）。则\(V_j\)构成一个多分辨率分析。
\(Thm\) 假设\(P(z)=\frac{1}{2}\sum h_k z^k\)是一个多项式满足\(P(1)=1\)，\(|P(z)|^2+|P(-z)|^2=1,|z|=1\)，\(|P(e^{it})|>0,|t|<\pi/2\)。\(\phi_0\)为Haar尺度函数，\(\phi_n(x)=\sum h_k\phi_{n-1}(2x-k)\)，则\(\phi_n\)依范数收敛到\(\phi\)且\(\phi\)满足上述定理三个条件。
例如\(P(z)=\frac{1+z}{2}\)可以得到Haar小波。
在Daubechies小波的构造中将要用到这个定理。