两类混合特征信号的超完备稀疏表示方法
孙　蒙，王正明
(国防科学技术大学理学院数学与系统科学系，湖南长沙410073)
  摘　要:　本文提出了基于跳跃字典的超完备稀疏表示方法和基于自适应分割定义域的超完备稀疏表示方法，分
别用于重建带有周期和方波特征的信号和带有周期和冲击特征的信号.实例表明，这两种方法对相应的信号在逼近误差和稀疏性上达到了比直接采用基追踪或小波逼近更好的效果.
关键词:　信号表示；超完备；稀疏表示；跳跃字典；自适应分割；周期信号；方波信号；冲击信号中图分类号:　TP391141  　文献标识码:　A    文章编号:　037222112(2007)0721327206
Overcomplete and Sparse Repre sentation of Two K inds of Signals
with Mixed Feature s
S UN Meng ,W ANG Zheng 2ming
(Department o f Mathematics and System Science ,National Univer sity o f De fense Technology ,Changsha ,Hunan 4100
73,China )
Abstract :　This paper addresses new methods to recreate signals with periodic and rectangular features ,employing J ump Dic 2tionary 2based overcomplete sparse representation method ,and signals with periodic and impulse features ,employing self 2adaptive segmentation 2based overcomplete sparse representation method.As revealed in our trials ,in terms of approximation error and sparsi 2ty ,both of the two methods mentioned above get better prediction results than basis pursuit algorithm and wavelet approximation.
K ey words :　signal representation ;overcomplete ;sparse representation ;jump dictionary ;adaptive segmentation ;periodic sig 2nal ;rectangular signal ;impulse signal
1　引言
  信号的精确稀疏表示是信息压缩和数据传输的关
