基于OMMP 算法的多测量向量问题的重构

冯晓艳,王金平

（宁波大学 数学与统计学院,浙江 宁波 315211）

压缩感知[1-2]作为一种新的采样理论,已广泛应用于各个领域,如图像压缩、信号处理、雷达系统以及医学成像等[3-6].压缩感知的主要目的是从模型

中恢复稀疏信号x.我们可以通过找到如下l0优化问题的解,达到这一目的:

式中:y∊Rm是测量向量;Φ∊Rm×n(m≪n)是感知矩阵;v∊Rm是噪声向量;||x||0是x的l0范数,表示x的非零项个数,对于任意向量x,定义其支撑集: supp(x)={i:xi≠0}.如果它是K-稀疏的,则有||x||0≤K.式(1)是单测量向量的稀疏恢复,可以拓展到多测量向量的稀疏恢复问题.本文主要研究多测量向量问题[7-9].

多测量向量问题在脑磁图扫描技术[10]、波达方向估计[11]等领域有着广泛应用.向量x的支撑集上面已给出,对于矩阵X=(X1,X2,…,Xp)∊Rn×p,定义其行支撑集为:

这里Xi表示矩阵X的第i列,若测量矩阵Y∊Rm×p,感知矩阵Φ∊Rm×n是已知的,则多测量向量问题可以描述为:

这里|supp(X)|表示矩阵X的非零行数.若|supp(X)|≤K,则称矩阵X是K-行稀疏的.很显然,当p=1 时,多测量向量(MMV)问题就变成了单测量向量(SMV)问题.

文献[12-13]已证明,当矩阵Φ满足一定条件时,通过恢复单测量向量的一些稀疏算法可以稳定恢复未知信号x.在分析稀疏恢复算法的恢复性能时,限制等距性(RIP)是使用较为广泛的方法之一.对于感知矩阵Φ∊Rm×n和任意正整数K,若存在一个常数δ∊ (0,1)满足:

则称Φ满足K阶的限制等距性,使得式(4)成立的最小常数δK称为Φ的限制等距常数(RIC).

正交匹配追踪算法(OMP 算法)是解决式(1)非常有效的一种贪婪算法,其对式(3)同样有效.正交多匹配追踪算法(OMMP 算法)[13](也被称作gOMP 算法[14])作为OMP 算法的拓展,每次迭代从感知矩阵Φ中选择与残差相关性最大的N≥1 个列作为指标集.由于每次迭代选择多个正确的指标集,所以相较于OMP 算法,OMMP 算法所需的迭代次数更少.在某些条件下,OMMP 算法可以找到式(3)中的最稀疏解X.多测量向量问题的OMMP 算法如下:

对一般的正整数N,为保证OMMP 算法准确地恢复K-稀疏信号,已有很多基于RIC 条件被陆续提出.Liu 等[14]提出,当限制等距常数δ满足:

时,OMMP 算法可恢复任意K-稀疏信号;Wang 等[15]证明了

是OMMP 算法经K次迭代恢复任意K-稀疏信号的一个充分条件;该条件又被Satpathi 等[16]改善为:

Shen 等[17]将限制RIC 条件进一步改善为:

Wen 等[18]提出了更加松弛的RIP 条件,即RIC 满足:

时,OMMP 算法可以在K次迭代准确恢复K-稀疏信号.文献[18]中的RIC 针对单测量向量问题中的OMMP 算法.本文将此条件由单测量向量问题过渡到多测量向量问题,发现该结论仍然成立.

在单测量信号恢复中,信噪比(SNR)和最小平均比(MAR)根据文献[19]定义如下:

受此启发,在多测量向量问题中把它们分别命名为多向量信噪比(MSNR)和多向量最小平均比(MMAR),并定义为:

有了这两个新定义,我们将证明在MSNR 和MMAR 满足一定条件下,若限制等距常数δ满足:

则OMMP 算法每次迭代可以确保恢复至少一个正确的指标集.

1 预备知识

首先介绍文中出现的一些基础符号的含义,以及用到的引理.

对任意矩阵A∊Rn×p和B∊Rn×p,定义内积

其中:AT表示矩阵A的转置.由这种内积诱导的范数是Frobenius 范数,记为||∙||F.对任意向量x和矩阵X,||x||2和||X||F分别表示x的l2范数和X的Frobenius 范数,且

I和0 分别表示单位矩阵和零矩阵.T=supp(X)是X的支撑集,|T|表示集合T的基数,Λ={1,2,…,n}且TΛ={i∊T,i∉Λ}.令Tc和Λc分别表示T和Λ的补集,即Tc={1,2,…,n}T,Λc={1,2,…,n}Λ.矩阵ΦΛ表示Φ的子矩阵,其中仅包含由Λ索引的列.类似地,XΛ∊R|Λ|×p表示X的子矩阵,其中仅包含由Λ索引的行.如果ΦΛ是列满秩矩阵,Φ†是其伪逆矩阵,则Φ†=分别表示ΦΛ的列空间上的投影和正交补投影.由PΛ的对称性和幂等性可得表示矩阵Φ中任意一行的最大l2范数.

下面介绍几个有用的引理.

引理3[21]假设矩阵M∊Rn×p,N∊Rn×p,则

引理 4[22]矩阵A∊Ra×a,B∊Ra×a都是对称矩阵,且AB≠0,则

