Daubechies小波

发表于 分类于 ，

前言

目前我们提到过的小波大致有Haar小波，Shannon小波与线性样条小波。它们都有其各自的缺陷，在之前也有提到过Haar小波不连续，Shannon小波与线性样条小波没有紧支撑。Daubechies发明了一系列以她的名字命名的小波系，成为了后来人们的更好选择。我们就将构造任意光滑的正交小波基函数。

小波的正则性和消失矩

正则性就是一种对函数连续性的度量。常见的刻划方式有例如

  1. 函数的可导次数

  2. 函数的局部/全局Lipschitz系数

  3. 频域中刻划：

    \[ \int_{\mathbb{R}} \frac{|\hat{f}(\lambda)|}{1+|\lambda|^\alpha} <\infty \]

等等。正则性高，则小波的稳定性好，不会出现大量近似计算的不稳定情况。

消失矩

如果 \[ \int_\mathbb{R}x^n\psi(x)dx=0,n=0,1,\cdots,m-1,\int_\mathbb{R}x^m\psi(x)dx\ne 0 \] 则称\(\psi\)具有m阶消失矩。

可见若小波函数具有高消失矩，则会突出显示信号中的高频部分。

\(Thm\) 设\(\psi\)为一小波，如果\(H(\lambda)=\frac{1}{2}\sum_{k\in\mathbb{Z}}h_ke^{-ik\lambda}\)在\(\lambda=0\)具有\(m-1\)阶连续导数，则下面性质等价：

  1. \(|\psi|\)具有m阶消失矩
  2. \((\hat{\psi})^{(n)}(0)=0,n=0,1,\cdots,m-1\)
  3. \(H^{(n)}(\pi)=0,n=0,1,\cdots,m-1\)
  4. \(\sum_{k\in\mathbb{Z}}(-1)^kk^nh_k=0,n=0,1,\cdots,m-1\)

注意到 \[ \hat{\psi}(\lambda)=G(\frac{\lambda}{2})\hat{\phi}(\frac{\lambda}{2})=-e^{-i\lambda/2}\overline{H(\frac{\lambda+2\pi}{2})}\hat{\phi}(\frac{\lambda}{2}) \] 结论都是一些简单的数学变形。

一些关于消失矩的结论

\(Thm\) 设小波具有m阶消失矩，其尺度函数为\(\phi\)，\(f\in L^2(\mathbb{R})\)具有任意阶导数，则对于任意的正整数\(j\)有 \[ \Vert f-\sum_{k\in Z}\langle f,\phi_{j,k}\rangle \phi_{j,k}\Vert\le 2^{-jm}\Vert f^{(m)}\Vert \] 这个结论告诉我们当小波具有较高的消失矩的时候，用小波函数生成的级数逼近光滑函数能够取得良好的效果。

消失矩与正则性是如何联系的呢，这我们有如下定理

\(Thm\) 如果\(\psi_{j,k}(x)=2^{\frac{j}{2}}\psi(2^jx-k)\)是\(L^2(\mathbb{R})\)上的标准正交基，且\(|\psi(x)|\le C(1+|x|)^{-\alpha}\),\(\alpha >m+1,\psi \in C^m\)且当\(l\le m,\psi^l\)有界，则： \[ \int_{R}x^l\psi(x)dx=0,l=0,1,\cdots,m \]

Daubechies小波的构造

上一章说到，若要双尺度系数生成正交小波，其生成多项式需要满足条件

  1. \(P(1)=1\)
  2. \(|P(z)|^2+|P(-z)|^2=1,|z|=1\)
  3. \(|P(e^{it})|>0,|t|<\pi/2\)

这第二个条件最难处理，恰恰对应的就是小波函数的正交性。正交性的一个必要条件是 \[ \sum h_k\overline{h_{k+2n}}=2\delta_{0,n} \] （从这个式子可以看出，若h紧支，如\(h_0,\cdots,h_N\ne 0\)，则必有N为奇数）

然而，可惜的是这个条件并不能作为正交性的一个充分条件，否则我们就可以之间用此条件联立条件1，再验证条件3得到一个解了。我们希望的就是添加一些补充的条件，使得这样的方程解出来必然满足正交性。Daubechies引入消失矩的条件，构造了一大类具有不同消失矩和紧支集的正交小波。

例：\(N=3\)

有正交性必要条件 \[ \begin{cases} h_0^2+h_1^2+h_2^2+h_3^2=2\\ h_0h_2+h_1h_3=0 \end{cases} \] 条件1 \[ h_0+h_1+h_2+h_3=2 \] 消失矩 \[ \begin{cases} h_0-h_1+h_2-h_3=0\\ h_1-2h_2+3h_3=0\\ h_1-4h_2+9h_3\ne 0 \end{cases} \] 求解可得 \[ \{\frac{1+\sqrt{3}}{4},\frac{3+\sqrt{3}}{4},\frac{3-\sqrt{3}}{4},\frac{1-\sqrt{3}}{4}\} \]

\[ \{\frac{1-\sqrt{3}}{4},\frac{3-\sqrt{3}}{4},\frac{3+\sqrt{3}}{4},\frac{1+\sqrt{3}}{4}\} \]

若去掉消失矩条件则另有解 \[ \{1,0,0,1\} \] 不满足正交小波条件。

构造方法