键技术.小波在处理一维信号的逼近问题中取得了很好的效果，但是，用大尺度的小波系数对信号作的线性逼近等价于它在一个均匀网格上的有限元逼近，逼近误差依赖于函数的均匀正则性[1].也就是说，小波对跳跃点或脉冲的逼近精度是通过牺牲系数的稀疏性来实现的.近年来,D onoho 提出的信号的超完备稀疏表示方法取得了显著的发展[2].常用的信号稀疏表示方法有以逐步选取原子为代表的匹配追踪方法(MP )和以求解大尺度优化问题为代表的基追踪方法(BP ).MP 的贪婪本
质决定了它较差的收敛性，而BP 则在求解时遇到了运算和选取合适参数的困难.本文通过设计跳跃字典，自动识别间断点稀疏表示带有周期和方波特征的信号；对带有周期和冲击信号，利用动态规划，先将定义域自适应地分割成正则性较好的一些区域；然后对每个区域利用超完备基下的基追踪算法进行稀疏表示求解.实验表明，上述两种处理方法对相应的信号无论在逼近误差还是在
稀疏性上都达到了比单纯采用基追踪或动态规划分割后用一组基处理更好的效果.2　超完备稀疏表示技术
211　超完备逼近的思想来源
信号可以在一簇完备正交基下展开，因而可用该正交基的有限个分量表示信号，根据分量的选取方式不同，有线性逼近和非线性逼近.不可否认，这种成熟的方法在以往的理论和技术中都取得了很好的效果；但是，信号都是有自身特征的，不同区域有着不同的特征，仅用一组完备正交基不能达到精确稀疏表示信号的目的.另外，三角函数基不能很好的反映信号的局部特征；小波变换不能足够稀疏地表示信号的突变特征等.因此，利用具有不同特征的多组基组成的冗余字典去稀疏表示信号是很有意义的.212　字典的构造
考虑区间[0,1]上的信号，通过以下完备字典根据信号特征两两组合构造超完备字典:
①余弦字典:
收稿日期:2006206228；修回日期:2007203201基金项目：国家自然科学基金(N o.60572136)
第7期2007年7月
电  子  学  报
ACT A E LECTRONICA SINICA V ol.35　N o.7
July  2007
{cos (2k πx ),k =0,1,…,N}(1)
只要N 足够大，该字典就能精确的表示区间[0,1]上能
量有限的光滑信号.特别的，该字典对于“振荡”类信号具有很好的逼近性能.但是在信号的间断点处，该字典就会出现G ibbs 现象.
②小波字典:
φJ
,k ,k =0,1,…,2
J 0-1
ψj ,k ,j =J 0,…,J ;k =0,1,…,2
j -1
(2)
其中,φ和ψ分别为小波尺度函数和母函数(比如Haar
或Shannon );J 0,j 表示伸缩;k 表示平移，其取值范围由函数的支集含于[0,1]决定;J 是分辨率的上界，它可以根据信号的长度和可以忍受的截断误差决定，一般取J
=log 2N.
当J 足够大时，无论“脉冲”还是“震荡”信号都可以被精确地表示，但是稀疏性会很差.
③跳跃字典
{(x -x 3k )0
+,k =1,…,M}(3)其中(x -x 3
k )0
+
=
0,0<x 3
k
1,
x ≥x 3
k
,x 3
k 为间断点.
(逼近误差小、重建系数的稀疏性好).213　现有基追踪算法的优缺点及改进方向
不妨设选取的超完备字典构成的设计矩阵(基函数在采样点的值构成的矩阵)为D ，待估系数向量为α，信号观测值向量为y .于是基追踪可以描述为以下问题:
m in ‖α‖1subject to y =D
α(4)此处采用了L 1范数度量系数的稀疏性，以下简要介绍一种现有的求解算法[3]:
首先，通过设置参数λ使以上有约束问题转化成无约束的优化问题:
m
in {1
2
‖y -D α‖2+λ‖α‖1}(5)
其次，用αH W (α)α替换‖α‖1，将上式转化为求
解以下优化问题:
m in α
1
2
y -D α2
2+λ
αH W (α)α(6)
其中,W (α)=diag (1/|αi |),H 表示共轭转置；迭代求解
如下:
^α(n +1)=β(D H D +2λW (^α(n )))-1D H y +(1-β)^
α(n )(7)
其中,β为迭代步长,0<β≤1，迭代初值可取^α(0)
=
D H y .迭代的终止条件由‖^α(n +1)-^α(n )‖22/‖^α(n )‖22<δCG 控制(本文取δCG =10
-3
)，这样即可得到优化问题的解^α.在对字典D 进行规范化(‖D ‖2=1)的情况
下,λ的经验值可取λ=σ2log (P )，其中,P 为字典D
的势,σ为噪声的方差.在得到表示系数α的估计^α以
后，可以由^y =D ^α很容易得到重构的信号.
实验表明，超完备稀疏表示的基追踪方法在处理包含两种不同特征的信号时取得了较好的效果.但是，由于参数λ取值为经验值，算法对于正则形态差的信号效果不是很好，有时候区分不出不光滑点，为减小逼近误差就需要牺牲稀疏性为代价.另一方面用L 2范数作为稀疏性度量，有时就会过分保证稀疏性而丧失了逼近的精确性；实际上，误差主要是从正则形态不好的地方产生的.
一个很自然的想法就是“分而治之”，把信号按照自身的特点自适应地分段处理，这样逼近效果肯定会得到改进；另一方面，稀疏性可能会有一些牺牲，即便如此，仍可断言在达到同等精度的条件下，如果所分段数较少采用分段处理比采用增加小波系数的方法需要的系数少得多(归因于超完备字典)，估算如下:
假设采用余弦和小波基组成的超完备字典所用余弦基个数为N ；尺度函数分辨率为J 级，因此父小波基的个数为2J ；于是分段前所用的系数(包含为0的系数)为:2J +N.假设将其分成了M 段，由于每段正则性较好需要较少的小波系数2J 0
，于是分段后所用的系数
(包含0)为:(2J
0+N )M.一般可取,N ≈10,J ≈8,J 0≈4
可以估计当M ≤10时，分段后的系数要少于分段前的系数，这意味着分段数不宜太多.另外，如果分段前的系数比较稀疏，那么分段后各段的系数也应该比较稀疏，于是可以把每段的系数作为矩阵的一行，这个矩阵为稀疏矩阵，便于计算、存储和传输.3　基于自适应分段的超完备稀疏表示
311　基于跳跃字典的超完备稀疏表示方法31111　跳跃点的自动定位方法
对于带有方波特征的周期信号，可以做出如下假
定：跳跃点就是间断点，而在非间断点处信号没有突变.此时本文给出一种快速的判断跳跃点并且利用跳跃点位置信息进行超完备稀疏表示的新方法.
首先对所得到的信号的采样数据{S n }K n =0进行向前差分或向后差分并取绝对值，得到{y n }K n =1，本文取y n =|s n -s n -1|.实际上如果x n 为间断点，那么y n 或者y n +1就会比较大(或者说相对于非间断点的情况相差比较大)，某种程度上来说y n 或者y n +1就是{y n }K n =1中的异常值，选用异常值判别准则[7]来到这样的y n 进而到了对应的自变量值x n ，此时就可以把x n 看成间断点的坐标.“异常值判别准则”的一般描述如下:
对于线性回归模型Y =X β+ε,ε～N (0,σ2
I K ).定
8231  电  子  学  报2007年
义
δ=(I K -H )Y ,H =X (X T X )
-1
X
T
(8)其中I K 为K 阶单位矩阵,
ζt =(1-h t )
-1δ2
t
(9)
其中h t 为H 的第t 个对角元素,δt 为δ的第t 个元素.
当ζi =max t
ζt >α‖δ‖2
时(范数取为向量的L 2范数)，则认为Y i 为异常数据.这里α由式(10)和式(11)
决定:
I (l ,α
)
=(∫
π2
sin
l -2
φd φ)
-1
∫
arcsin 1-α
sin
l -2
φd φ(11)
其中N 为待估系数的个数.
该方法在实际计算时,Y 取为{y n }K n =1,X 取原设计矩阵D 的前K 行(或者是后K 行，视采用向前差分或向后差分而定，本文取前K 行)，显然，此时β并不是要估计的系数，但是它并不影响自动识别间断点的目的.此
时假定ε～N (0,σ2
I K )，这是因为ε是零均值的，而且它们之间可以认为是不相关的；由于该项会受到多种因素的影响，根据中心极限定理，可以做出符合正态分布的假定.实例表明该方法能够将间断点到，但是由于存在随机误差，容易受待估参数个数的影响而使非间断点误判为间断点，这种错误可以通过对信号的多组采样值处理后比较而避免.该方法的一个明显的优点就是自动识别而不受到先验信息的影响.31112　算法描述
(1)对采样信号值差分取绝对值，按照(1)中方法用“异常值判别准则”到跳跃点坐标，如果有多组采样信号，可以重复几次，比较后判断出跳跃点坐标以减小随机误差的影响;
(2)由估计出的跳跃点坐标根据式(3)生成跳跃字典，并和余弦基组成超完备字典;
(3)设置参数λ,β，利用基追踪方法求解系数，重构信号.31113　误差估计
在判断出间断点位置的前提下，误差可分成两类：一类是各段的逼近误差εi ，一类是段间间断点处的逼近误差εi
′，若分成m 段，那么总体误差可以表示为ε=
∑
m
i =1
εi
+∑m
i =0
εi
′(12)
根据结论[1]，如果存在0<s <q 对于信号f 满足
∫+∞-∞
|ω|
2s
|^f (ω
)|2d ω<+∞(13)
其中^f 为原信号的F ourier 变换,q 为所选小波的消失
矩.则有:
εi ～2-M
(14)其中M 是逼近的项数.可见对于信号的光滑段，小波逼
近的误差阶2-M ；但是，在信号的跳跃点附近，小波线性
逼近的效果不好.
理论上，对于存在第一类间断点的信号，估计出间断点位置后，可以转化成连续信号处理，本文证明了以下定理:
定理　若f (x )∈L 2[0,2
π]∩L 1[0,2π]，并且在[0,2
π]有m 个第一类间断点，则它一定可以表示为f (x )=
∑+∞
i =0
a i
cos ix +∑m
k =1
b k
(x -x 3k )0+
(15)
其中,{x 31,…,x 3
m }为f (x )的第一类间断点.
证明　设f (x )在x 3j 处的左右极限差为b j =
f +
(x 3
j )-f
-
(x 3
j )，令g (x )=f (x )-
∑m
j =1
b j
(x -x 3j )0
+，那么g (x )在区间[0,2
π]连续，并且当f (x )在除间断点外的区域光滑时g (x )是光滑函数，显然g (x )偶
延拓后可以展开成余弦级数，因此式(15)成立，证毕.
实际上，只要我们到了间断点，并且能够根据基追踪算法较准确地估计出b i ，那么逼近误差可以表达为εi +εi ′～2-M .这依赖于正则化参数λ的选取,λ取大时稀疏性明显，取小时逼近误差较小.实际上不存在对一切采样信号都既能保证逼近误差小又能具有很好稀疏控制功能的正则化参数，它是根据字典的构造和采样信号局部特征的具体性质而变化的；实际计算时，应首先考虑逼近误差，然后考虑稀疏性，合理的选择参数.31114
　算例分析
以余弦调制的矩形脉冲信号为例:
原信号图像如图1(a )，加入σ=011高斯白噪声
后，采用上述方法，取λ=011求解，得到图1(b )所示的重构信号.
该方法的局限在于把跳跃大的点都当成间断点处理，实际上，跳跃还可能是高斯类脉冲产生的，它是连续的，不能用跳跃字典处理.以下我们给出解决这个问题的一个新方法.312　基于自适应分割定义域的超完备稀疏表示3.2.1　分段思想和分割后现有的处理方法
不妨设自变量和信号值为{(x i ,s i )}N i =0.首先，我们
9
231第　7　期孙　蒙：两类混合特征信号的超完备稀疏表示方法
定义一个“单元”，它包含是一个包含C个自变量点的数组，于是整个信号最多可以分成L=「(N+1)/C 个这样的没有公共部分的“单元”(单元的大小也可不同).然后再对这些“单元”进行合理的合并，合并的原则就是使得总体的逼近误差和稀疏性尽量小.设组合这「(N+1)/C 个单元的方式的集合为T，于是问题归结为求解如下优化问题:
m in t∈T m in
α
t
{‖s-Dαt‖2+λ‖αt‖1}(16)
此处用正则化参数λ把多目标问题转化成了单目标问题.对于分割的某一段，采用本文中的超完备稀疏表示方法求解得到m in
α
t
{‖s-Dαt‖2+λ‖αt‖1}；整体上利用
动态规划来设计，求出使各段‖s-Dα
t
‖2+λ‖αt‖1的
和最小的自变量区间的划分方法和系数向量α
t
.
文献[5,6]都是处理音频信号的，这类信号的特点是突变较多；它们利用的是LPC技术，显然对于稀疏表示脉冲信号有缺陷.分割后，文献[8]采用的是正弦模型，可以看到该方法比直接利用正弦基去表示信号进步了许多.理论上，只要“单元”足够小，用正弦基或者是多项式基[8]都可以比较精确的表示原信号.但是当分段数超过10时，根据2.3中的推断，同样逼近精度下，该方法的稀疏性不如小波逼近.因此应该设法使分段数尽量少，现有的超完备稀疏表示技术可以达到较为稀疏精确的表示各段信号的目的.
本文借用存储和计算都非常简单的栅格算法(“T rellis Alg orithm”)文献[5]的思想而目标函数仍采用式(8)，针对分段光滑信号的特点，来达到分段稀疏表示的目的.对带有周期和冲击特征的信号，本文通过自适应分割技术分段处理，把正则性很差的奇异点分离出来，而不是用很多的系数去表示.在一定程度上克服了现有的稀疏表示技术“稀疏性度量准则困难”、“容易导致过分稀疏”的缺陷.
31212　算法描述
①把观测数据记成向量s，并且把自变量采样区间变换到[0,1];
②选择超完备字典，构造设计矩阵D;
③确定需要的参数λ,β,C，并且划分自变量区间为L个“单元”;
④按照如下的方式组织数据(如图3(a)):
在第t步,0≤t≤L-1，新增一个集合S
t
，它包含t +1个新划分方法s t,v,0≤v≤t(划分方法s t,v表示在距起始采样点v个单元处把含有t个单元的段分成两部
分).然后对于每个s
t,v ∈S
t
，依次完成以下步骤:
(a)计算目标函数值，它是两段[0,v]和[v,t]的目标函数‖s-Dα
t
‖2+λ‖αt‖1之和;
(b)把每种划分方法下得到的目标函数值按照图3
(a)所示的方式存储，实际上，对于每一步结束后需要记录的就是使得到该步为止使得目标函数最小的v值和相应的目标函数值;
(c)产生新的状态S L.
⑤动态规划，迭代求解.
不妨用j3
t
表示第t步的最小误差.显然初始值为j30=0.然后利用式子
j3t+1=m in
0≤v≤t
{j3t-v+m in
α
t,v
{‖s-Dαt,v‖2+λ‖αt,v‖1}}
(17)
和存储j3
t-v
,v=0,…,t的求出使得第t+1步总体误差
最小的分割点v3
t+1
，把最小值j3t+1和相应的分割点v3t+1
存储.然后连接s3
t,v
和s
t+1,0
，把(j3t+1,v3t+1)编入路径.如图3(b)所示.
⑥回溯，得到最终的划分.
从j3
L
开始沿着⑤中的路径，从s
L,0
到s0
,0
，
假设该路上k个这样的值，于是最优分段为t3={t0,t1,…, t k,t k+1=L}.(图3(b)).
⑦按照⑥中得到的最优分段，分别进行超完备逼近重构信号，计算出逼近误差和稀疏性.
31213　逼近误差阶的估计
同前一节误差的估计一样，此处仍然假定分割后每段都是近似光滑的信号.显然,
根据已知结论，对于各光滑信号
段，逼近误差可取为2-M；而对于两
段间的区域，可以如下估计逼近误
差.
通过对各段稀疏表示，对该间
断点的左右两段光滑函数做出表
示,x
i
以左采用得到一个重建表达
式,x
i+2
以右得到另外一个重建表达式,x
i+1
是间断点.
把这两个函数分别延拓到x正则匹配关键词
i+2
和x
i
，
如图2所示.如果这两个逼近函数绝对值的公共上界为A，那么，间断点x i和x i+2之间的函数值的逼近误差为:εi′≤4A2(x i+1-x i).可见当步长x i+1-x i很小时误差也很小.
需要指出的是，此处间断点误差的估计不同于F ourier或小波逼近时对于奇异点的逼近误差.后两者都是通过增多系数来捕捉间断点的跳跃，它们可能导致间断点周围点的振荡，比如G ibbs现象，而小波基做线性逼近的误差阶为1/M，非线性逼近在实际中较难求解.
31214　算例分析
本文采用Shannon尺度函数去逼近“脉冲”，对在“单元”长度整数倍附近的间断点能实现自动区分.为便于观察该算法的效果，对于带有周期和冲击的混合特征信号，本文给出一个既含有“脉冲”又含有“振荡”
0331  电  子  学  报2007年
和“间断点”的例子，并且与已有的方法在逼近误差和稀疏性方面进行比较.
示例信号
f (x )=
e
-100(x -π/2)
2
,
0≤x ≤
πcos x ,
π
<
x <2π
(18)
选用余弦基和Shannon 父小波基组成超完备基，每个单元的长度取为C =10，采样点数为100，然后按上述算法求解得到用本文算法稀疏表示信号的结果.
表1　各种方法逼近误差和稀疏性的比较
小波方法
追踪算法
本文方法
逼近误差
0.45720.11360.0031系数的L 1范数22.16102.04941.8693所选字典
Haar
C osine Shannon
C osine Shannon
  从图4和表1可以看出，小波逼近在尺度增大时精度效果较好，但是稀疏性很差；现有的基追踪算法，参数选择困难，此处选取了较小的正则化参数，使逼近误差较小，但是在间断点处的伪振荡明显，效果不好；本文的方法通过自适应分割，把间断点单独考虑(该方法
不对间断点的小邻域内的信号值做估计，这些值可根据间断点的采样值和左右极限再结合实际情况估计得到)，避免了间断点附近的伪振荡，在逼近精度和稀疏性方面都比较令人满意.
但是，该方法仍存在以下缺陷:
采样点数目一定时，当每个单元包含的点的个数较少时，单元的数目就会增多，计算的复杂度就明显的增加；分割的效果对于不规则点(间断点、跳跃点)的分布也是比较敏感的，分布不均匀时，难以到合适的单元长度C ，处理效果不好.4　结论
  本文提出了基于跳跃字典的超完备稀疏表示方法和基于自适应分割定义域的超完备稀疏表示方法.这两种新方法对两类混合特征信号的稀疏表示取得了较好的效果；但两种方法都存在着局限性，还需要进一步的改进完善.