2 主要结果

给出MMV 问题的OMMP 算法可以稳定恢复K-稀疏信号的充分条件.首先给出以下引理.

引理5对于正整数N,k,l,0≤k≤l≤|T|-l,且N(k+1)+|T|-K≤m,集合Λ⊂ {1,2,…,n}满足|Λ|=Nk和|T∩Λ|=l,令集合W⊂Tc满足|W|=N且W∩Λ=∅.若Y=ΦX+V中的Φ满足N(k+1)+|T|-l阶的RIP 条件,则

在证明前需要说明,引理5 的灵感主要源自文献[18],把文献[18]中的p=1 延拓到一般的p,即MMV 问题.不同于文献[18]中定义的向量定义矩阵EW=RN×p(式(15)).

首先证明

此处(a)是由式(9)所得,(b)是因为

通过计算可得:

为了书写方便,令W={j1,j2,…,jN},并且定义矩阵E∊RN×p为:

X(t)TΛ表示矩阵XTΛ的第t列,(EW)t表示EW的第t列.不难得到:

此外,还定义

则有:

因此有:

这里(a)是由式(18)～(20)所得,(b)和(c)分别由式(12)和式(15)所得.进而有:

由式(26)可得:

最后一个等号是由式(14)的第一个等式得到.另一方面,有:

此处(a)是由引理2(|T∩Λ|=l,|W|=N,|Λ|=kN和|Λ∪((TΛ) ∪W)|=N(k+1)+|T|-l)得到;(b)由式(22)和式(23)得到;(c)由式(14)的第二个等式得到.

结合式(18)、(27)、(28)以及1-μ4＞0可得:

结合式(11)和式(29)可得:

引理5 的证明结束.

注释1当p=1 时,引理5 中式(10)就变为文献[18]中的

当p=1 且N=1 时,该结论变成文献[23]中

引理中条件N(k+1)+|T|-k≤m是为了确保假设Φ满足N(k+1)+|T|-l阶的RIP 条件.

有了引理1,可以证明定理1.

定理1对正整数k和N满足0≤k≤|T|-1和N(k+1)+|T|-k≤m,假设矩阵Φ满足N(k+1)+|T|-l阶的RIP 条件,即

则OMMP 算法在前(k+1) 次迭代中每次迭代至少可以识别一个T中的索引,直到T中所有索引都被识别,或OMMP 算法在满足条件:

时终止迭代.

用数学归纳法证明该结论.

假设OMMP 算法在前k次迭代中至少选择一个正确索引,则有l=|T∩Λk|≥k.假设T⊈Λk(即l≤|T|-1)以及算法1 至少迭代(k+1)次,否则结论显然成立.接着需要证明(Λk+1Λk)∩T≠∅.由于Λ0=∅,所以k=0时归纳假设|T|＞|Λk∩T|≥k成立.因此,第一次迭代的证明包含k=0 的情况.

让

满足

则要证(Λk+1Λk)∩T≠∅,只需证

由式(33)知,只需证

即可.

由算法1 的第4 和5 行可知:

令

接着证明

显然,存在i0∊TΛk和j0∊W满足:

因此

此处(a)是由Cauchy-Schwarz 不等式所得,(b)由引理2 和可得.下面给出β1的下界.由算法1 的第3 行知,|Λk|=kN.由归纳假设,

由式(32)和|W|=N,结合引理1 和引理5,以及式(39)可得:

第二个不等式是因式(43)中k≤l以及引理1 得到.又由l=|T∩Λk|,故有:

这里(a)和(c)是将式(6)直接代入即可,(b)是由于

因此有:

将式(44)和式(46)结合可得:

由式(42),要想式(41)成立,只要使

这等价于式(31).由归纳假设,结论成立.定理中当k=|T|-1时,结合引理1 可以得到定理2.

定理2对于正整数N满足1≤N≤(m-1)/K,假设矩阵Φ满足RIP 条件

则OMMP 算法在k0(1≤k0＜K)次迭代终止之前至少检索到T中的k0个索引,或者在K次迭代中恢复T只要

注释2当N=1 且p=1 时,MMV 问题的OMMP 算法就变成了SMV 问题的OMP 算法,对应的条件变成文献[19]中的

很显然,我们的条件比该条件更松弛.

考虑OMMP 算法迭代k0(0＜k0＜K)次后可能会终止,此时该算法在式(48)和式(49)的条件下不能保证恢复T.因此将再给出一个定理,在给出新定理前,先给出引理6.

引理6假设V=0,对于正整数k,N,并且有1≤k≤|T|-1和1≤N≤(m-1)/K,矩阵Φ满足RIP 条件

证明用反证法证明这个引理.设T⊈,令Γ=T∪.定义

由定理2 和引理6,可以直接得出定理3.

定理 3假设噪声V=0,对于正整数N(1≤N≤(m-1)/K),矩阵Φ满足RIP 条件

则OMMP 算法可以在K次迭代中恢复X.

注释3在p=1 且没有噪声的情况下,OMMP算法在K次迭代准确地恢复稀疏信号x的充分条件是

很显然

即定理3 的条件更松弛.

3 结论

本文将OMMP 算法中的SMV 问题扩展到MMV 问题,并证明了在MSNR 和MMAR 的条件下,若矩阵Φ满足RIP 条件

则OMMP 算法可以准确恢复K-行稀疏矩阵X.