动机
傅里叶(Fourier)系数将函数与贯穿整个周期的振荡比较。有时变化发生的位置和频率同样重要。小波系数在特定位置和尺度上比较函数的行为。Haar 系统是最容易精确计算的例子:每个小波在一个二进区间的左半边为正、右半边为负。
这一构造不只是一些有用函数的集合。我们先证明每个有限层级都描述了全部对应的二进阶梯函数,再说明越来越细的二进阶梯可以逼近每个 L2 函数。由此得到完备标准正交基及能量恒等式。结论使用 L2 范数,不能悄悄加强成恢复每个选定的点值。
定义
在 [0,1] 上使用 Lebesgue 测度。L2([0,1]) 中的函数是按几乎处处相等划分的等价类。取对第一变量线性的内积:
⟨f,g⟩=∫01f(x)g(x)dx,∥f∥22=⟨f,f⟩.
下文区间左闭右开。端点 1 的处理只影响零测集,不影响任何 L2 结论。
对于整数 j≥0 和 0≤k<2j,令
Ij,k=[k2−j,(k+1)2−j),并以 Ij,kL、Ij,kR 表示其左半和右半。定义尺度函数 ϕ=1[0,1] 和 Haar 小波
ψj,k=2j/2(1Ij,kL−1Ij,kR).小波在 Ij,k 以外为零,两半区间上取相反常数,积分为零。因子 2j/2 使其范数平方为一:区间长度为 2−j。
快速检查
(不用乘积公式积分,计算 ⟨ψ0,0,ψ1,1⟩。)
先找出 ψ1,1 的支撑在 [0,1) 中的位置。
解答 · 答案
ψ1,1 的支撑是 [1/2,1),即 I0,0 的右半,而 ψ0,0 在那里恒等于 −1。因此 ⟨ψ0,0,ψ1,1⟩=−∫1/21ψ1,1=0,因为每个 Haar 小波的积分都是零。这正是下文证明所用的嵌套论证。
f∈L2 的小波系数为
cj,k=⟨f,ψj,k⟩=2j/2(∫Ij,kLf(x)dx−∫Ij,kRf(x)dx).
这些积分有限:有限测度区间上的 Cauchy–Schwarz 不等式给出 ∥f∥1≤∥f∥2。系数是两半区间积分之差乘以尺度因子,一般并非两个平均值未经缩放的差。只要两个积分相同,系数便为零,即使 f 在两半上都不恒定。
令 DJ 为在每个 IJ,k(0≤k<2J)上几乎处处为常数的函数空间。区间示性函数构成其一组基,因此维数为 2J。对 J≥0 定义
PJf=⟨f,ϕ⟩ϕ+j=0∑J−1k=0∑2j−1⟨f,ψj,k⟩ψj,k,当 J=0 时求和为空。端点约定不改变它作为 L2 元素的含义。
定理:正交性与完备性
对每个 J≥0,函数族
{ϕ}∪{ψj,k:0≤j<J, 0≤k<2j}是 DJ 的一组标准正交基。因此 PJf 是 f 在 DJ 上的正交投影,并在每个 IJ,k 上几乎处处等于该区间的平均值
2J∫IJ,kf(x)dx.
定理 3.1.4
(Haar 完备性与 Parseval 恒等式)
可数函数族 {ϕ}∪{ψj,k}j≥0,0≤k<2j 是 L2([0,1]) 的标准正交基。具体地,对每个 f∈L2,
∥f−PJf∥2⟶0,∥f∥22=∣⟨f,ϕ⟩∣2+j=0∑∞k=0∑2j−1∣⟨f,ψj,k⟩∣2.按层级求和时,Haar 级数在 L2 中收敛到 f。按基函数的任意枚举顺序求和,级数也在 L2 中收敛。这些结论确定的是等价类,而不是每个点上的值。
Haar 系统为何完备
每个 ψj,k 的范数为一且平均值为零,所以与 ϕ 正交。同一层级的不同区间互不相交。对于不同层级,两个二进区间要么不相交,要么较小者包含于较大者。在后者情形,较细区间完全落在较粗区间的一半中;粗小波在那里为常数,而细小波的积分为零,因此内积为零。若选用另一代表元而令端点重叠,重叠也只是零测集。
当 j<J,每个 Haar 函数在每个第 J 层小区间上为常数,因此属于 DJ。该族成员数为
1+j=0∑J−12j=2J=dimDJ.标准正交组线性无关,所以它是 DJ 的基。投影到这组基便得到 PJ 的公式。也可以直接观察:区间平均值组成的函数属于 DJ,而残差在每个小区间上的积分为零,故与 DJ 中所有函数正交。正交投影的唯一性给出平均值公式。
先设 g 在 [0,1] 上连续。一致连续性给出连续模 ωg(δ)=∣x−y∣≤δsup∣g(x)−g(y)∣,当 δ→0 时趋零。在第 J 层每个小区间上,g(x) 与该区间平均值之差至多为 ωg(2−J)。因此
∥g−PJg∥2≤∥g−PJg∥∞≤ωg(2−J)⟶0.这里 ∥⋅∥∞ 是本性上确界,第一个不等式利用整个区间的测度为一。小区间平均值的代表元在端点取什么值,都不改变估计。
连续函数在 L2([0,1]) 中稠密。一种证明方法是先用简单函数逼近 L2 函数,再利用 Lebesgue 测度的正则性,用连续函数在 L2 中逼近可测集合的示性函数。给定 f∈L2 和 ε>0,选取连续 g 使 ∥f−g∥2<ε。正交投影的算子范数至多为一,因为勾股恒等式给出 ∥PJv∥2≤∥v∥2。利用分解 f−PJf=(f−g)−PJ(f−g)+(g−PJg) 及三角不等式,得到
∥f−PJf∥2≤2∥f−g∥2+∥g−PJg∥2.先选 g,再取充分大的 J,便得到收敛。有限正交恒等式
∥f∥22=∥f−PJf∥22+∣⟨f,ϕ⟩∣2+j=0∑J−1k∑∣⟨f,ψj,k⟩∣2在 J→∞ 时给出 Parseval 恒等式。它也证明完备性:若函数与每个 Haar 函数正交,则每个 PJf=0,取极限得到 f=0,作为 L2 元素成立。
对任意枚举顺序,第 N 个部分和是到前 N 个函数张成空间的正交投影。任何有限层级最终都会全部出现。一旦第 J−1 层及此前所有基函数出现,该张成空间便包含 DJ;由最佳逼近,残差不超过 ∥f−PJf∥2。之后的张成空间只增大,所以上界对所有更后的部分和仍成立。因为 ∥f−PJf∥2→0,任意枚举都在 L2 中收敛到 f。单凭此论证不能断言任意枚举都逐点收敛。
证明透视
为什么有限层级计数还不是完备性
两个证明用到不同种类的事实。第一个纯粹是计数。二进区间的嵌套性使较粗的小波在较细小波的支撑上为常数,较细小波的均值为零便使内积消失;计数 1+j<J∑2j=2J 再把 DJ 内的标准正交集提升为 DJ 的基。单靠这一半不能得到完备性,因为标准正交族可以遗漏整个方向:删去 ψ0,0 后,余下的族仍然标准正交,而 ψ0,0 与其中每个函数都正交。
分析在第二个证明中才出现。一致连续性给出小区间振幅的界 ωg(2−J),连续函数的稠密性把这个界带到每个 L2 等价类,而 ∥PJv∥2≤∥v∥2 防止逼近误差 f−g 被放大。论证以有限的勾股恒等式闭合:残差趋于零后,有限能量恒等式便成为 Parseval 恒等式;与整个族正交的函数对每个 J 都有 PJf=0,因此在 L2 中为零。
投影公式还给出具体的双尺度能量计算。设 AL,AR 是 f 在 I=Ij,k 两半上的平均值,记 ∣I∣=2−j。它们共同的父区间平均值为 A=(AL+AR)/2,Haar 系数则为
cj,k=2∣I∣(AL−AR).
在两半区间上,Pj+1f 分别取 AL,AR,而 Pjf 取 A。因此在 I 上新增的范数平方为
2∣I∣(∣AL∣2+∣AR∣2)−∣I∣∣A∣2=4∣I∣∣AL−AR∣2=∣cj,k∣2.
这一恒等式对复数平均值也成立。它解释了一个系数的平方所衡量的量:把该小区间分成两个平均值后增加的能量。系数为零说明两个平均值相同,但不说明 f 在任一半区间上恒定。
概念视角算法
用反复求平均和求差计算系数
两尺度恒等式可以由 f 在第 J 层的 2J 个小区间平均值,算出第 J 层以下的全部系数。把相邻小区间配对:Ij,k 内的每一对给出母区间平均值 A=(AL+AR)/2 和系数 cj,k=2−j/2(AL−AR)/2。对母区间平均值重复这一步,直到只剩一个平均值 ⟨f,ϕ⟩。总共只需 2J−1 次配对,因此在 PJf 的小区间平均值描述与 Haar 描述之间转换,运算次数与 2J 成正比。
Lipschitz 条件提供了正则性控制系数的定量例子。假设某个代表元满足 ∣f(x)−f(y)∣≤L∣x−y∣。写 Ij,k=[a,a+ℓ),其中 ℓ=2−j;把左半中的 a+t 与右半中的 a+ℓ/2+t 配对,则
∣cj,k∣≤ℓ−1/2∫0ℓ/2L2ℓdt=4L2−3j/2.
第 j 层有 2j 个系数。将其平方界与 Parseval 恒等式结合,得到
∥f−PJf∥22≤j=J∑∞16L22−2j=12L22−2J.
下例 f(x)=x、L=1 达到等号。这是对 Lipschitz 函数的充分估计,并非对所有系数具有相似衰减的函数的完整刻画。
例题
令 f=1[0,1/2)。常数系数为 ⟨f,ϕ⟩=1/2,第一小波系数为 ⟨f,ψ0,0⟩=1/2。除端点外,每个更细小波都支撑在 f 恒定的区域内,所以其系数为零。因此
f=21ϕ+21ψ0,0在 L2 中,∥f∥22=41+41=21.按左闭右开约定,ψ0,0(1)=0;在 x=1,右边所写代表元取值 1/2,左边示性函数取值零。等式仍然在 L2 中成立,因为单个端点是零测集。把函数视为等价类时,不能忽略这种细节。
令 f(x)=x,其平均值为 1/2。在长度 ℓ=2−j 的第 j 层区间上,直接积分可知左半积分减右半积分为 −ℓ2/4,与区间位置无关。因此
cj,k=−42−3j/2,k=0∑2j−1∣cj,k∣2=162−2j.对所有层级求和得到 j≥0∑2−2j/16=1/12,所以 Parseval 恒等式为 1/3=1/4+1/12,与 ∫01x2dx 一致。舍去第 J 层及之后的能量为
∥f−PJf∥22=j=J∑∞162−2j=122−2J.因此范数误差为 2−J/12。误差平方与范数的幂次不同,开平方不能省略。
设 f 在 I2,1=[1/4,1/2) 左半为 3、右半为 1,其他地方为零。每半长度为 1/8,22/2=2,故
⟨f,ψ2,1⟩=2(83−81)=21.其他系数也可能非零:支撑在较大区间上的小波可能检测到整个支撑偏向其中一侧。基函数的局部性不意味着一个局部特征只有一个非零系数。
反例模式
基无法恢复人为指定的零测集值
令 f 除 f(0)=1 外处处为零。每个 Haar 系数和每个部分和都为零,但所写代表元在零点取值一。这并不矛盾:此函数与零函数代表同一个 L2 元素。基定理确定等价类,而不确定可以在不改变任何积分的情况下修改的点值。
常见错误
如果没有 2j/2,左右半区间示性函数之差的范数平方是 2−j,而不是一。标准正交投影与 Parseval 恒等式要求使用实际给出的归一化函数。同样,系数是与归一化小波的内积,不只是两侧的非正式对比。
定理证明的是 ∥f−PJf∥2→0,允许在零测集上修改代表元。若 f 连续,将最后一个小区间的平均值赋给端点 1,便得到一致收敛的代表元,这是上面连续模估计的结论。原式所写的部分和在 1 却未必如此:对 f(x)=x,所有小波在 1 为零,该处部分和恒为 1/2。相反,对 f=1[0,1/3),包含 1/3 的二进小区间在每一层的平均值均为 1/3 或 2/3,因为 2J/3 的小数部分在这两者之间交替。该小区间上的本性上确界误差为 2/3,因此即使修改端点值也无法一致收敛。一般逐点结论需要另外的条件。
总结
Haar 小波是归一化的局部半区间对比。二进区间的嵌套性证明正交性;有限维计数将每层与阶梯空间对应;二进阶梯函数的稠密性给出 L2 完备性。系数平方将函数能量分配给常数部分与各局部尺度,点值仍需另行讨论。
练习
快速检查
(写出 ψ1,0 在其两个半区间上的值,并验证其平均值及范数平方。)
解答 · 答案
在 [0,1/4) 上 ψ1,0=2,在 [1/4,1/2) 上为 −2,其他地方为零。两半积分相消;范数平方为 2(1/4)+2(1/4)=1。
快速检查
(对 f=1[1/2,1),求非零 Haar 系数并验证 Parseval 恒等式。)
解答 · 答案
常数系数为 1/2,⟨f,ψ0,0⟩=−1/2,所有更细系数均为零。Parseval 给出 ∥f∥22=1/4+1/4=1/2。
快速检查
(对 f(x)=x,求 P1f 在区间两半上的值,并计算 ∥f−P1f∥22。)
解答 · 答案
区间平均值在 [0,1/2) 上为 1/4,在 [1/2,1) 上为 3/4。平移坐标后,每一半贡献 ∫01/2(x−1/4)2dx=1/96,故 ∥f−P1f∥22=1/48,与能量尾和 2−2/12 一致。
快速检查
(假设 f∈L2 与 ϕ 和每个 ψj,k 都正交。证明 f=0 几乎处处成立,并解释为何这不意味着每个代表元处处为零。)
解答 · 答案
每个 PJf 都为零。完备性给出 ∥f∥2=0,因此 f=0 几乎处处成立。但可以修改代表元在一个点上的值,而不改变其 L2 等价类或系数。