1. 引言
当今时代,信息科学技术迅猛发展,大量的数据信息进入我们的生活,需要处理的数据量增大速度惊人。在信息处理过程中,获得信息的最重要途径是对信息进行采样,但传统的采样感知理论受奈奎斯特(Nyqusit)采样定理的限制,要求在采集信号时,信号的频率不能低于信号最高频率的两倍,这样就对相应的信号采集的硬件设备提出了更高要求,很大限制了信号处理的能力。基于此,人们开始找寻一种不受奈奎斯特定理约束的信息采集处理方法。
针对可稀疏压缩信号,Donoho等[1] -[5] 在稀疏分解和信号恢复等思想的基础上提出压缩感知(CS)理论框架。随后该理论得到迅速发展,在2006年Donoho[2] 正式提出了“压缩传感”这一术语。
传统感知的方式是先对信息进行采样后处理,而压缩感知将采样过程和压缩过程同时进行,采样更少但后续处理信息时的计算更多。压缩感知理论中最核心的部分就是信号重构,是指通过压缩测量的低维采样数据,精确或较精确地重构高维原始信息。
对于压缩传感信号重构问题,理想情况下是通过求解最原始的重构模型,即
. (1)
其中表示中非零元素的个数。基于范数重构信号的算法主要是贪婪算法,这其中比较经典的是正交匹配追踪法(Orthogonal Matching Pursuit, OMP)[6] [7] 。
由于基于最小范数进行信号重构的问题是一个NP-hard问题,所以实际中一般用求解最小范数来进行信号重构。文献[6] [7] 证明了问题与的等价性,并研究了其等价条件。基于最小范数进行信号重构问题模型如下:
. (2)
其中,基于范数最小进行求解的算法中最基本的是基追踪法(Basis Pursuit, BP)。事实上伪范数比范数更接近原问题中的范数。
图1是多维情况下极小化的图形,图2是多维情况下极小化的图形由图1和图2可以看出,恢
Figure 1. The minimize of
图1. 极小化
Figure 2. The minimize of
图2. 极小化
复信号时范数优化有时比范数优化方法效果会更好。
伪范数比范数更接近原问题中的范数。问题模型如下,
. (3)
文献[7] 指出稀疏向量是的全局极小解,并且比范数优化方法所需的的观测数量更少。同时文献[8] -[10] 证明了比范数优化方法重构信号要求更弱的充分条件。下面我们用极大熵函数构造范数的光滑逼近函数,进而实现信号重构。
由于范数最小化问题(3)中的目标函数可表示为
.
故问题(3)也可以写成如下形式,
(4)
由于问题(4)中的目标函数不可导,故光滑约束算法不能使用。本文构造光滑函数去逼近式(4),将问题转变成约束光滑问题,从而用光滑约束算法求解。
2.范数的光滑近似
由于最大值函数可用极大熵函数光滑近似[11] ,其中参数,为变量。因此可用极大熵函数代替式(4)中的函数,得到如下光滑问题:
(5)
引理1[12] 假设,,为连续可微的函数,
则函数有以下性质:
1)和,有;
2)和有;
3)有。
引理2 式(5)定义的函数有如下性质。,有
(6)
证明:由本文引理1知,,,有
(7)
由和的定义,有
由式(7)可得
证毕。
引理3,,有
且。
对问题(3)作如下假设:
矩阵的秩为,变量,其中为基变量所对应的向量,为非基变量所对应的向量;为基变量所对应的矩阵中的列,为非基变量所对应的矩阵中的列,矩阵,可行域非空。
在上述假设条件下,(3)中的约束条件可写成。
由此可得,将带入问题(5)的目标函数中,则式(5)转化为如下无约束问题:
. (8)
本文分别用和记问题(4)和(5)的最优解。
3. MEFM算法
算法1(Maximum Entropy Function Method)
步骤1 取,误差,,。
输入矩阵,,测量值、阀值,步长。
步骤2 取。
步骤3 求解式(8),即求解如下问题
步骤4 若,置:,返回步骤3;反之,输出。
MEFM算法具有如下性质。
定理1 假设式(8)的最优解为,且算法1产生的点满足
(9)
则
式中为迭代次数。
证明:由是式(5)的最优解,即
(10)
再由式(6)得
因此可得
(11)
由(6)式得
(12)
式(11)与式(12)相加得
(13)
再由(8)可得
(14)
由式(9)和式(14)可知
(15)
再由式(14)和(15)有
(16)
将代入式(16)可得,
定理2 假设是式(3)的最优解。若存在,设,若中存在时有。则是问题(3)的最优解。
证明:对由,有
由引理3得
(17)
式(17)中令,并由定理2中的条件(2)可得
由于是式(5)的最优解,故对任意满足的点有
故。
以下证明是问题(5)的可行解,由于是式(5)的最优解,故有。令,可得,即是问题(5)的最优解。
4. 信号重构实例
用MEFM算法和OMP算法对一维信号进行重构。其中重构信号稀疏度,信号长度,信号观测度,,,,,,,;由图3可以看出重构信号稀疏度K = 6。
测量值必须满足的,取时,采样率,取,,,用MEFM算法对信号进行重构,重构效果如图4;用OMP算法重构信号,信号重构效果如图5。由图4和图5可以看出MEFM算法和OMP算法都能够很好的重构信号。
Figure 3. Original signal; Frequency domain
图3. 原始信号;频域信号
Figure 4. Reconstruction effect of one-dimensional signal
图4. MEFM算法重构信号
Figure 5. Reconstruction effect of one-dimensional signal
图5. OMP算法重构信号
Table 1. Error of reconstruction
表1. 重构误差
表1分别列出了MEFM算法和OMP重构算法的重构误差,可以看出,在相同采样率的情况下,MEFM算法的信号重构误差为2.9716e−024,OMP算法的信号重构误差为7.2093e−004。即采样率相同时,MEFM算法比OMP重构算法的重构效果更好,重构误差更小;OMP算法在运行时需已知信号稀疏度,而MEFM算法运行时不需要已知信号稀疏度;OMP算法是基于范数最小化问题,是非光滑的,而MEFM算法是基于极大熵函数光滑化的最小化问题,一些基于求导求解的方法都适用,所以计算更方便,效率更高。
参考文献