样条子空间上的随机采样

李慧敏， 李水艳

(河海大学 理学院，江苏 南京 211100)

1 引言

利用离散序列重构连续信号(函数)是信号处理的重要任务之一.Shannon-Whittaker采样定理[1]成功地解决了带限函数空间中的采样重构问题.在实际应用中,用到的信号空间往往是非带限函数空间,如平移不变空间[2-5].样条子空间作为特殊的平移不变空间,在计算机图形学[6]、计算机辅助设计[7]、信号和图像处理[8]等领域起着至关重要的作用.对于样条子空间中的函数,如何确定合适的采样点使函数能够唯一地重构出来,是信号处理中的一个关键问题.孙文昌等人在样条子空间上的局部采样[9]中给出了一个选取采样点的方法,但该方法比较难验证.为了更好地解决这一问题,本文利用随机采样的方法来研究样条子空间上的函数重构问题.

考虑由m阶样条φm生成的样条子空间

中信号f∈Vm的随机采样重构问题,其中φm=χ[0,1]*…*χ[0,1](m个卷积),χ[0,1]是有限区间[0,1]上的特征函数,h为尺度参数.首先给出随机采样集E∶={xi∶1≤i≤n}的刻画条件,使得信号f能唯一地重构出来,并且得到重构概率,然后运用最小二乘法建立重构模型和算法，最后通过数值实验对模型和算法进行验证.

2 随机采样的概率估计

对于有界区间Ω=[0,1]上的随机采样数据密度水平的概率估计,将有界区域Ω=[0,1]均匀地分成N=1/h个小区间Ωl=[hl,h(l+1)],其中0≤l≤N-1.

引理1 设随机采样集E∶={xi∶1≤i≤n}是一个独立随机变量序列,每个变量均匀分布在Ω=[0,1]上.对于每个子区间Ωl,使用#(E∩Ωl)表示E∩Ωl上的采样点数,则

证明对于任意的子区间Ωl⊂Ω,令

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

是n个独立实验中“成功”的概率,累积分布函数表示为F(0;n,p)∶=P{#(E∩Ωl)≤0}.通过Chernoff二项分布不等式[10],有

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

结合基本概率公式,可得

特别地,当n=N1+ε时,上式变为

3 样条子空间函数可以唯一重构的条件刻画

若Vm中的信号f能在高概率下唯一地重构出来，即存在唯一的序列{a(α)∶α∈I},使得

(1)

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

定理1 假设生成子φm具有一定的光滑性,随机采样集E∶={xi∶1≤i≤n}是一个独立随机变量序列,每个变量均匀分布在Ω=[0,1]上，则仅用有限个采样值{f(xi)∶1≤xi≤n}就可以唯一地重构信号f∈Vm,并且得到重构概率为

其中,采样点数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 模型与算法

通过求解

(2)

得到最优解a*，进而有逼近解

将(2)式写成矩阵的形式,得到优化模型

(3)

其中Ai,α=φm(xi/h-α),I=[-m,N-1]，F=[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:估计采样点之间的距离hh≈min|xi-xj|i≠j

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

由定理1,可以得到矩阵A的列向量是线性无关的,所以最小二乘法的解是唯一的,信号f能够被唯一地重构出来.

5 数值实验

为了验证算法的有效性,利用MATLAB进行数值实验,分别考虑无噪音的信号的随机采样重构问题与有噪音的信号的随机采样重构问题.

第一个实验,设f1(x)=sin(5πx)2为未知连续信号,在[0,1]上进行随机采样E∶={xi∶1≤i≤20},得到采样值{f1(xi)∶1≤i≤20},取尺度参数h=1/10,三次B-样条[12]

作为样条子空间的基.

图1 无噪音的信号重构 图2 有噪音的信号重构

第二个实验,设f2(x)=cos(3πx)2为未知连续信号,在[0,1]上进行随机采样E∶={xi∶1≤i≤20},得到采样值yi=f2(xi)+ηj,其中ηj服从正态分布N(0,0.02),参数和空间的选取与第一个实验相同.

上述数值结果表明,该算法能够较好地解决样条子空间上有无噪音的信号采样重构问题.