動機
傅立葉(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 等價類或係數。