小波稀疏性与非线性逼近

形式陈述

只允许保存少量系数时，应保存完整的低分辨率，还是保留最重要的局部细节？本页先假定函数已经知道，研究无噪声逼近；统计观测会在最后另行接上。

令实函数 $f\in L^2[0,1]$ 具有区间Haar展开

f=c\phi_{0,0}+\sum_{j\ge0}\sum_{k=0}^{2^j-1}\beta_{j,k}\psi_{j,k},\qquad c=\int_0^1f,\quad\beta_{j,k}=\int_0^1f\psi_{j,k}.

始终保留尺度系数 $c$ 。给定整数 $m\ge1$ ，允许另外保留至多 $m$ 个细节函数，位置和系数都可以选择。最佳 $m$ 项平方误差定义为

e_m(f)^2=\inf_{\substack{|S|\le m\\(b_{j,k})_{(j,k)\in S}}} \left\|f-c\phi_{0,0}-\sum_{(j,k)\in S}b_{j,k}\psi_{j,k}\right\|_2^2.

将全部细节绝对值递减排列为 $a_1\ge a_2\ge\cdots\ge0$ ；有限非零序列后面补零。因细节平方可和，任意正阈值以上只有有限项，可以作这样的排列。并列时按层数、位置的字典序选取，不影响误差。正交性给精确答案

e_m(f)^2=\sum_{\ell>m}a_\ell^2.\tag{1}

证明分两步。固定 $S$ 时，误差为 $\sum_{(j,k)\in S}|b_{j,k}-\beta_{j,k}|^2+\sum_{(j,k)\notin S}|\beta_{j,k}|^2$ ，故已选位置的最优系数就是原系数。然后若保留较小系数却删去较大系数，交换两者不会增加误差，所以应保留最大的 $m$ 项。无限展开的式子由Parseval与非负级数取极限得到。

定义细节的超水平计数

N(\lambda)=\#\{(j,k):|\beta_{j,k}|>\lambda\}.

若某个 $0<p<2$ 与 $A\ge0$ 满足 $N(\lambda)\le(A/\lambda)^p$ 对每个 $\lambda>0$ 成立，这就是计数测度上的弱 $\ell^p$控制。令阈值从下方趋近 $a_\ell$ ，便有 $a_\ell\le A\ell^{-1/p}$ 。用递减函数的积分比较，式(1)给

e_m(f)^2\le A^2\sum_{\ell>m}\ell^{-2/p} \le\frac{p}{2-p}A^2m^{1-2/p}.\tag{2}

这里控制的是平方误差；误差范数本身要再开平方。 $p<2$ 使尾部积分收敛，不能把 $p=2$ 直接代入。 $A=0$ 时全部细节为零，结论也成立。

直觉

预先选一个固定低分辨率空间，意味着每个位置都得到同样多的描述预算。最佳 $m$ 项逼近允许预算跟着函数走：平坦区域几乎不存细节，变化附近存得更多。最终向量仍是基函数的线性组合，但从输入函数到保留集合的映射依赖输入，因此称为非线性逼近。

稀疏不必意味着大部分系数精确为零。式(2)允许无穷多个非零系数，只要求“大系数的数量”增长受到控制。少量大系数加许多很小系数，也可以让截断尾部很小。

例子与边界

一个不在二进节点上的跳跃

取 $f(x)=\mathbf1_{[1/3,1]}(x)$ ，端点取值不影响 $L^2$ 。尺度系数为 $c=2/3$ 。每层至多一个小波支撑跨过跳点，其他细节因函数在支撑上恒定而为零。

在跨跳点的区间中，跳点的相对位置交替为 $1/3$ 和 $2/3$ ，所以左右半区积分之差的绝对值总是该区间长度的 $1/3$ 。因此每层唯一非零细节的幅度为

|\beta_j|=\frac13\cdot2^{-j/2},\qquad j=0,1,\ldots.

尺度能量为 $4/9$ ，细节能量为 $\sum_j2^{-j}/9=2/9$ ，总和 $2/3$ 正好是 $\int f^2$ 。细节幅度已经按层递减，保留前 $m$ 项得到

e_m(f)^2=\frac19\sum_{j=m}^\infty2^{-j}=\frac29\cdot2^{-m}.\tag{3}

比如保留三个细节和一个尺度系数，平方误差为 $1/36$ 。其支撑位置也要存储，不能把“只存四个实数”当作完整压缩格式。

完整的 $V_J$ 分辨率空间有 $2^J$ 个基方向，而这条函数在其中只有一个尺度和 $J$ 个非零细节；其投影误差同样是 $(2/9)2^{-J}$ 。对这条特定函数，保留稀疏位置可节约大量零系数。它并没有声称对所有函数都能把 $2^J$ 个方向压成 $J+1$ 个数而保持同样误差。