设\(h=\{h_0,\cdots,h_L\}\)满足

  1. \(\sum h_k\overline{h_{k+2n}}=2\delta_{0,n}\)

  2. \(\sum h_k=2\)

  3. 存在正整数N使得 \[ H(\lambda)=(\frac{1+e^{-i\lambda}}{2})^N Q_N(e^{-i\lambda}) \] 其中\(Q_N(z)\)为\(L-N\)次实系数多项式且满足 \[ Q_N(-1)\ne 0,\sup_{|z|\le 1}|Q_N(e^{-i\lambda})|<2^{N-1} \] 则双尺度方程迭代可解。在条件\(\hat{\phi}(0)=\frac{1}{\sqrt{2\pi}}\)下，其解连续唯一且是具有紧支集的正交尺度函数。

\(Lemma\) （Riesz引理）

设A是一个实系数余弦多项式 \[ A(\lambda)=\sum_{k=0}^N a_k\cos k\lambda \] 其中，\(a_N\ne 0\)，满足对任意的\(\lambda\in \mathbb{R}\)有\(A(\lambda)\ge0\)。则存在\(N\)次实系数代数多项式 \[ B(z)=\sum_{k=0}^N b_k z^k \] 满足\(|B(e^{i\lambda})|^2=A(\lambda)\)，且\(B(1)>0\)。

\(Lemma\) 形如\(H(\lambda)=(\frac{1+e^{-i\lambda}}{2})^N Q_N(e^{-i\lambda})\)的实系数三角多项式满足 \[ |H(\lambda)|^2+|H(\lambda+\pi)|^2=1 \] 的充要条件是 \[ |Q_N(e^{i\lambda})|^2=P\left(\sin^2\frac{\lambda}{2}\right) \] 其中多项式P满足 \[ \begin{aligned} P(y)=P_N(y)+y^NR\left(\frac{1}{2}-y\right)\\ P_N(y)=\sum_{k=0}^{N-1}\frac{(N+k-1)!}{(N-1)!k!}y^k \end{aligned} \] \(R(y)\)是一个可选的奇多项式，使得\(P(y)\ge0,\forall y\in [0,1]\)。

主要步骤

  1. 确定多项式 \[ P_N(y)=\sum_{k=0}^{N-1}\frac{(N+k-1)!}{(N-1)!k!}y^k \]

  2. 利用 \[ |Q_N(e^{i\lambda})|^2=P\left(\sin^2\frac{\lambda}{2}\right) \] 解出\(Q_N(z)\)。

  3. 利用 \[ H(\lambda)=(\frac{1+e^{-i\lambda}}{2})^N Q_N(e^{-i\lambda}) \] 求出\(\{h_k\}_{k=0}^{2N-1}\)

  4. 求出双尺度方程的迭代解\(\phi\)和正交小波\(\psi\)

例子

\(D_4\)小波：取\(N=2\)则 \[ P_2(y)=1+2y \] 假设 \[ Q_2(e^{i\lambda})=q_0+q_1e^{i\lambda} \] 则 \[ |Q_2(e^{i\lambda})|^2=(q_0+q_1)^2-4q_0q_1\sin^2\frac{\lambda}{2}=P\left(\sin^2\frac{\lambda}{2}\right) \] 于是 \[ q_0=\frac{1+\sqrt{3}}{2},q_1=\frac{1-\sqrt{3}}{2}~or~q_0=\frac{1-\sqrt{3}}{2},q_1=\frac{1+\sqrt{3}}{2} \] 对于前者 \[ \begin{aligned} H(\lambda)&=\left(\frac{1+e^{-i\lambda}}{2}\right)^2\left(\frac{1+\sqrt{3}}{2}+\frac{1-\sqrt{3}}{2}e^{-i\lambda}\right)\\ &=\frac{1+\sqrt{3}}{8}+\frac{3+\sqrt{3}}{8}e^{-i\lambda}+\frac{3-\sqrt{3}}{8}e^{-2i\lambda}+\frac{1-\sqrt{3}}{8}e^{-3i\lambda} \end{aligned} \] 对应解 \[ \left\{\frac{1+\sqrt{3}}{4},\frac{3+\sqrt{3}}{4},\frac{3-\sqrt{3}}{4},\frac{1-\sqrt{3}}{4}\right\} \] 类似地有后者对应解\(\{\frac{1-\sqrt{3}}{4},\frac{3-\sqrt{3}}{4},\frac{3+\sqrt{3}}{4},\frac{1+\sqrt{3}}{4}\}\)

Daubechies小波的性质

紧支性

由迭代构造 \[ \phi_n(x)=\sum h_k\phi_{n-1}(2x-k) \] \(h_0,\cdots,h_{2N-1}\)外均为零，有尺度函数支集\([0,2N-1]\)，小波函数支集\([1-N,N]\)

消失矩

容易验证 \[ \int_{\mathbb{R}} x^k\psi_N(t)dt= \begin{cases} 0,&k=0,\cdots,N-1\\ -\frac{N!}{4^N}Q_N(-1),&k=N \end{cases} \]

Daubechies小波的计算

除了Haar小波，我们不能给出其它Daubechies小波函数的初等函数表示形式，但有算法可以求出小波函数和尺度函数在每一个有理点的值。

  1. 计算尺度函数和小波函数在整数节点的值：

    注意到只有\(\phi(k)=0,k\le 0,k\ge 2N-1\)，则只要计算\(\phi(j),j=1,\cdots,2N-2\)则 \[ \psi(j)=\sum_{k=0}^{2N-1} h_k\psi(2j-k)=\sum_{k=2j-2N+1}^{2j} h_{2j-k}\psi(k) \] 可得一个奇异的线性方程组

    结合条件 \[ \int \phi(x)dx=\sum_j\phi(j) \] 从而使用尺度函数的标准化条件联立可得。

  2. 计算\(\phi(\frac{n}{2^j})\)与\(\psi(\frac{n}{2^j})\)的值

    这由MRA尺度函数构造是显然的。