樣條子空間上的隨機(jī)采樣

李慧敏， 李水艷

(河海大學(xué) 理學(xué)院，江蘇 南京 211100)

1 引言

利用離散序列重構(gòu)連續(xù)信號(hào)(函數(shù))是信號(hào)處理的重要任務(wù)之一.Shannon-Whittaker采樣定理[1]成功地解決了帶限函數(shù)空間中的采樣重構(gòu)問(wèn)題.在實(shí)際應(yīng)用中,用到的信號(hào)空間往往是非帶限函數(shù)空間,如平移不變空間[2-5].樣條子空間作為特殊的平移不變空間,在計(jì)算機(jī)圖形學(xué)[6]、計(jì)算機(jī)輔助設(shè)計(jì)[7]、信號(hào)和圖像處理[8]等領(lǐng)域起著至關(guān)重要的作用.對(duì)于樣條子空間中的函數(shù),如何確定合適的采樣點(diǎn)使函數(shù)能夠唯一地重構(gòu)出來(lái),是信號(hào)處理中的一個(gè)關(guān)鍵問(wèn)題.孫文昌等人在樣條子空間上的局部采樣[9]中給出了一個(gè)選取采樣點(diǎn)的方法,但該方法比較難驗(yàn)證.為了更好地解決這一問(wèn)題,本文利用隨機(jī)采樣的方法來(lái)研究樣條子空間上的函數(shù)重構(gòu)問(wèn)題.

考慮由m階樣條φm生成的樣條子空間

中信號(hào)f∈Vm的隨機(jī)采樣重構(gòu)問(wèn)題,其中φm=χ[0,1]*…*χ[0,1](m個(gè)卷積),χ[0,1]是有限區(qū)間[0,1]上的特征函數(shù),h為尺度參數(shù).首先給出隨機(jī)采樣集E∶={xi∶1≤i≤n}的刻畫條件,使得信號(hào)f能唯一地重構(gòu)出來(lái),并且得到重構(gòu)概率,然后運(yùn)用最小二乘法建立重構(gòu)模型和算法，最后通過(guò)數(shù)值實(shí)驗(yàn)對(duì)模型和算法進(jìn)行驗(yàn)證.

2 隨機(jī)采樣的概率估計(jì)

對(duì)于有界區(qū)間Ω=[0,1]上的隨機(jī)采樣數(shù)據(jù)密度水平的概率估計(jì),將有界區(qū)域Ω=[0,1]均勻地分成N=1/h個(gè)小區(qū)間Ωl=[hl,h(l+1)],其中0≤l≤N-1.

引理1 設(shè)隨機(jī)采樣集E∶={xi∶1≤i≤n}是一個(gè)獨(dú)立隨機(jī)變量序列,每個(gè)變量均勻分布在Ω=[0,1]上.對(duì)于每個(gè)子區(qū)間Ωl,使用#(E∩Ωl)表示E∩Ωl上的采樣點(diǎn)數(shù),則

證明對(duì)于任意的子區(qū)間Ωl?Ω,令

p∶=P(xi∈Ωl)=1/N

是n個(gè)獨(dú)立實(shí)驗(yàn)中“成功”的概率,累積分布函數(shù)表示為F(0;n,p)∶=P{#(E∩Ωl)≤0}.通過(guò)Chernoff二項(xiàng)分布不等式[10],有

令#(E∩Ωl)≤0為事件Al,那么

結(jié)合基本概率公式,可得

特別地,當(dāng)n=N1+ε時(shí),上式變?yōu)?/p>

3 樣條子空間函數(shù)可以唯一重構(gòu)的條件刻畫

若Vm中的信號(hào)f能在高概率下唯一地重構(gòu)出來(lái)，即存在唯一的序列{a(α)∶α∈I},使得

(1)

其中h=1/N,I={α∈∶suppφm∩Ω≠0}=[-m,N-1].

定理1 假設(shè)生成子φm具有一定的光滑性,隨機(jī)采樣集E∶={xi∶1≤i≤n}是一個(gè)獨(dú)立隨機(jī)變量序列,每個(gè)變量均勻分布在Ω=[0,1]上，則僅用有限個(gè)采樣值{f(xi)∶1≤xi≤n}就可以唯一地重構(gòu)信號(hào)f∈Vm,并且得到重構(gòu)概率為

其中,采樣點(diǎn)數(shù)n滿足n≥(N+m).

證明等式(1)的矩陣形式表示為

F=Aa

其中

F=[f(x1),f(x2),…,f(xn)]T

a=[a(-m),a(-m+1),…,a(N-1)]T

A=[φm(xi-α)]1≤i≤n,-m≤α≤N-1

4 模型與算法

通過(guò)求解

(2)

得到最優(yōu)解a*，進(jìn)而有逼近解

將(2)式寫成矩陣的形式,得到優(yōu)化模型

(3)

其中Ai,α=φm(xi/h-α),I=[-m,N-1]，F(xiàn)=[f(x1),f(x2),…,f(xn)]T.

(4)

其中Ai,α=φm(xi/h-α),I=[-m,N-1]，Y=[y(x1),y(x2),…,y(xn)]T,基于此模型,給出如下算法:

步驟1:估計(jì)采樣點(diǎn)之間的距離hh≈min|xi-xj|i≠j

步驟2:生成矩陣AAi,α=φm(xi/h-α)

由定理1,可以得到矩陣A的列向量是線性無(wú)關(guān)的,所以最小二乘法的解是唯一的,信號(hào)f能夠被唯一地重構(gòu)出來(lái).

5 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證算法的有效性,利用MATLAB進(jìn)行數(shù)值實(shí)驗(yàn),分別考慮無(wú)噪音的信號(hào)的隨機(jī)采樣重構(gòu)問(wèn)題與有噪音的信號(hào)的隨機(jī)采樣重構(gòu)問(wèn)題.

第一個(gè)實(shí)驗(yàn),設(shè)f1(x)=sin(5πx)2為未知連續(xù)信號(hào),在[0,1]上進(jìn)行隨機(jī)采樣E∶={xi∶1≤i≤20},得到采樣值{f1(xi)∶1≤i≤20},取尺度參數(shù)h=1/10,三次B-樣條[12]

作為樣條子空間的基.

圖1 無(wú)噪音的信號(hào)重構(gòu) 圖2 有噪音的信號(hào)重構(gòu)

第二個(gè)實(shí)驗(yàn),設(shè)f2(x)=cos(3πx)2為未知連續(xù)信號(hào),在[0,1]上進(jìn)行隨機(jī)采樣E∶={xi∶1≤i≤20},得到采樣值yi=f2(xi)+ηj,其中ηj服從正態(tài)分布N(0,0.02),參數(shù)和空間的選取與第一個(gè)實(shí)驗(yàn)相同.

上述數(shù)值結(jié)果表明,該算法能夠較好地解決樣條子空間上有無(wú)噪音的信號(hào)采樣重構(gòu)問(wèn)題.