光滑函数为何有小的细尺度系数

设 $0<s\le1$ 且 $|f(x)-f(y)|\le L|x-y|^s$ 。令一个支撑区间长度为 $h=2^{-j}$ 、左端为 $a$ 。左右半区配对积分给

\beta_{j,k}=2^{j/2}\int_a^{a+h/2}[f(t)-f(t+h/2)]dt,

从而

|\beta_{j,k}|\le L2^{-s-1}2^{-j(s+1/2)}.\tag{4}

记 $C=L2^{-s-1}$ 。每层有 $2^j$ 个系数，删去 $j\ge J$ 的全部细节，平方误差至多

\sum_{j\ge J}2^j C^2 2^{-2j(s+1/2)} =\frac{C^2}{1-2^{-2s}}2^{-2Js}.\tag{5}

同样的计数还能接到式(2)。设 $p=1/(s+1/2)$ ；当 $0<\lambda\le C$ 时，只有 $2^j<(C/\lambda)^p$ 的层可能有系数超过阈值，几何级数给 $N(\lambda)\le2(C/\lambda)^p$ 。 $\lambda>C$ 时没有超过项。因此可取 $A=2^{1/p}C$ ，得到 $e_m^2=O(m^{-2s})$ 。对于处处同等光滑的函数类，这与完整分辨率的阶相同；非线性表示的突出收益来自局部不均匀的结构。

系数衰减不是无条件的光滑性证书

函数 $f=\mathbf1_{[1/2,1]}$ 只有尺度系数和一个粗细节，却有真实跳跃。它的高层Haar系数全部为零，当然满足任何正指数的细层衰减界，但它不连续。因此式(4)是当前Haar基下由Hölder光滑性推出系数界的充分方向，反向不能照抄。

一般Besov空间的小波刻画会规定小波的正则性、消失矩、指数范围和区间边界处理。只凭Haar例子不能宣布所有这些函数空间都被刻画，也不能将本页的稀疏类与弱导数定义的Sobolev空间等同。跳跃函数不在一维 $H^1$ 中，却可以极其Haar稀疏，正好显示两个描述不同。

推论与应用

从无噪声预算转向统计误差

在正态系数模型中，若一个包含 $m$ 个细节的集合 $S$ 在看到噪声以前固定，并对其保留原观测、其余置零，则总细节风险精确为

m\tau^2+\sum_{(j,k)\notin S}\beta_{j,k}^2.

第一项是留下的噪声，第二项是丢掉的信号。无噪声逼近只计算第二项；若根据含噪系数大小选择 $S$ ，选择和噪声相关，不能继续不加证明地把第一项写成 $m\tau^2$ 。阈值风险与oracle比较正是为这个未知位置问题提供可执行的统计规则。

在相同能量的两个向量 $(1,0,\ldots,0)$ 和 $(1/\sqrt d,\ldots,1/\sqrt d)$ 中，前者一项即可精确重构，后者保留 $m$ 项的平方误差为 $1-m/d$ 。单看 $L^2$ 范数都等于一，无法区分这种可压缩性；需要查看排序尾部或超水平计数。

自测一。 若 $a_\ell=A/\ell$ ，属于本页 $p=1$ 的弱序列类。式(2)给 $e_m^2\le A^2/m$ ，不是 $A^2/m^2$ 。范数误差界为 $A/\sqrt m$ 。

自测二。 将跳点从 $1/3$ 移到 $1/2$ ，为什么尾误差突然在一个细节后为零？因为新跳点与最粗二进分割对齐；表示的稀疏程度依赖基与位置，不是只由“有一个跳跃”决定。

参考资料

Iain M. Johnstone，Gaussian Estimation: Sequence and Wavelet Models，2019年稿，§§9.1–9.2，pp.253–258，式(9.1)、(9.9)–(9.16)与Proposition 9.1：最佳坐标投影、排序系数与弱 $\ell^p$ ；第7章，Haar表示及平移敏感性。本文的 $1/3$ 跳点、Hölder半区配对和全部常数均直接计算。
David L. Donoho, Iain M. Johnstone, Gérard Kerkyacharian and Dominique Picard，Wavelet Shrinkage: Asymptopia?，Journal of the Royal Statistical Society B 57(2)，1995，§3（PDF pp.8–13）：空间非均匀性、函数类与小波估计。其更广统计结论具有小波及函数类条件，不能仅由本页Haar计算获得。

形式陈述 ​

一个不在二进节点上的跳跃 ​

光滑函数为何有小的细尺度系数 ​

系数衰减不是无条件的光滑性证书 ​

从无噪声预算转向统计误差 ​

反向链接

形式陈述

一个不在二进节点上的跳跃

光滑函数为何有小的细尺度系数

系数衰减不是无条件的光滑性证书

从无噪声预算转向统计误差