参考文献:
[1]St éphane Mallat.A Wavelet Tour of Signal Processing [M ].
2nd Edition.London :Academic Press ,1999.286-330.[2]Donoho L ,E LAD M.Optimally Sparse Representation in Gen 2
eral Dictionaries via Minimization [J ].PNAS ,2003,100(5):
2197-2202.
[3]汪雄良，王正明.基于快速基追踪算法的图像去噪[J ].计
算机应用,2005,25(10):2356-2358.
WANG Xiong 2liang ,WANG Zheng 2ming.Image de 2noising via fast basis pursuit methods [J ].Computer Applications ,2005,25(10):2356-2358.(in Chinese )
[4]王正明，易东云.测量数据建模与参数估计[M ].长沙：国
防科技大学出版社,1996.142-152.
[5]Prandoni P ,Vetterli M.R/D optimal linear prediction[J ].IEEE
Transaction ,Speech and Audio Processing ,2000,8(6):646-655.
[6]Zhen Wang ,Willett P.Fast and accurate variance 2segmentation
of white Gaussian data [A ].Proceedings :IEEE International Conference on Acoustics ,Speech ,and Signal Processing ,2002
[C ].IEEE Press ,2002(vol.2):1577-1580.
[7]汪雄良，王春玲.基于改进基追踪方法的信号去噪[J ].电
子技术应用,2005,31(8):19-21.
WANG Xiong 2liang ,WANG Chun 2ling.Signal De 2noising via fast basis pursuit methods [J ].Electronic technology applica 2tions ,2005,31(8):19-21.(in Chinese )
[8]Goodwin M.Multiresolution sinusoidal modeling using adaptive
segmentation[A ].Proceedings :IEEE International Conference on Acoustics ,Speech and Signal Processing ,1998[C ].IEEE Press ,1998(vol.3):1525-1528.
[9]赵鹤鸣，葛良，陈雪勤，俞一彪.基于声音定位和听觉掩蔽
1
331第　7　期孙　蒙：两类混合特征信号的超完备稀疏表示方法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。