基于l1-l2范数极小化的稀疏信号重建条件

周 珺, 黄 尉

(合肥工业大学 数学学院,安徽 合肥 230601)

0 引 言

压缩感知(compressed sensing,CS)是由Donoho、Candes、陶哲轩等人首先提出的一种新型的采样理论[1-2],主要是利用信号的先验信息,考虑从较少的线性测量中恢复高维稀疏信号。一般考虑以下模型:

y=Aβ+z

(1)

其中,A∈Rn×m(n≪m)为测量矩阵;z∈Rn为测量误差。压缩感知的目标是基于y和A重建未知信号β∈Rm。值得注意的是,假设信号是稀疏的,在无噪情形下,若测量矩阵A满足一定条件,则未知信号β可以被准确恢复。

为了解决上述问题,一个自然的想法就是采用l0最小化去找到满足Aβ=y可行解集合中最稀疏的解,但这是一个非凸和NP-难的问题,计算上是不可行的。因此,人们想到对l0最小化进行凸松弛,利用l1最小化方法来解决上述问题, 即

(2)

特别地,与l1范数相比,l1-l2范数更接近l0范数,从理论上说,l1-l2最小化模型优于l1最小化模型[3-4]。因此,本文考虑用l1-l2极小化方法从欠定的线性测量中重建信号,现考虑如下约束优化问题:

(3)

其中,B为取决于噪声的类型。特别地,在无噪声情形下(B={0})有:

(4)

其中, (3)式和(4)式是本文主要的研究模型。

本文主要研究了若测量矩阵A满足一定条件,则通过l1-l2极小化方法可以使k-稀疏信号精确恢复。此条件弱于文献[4]中给出的2k阶限制等距性质(restricted isometry property,RIP)条件。

1 预备知识

RIP由文献[1]首先提出,是压缩感知中使用最多的框架,主要是刻画一个矩阵和标准正交矩阵的相似程度。

定义1(RIP)[1]假设A∈Rn×m是一个测量矩阵,1≤k≤m是一个整数,若存在一个常数δk(0≤δk<1),对任意k-稀疏信号β,满足:

(5)

则称矩阵A满足k阶RIP。若δk是对每个k-稀疏信号均满足(5)式的最小非负数,则称δk为k阶限制等距常数(restricted isometry constant,RIC)。

定义2(ROC)[5]假设A∈Rn×m是一个测量矩阵,定义(k1,k2)阶限制正交常数(restricted orthogonal constant,ROC)为最小非负数θk1,k2,使得对任意具有不相交支撑集的k1-稀疏矢量β1和k2-稀疏矢量β2满足:

|〈Aβ1,Αβ2〉|≤θk1,k2‖β1‖2‖β2‖2。

引理1[6]令k1、k2≤m且λ≥0,假设信号β1、β2∈Rm有不相交支撑集,β1是k1-稀疏矢量,β2满足‖β2‖1≤λk2且‖β2‖∞≤λ,则有:

显然,引理1是对ROC定义的一般性推广。

定义3[3]若矢量x∈Rm,则定义矢量x的最佳k项近似误差为:

2 主要结论

2.1 稀疏信号的重建

定理1若信号β是k-稀疏的,测量矩阵A∈Rn×m满足:

(6)

Ti={pl:(i-1)k+1≤l≤ik},

因此

特别地,

故

移项整理得:

(7)

又因为

|〈AhT01,AhTj〉|≤

因此

于是有:

|〈Ah,AhT01〉|≥|〈AhT01,AhT01〉|-

(8)

因为Ah=0,所以由(7)式和(8)式有:

假设信号β不是k-稀疏的,现考虑如下2种类型的噪声情形:

(1)Bl2(ε)={z:‖z‖2≤ε}。

(2)BDS(ε)={z:‖ATz‖∞≤ε}。

定理2 若测量矩阵A∈Rn×m满足:

证明(1) 证明Bl2(η)={z∈Rn:‖z‖2≤η}。证明过程与定理1相似,不同之处如下:

|〈Ah,AhT01〉|≤‖Ah‖2‖AhT01‖2≤

其他过程与定理1相同,可得:

‖hT01‖2≤

(9)

由(7)式和(9)式得:

(2) 证明BDS(η)={z∈Rn:‖ATz‖∞≤η} 。类似地,

且

(10)

由(7)式和(10)式得:

2.2 高斯噪声情形

高斯噪声情形作为一种特殊情形被很多学者关注[8-9],其观察模型为:

y=Aβ+z,z～N(0,σ2In)。

假设σ是已知的,矩阵A中的列向量均为单位向量,定义如下2个噪声类型:

则分别对应有[9]:

这表明高斯变量z以高概率处于集合B1和B2中。显然,由定理2可给出如下定理。

定理3若测量矩阵A∈Rn×m满足:

则有如下结论:

3 结 论

本文主要考虑从很少的线性测量信号中恢复稀疏信号,基于RIP框架,得到了通过l1-l2极小化方法精确恢复稀疏信号的一个充分条件,同时,给出了有噪声情形下的误差估计。