任晓奎　张芷宁

(辽宁工程技术大学电子与信息工程学院　辽宁 葫芦岛 125105)

0　引　言

在信号或者图像的处理、传输等方面，奈奎斯特采样定律一直都是遵循的准则，但由于其在资源利用率等的方面的缺陷促进了压缩感知CS(Compressed sensing)这一新采样技术的出现。相比于奈奎斯特采样定律，压缩感知技术是将压缩和采样合并起来，利用较少的信号投影测量数据量，根据相应的重构算法，最终重构出较为完整的信号[1-2]。

压缩感知技术在稳定中发展，在不同的研究领域中都有体现，尤其是在信道估计领域中。传统的信道估计方法如最小二乘(LS)法[3]和最小均方误差(MMSE)法[4]都需要大量的导频信号才能做出准确的

估计，并且这些方法主要针对的是密集型信道。由于近些年的研究我们可以知道，实际条件下的信号多数都是稀疏的，如果依旧不顾效率采用大量的导频信号，会造成资源的严重浪费。贪婪算法[5]是压缩感知重构算法中极为重要的一类算法，其中匹配追踪MP(matching pursuit)、正交匹配追踪算法OMP(orthogonal matching pursuit )[6]、广义正交匹配追踪(GOMP)算法[7]均已在稀疏信道估计中得以应用[8-10]。但是，MP与OMP算法在应用时所需要的迭代次数过多，所需时间较长，导致重构效率不高。GOMP算法虽然在重构时间上较OMP算法有所提高，但是由于选择原子的方法不够完备，再加上原子数目的增加，使其最小均方误差(MSE)和误码率(BER)略差。而且OMP和GOMP算法的实现都需要稀疏度已知为前提才可实现，而实际环境这一前提无法满足，导致了这几种算法在信道估计中的局限性。本文提出改进的GOMP算法在不知晓稀疏度的情况下，通过变步长实现稀疏自适应匹配，并利用傅里叶变换的共轭对称性在原子的选择方面加以完善，提高了算法的应用价值。

1　压缩感知技术

压缩感知技术的本质，也就是把压缩和采样合二为一，即采样的过程也就是完成压缩的过程，经压缩感知采样后的数据本身也就是压缩后呈现的数据。通过对原始信号的一种提取后的精炼表达，减少了原始数据在存储空间或者传输带宽方面的需求。

运用压缩感知技术，需要关注的重点有两个。第一个是怎样设计出一个测量矩阵Φ，使得它可以在采样的整个过程中包含着信号中较为有效的信息[11]；第二个是怎样通过测量矩阵y重构原始信号x[12]。为此应该研究测量矩阵Φ应该具备的性质。首先应从确保重构的必要条件零空间特性开始。但是论证零空间特性是确保重构的必要条件这一过程中，并没有考虑到噪声的影响，所以在面向实际条件时，有必要在更为严格的情况下进行推导。这一点上促使有限等距性质RIP(restricted isometry property)在整个压缩感知理论中具有了重要地位[13]，即：

若存在δk∈(0,1)，使得：

(1)

2　算　法

2.1　OMP算法

正交匹配追踪(OMP)算法与之前的算法相比，保证了残差和已选列正交的这一条件，从而使相同的列并不会再一次被选中，减少了迭代的次数，优化了整个迭代的过程[15]。

OMP算法的本质是通过贪婪策略在Φ中来挑选一列原子。OMP算法首先选择原子φi∈Φ，然后将观测信号投影到原子上，以获得残差[16]。这些可以描述为:

y=ri+<φi,y>φi

(2)

它的目的是选择出使残差的二范数最小的原子。其中r1和<φi,y>φi明显是正交的，因此：

(3)

(4)

在每次迭代中，新的原子总是和残差保持正交关系。当迭代停止时，获得重建信号。这也就是OMP算法的基本原理。虽然OMP算法对于满足RIP性质的信号都可以做到较高精度的重构[17]，但是当原始信号具有较大长度时，OMP算法仍然只在一次迭代中选择一个原子，因此需要更多的迭代次数来进行原子的选择，必然会导致重构时间的大幅度增长，使得重构的效率低下。而在实际的信道估计领域中，其他算法整体重构精度的提高，无疑使算法的复杂度成为其走向实际应用的最大障碍。再加上OMP算法需要信号的稀疏度作为先验信息，也极大程度地限制了它的发展。

2.2　GOMP算法

GOMP算法在选择原子这一方面较OMP算法进行了改进[18]。GOMP算法首先计算内积。

C={ci|ci=yTφii=1,2,…,N}

(5)

OMP算法选择最相关的原子，其对应于C中的最大系数。但GOMP算法在每个迭代步骤中选择n个顶部原子(ci1,ci2,…,cin)。然后使用式(4)获得y的近似值，并使用以下公式更新残差：

(6)

式中：ΦΛ是由选自于Φ的原子所组成的子矩阵。

GOMP算法的具体步骤如下：

已知观测向量y，传感矩阵Φ，原子选择数S(S≤K)，迭代次数t。

(1) 进行初始化：r0=0,H=φ,t=0,J=φ。

(2) 令迭代次数增加：t=t+1。

(3) 计算相关系数：Ct=ΦTrt-1。

(4) 从计算出的Ct中挑选出最大的S个原子，然后将这些原子添加到集合J中。

(5) 更新索引集：H=H∪J。

由以上可知，选择原子数目的增加使得GOMP算法在收敛速度上比OMP算法要快得多，重建效率也有了提升，但需要提前了解稀疏度K这一不足仍没有得到较好的改进。对于原子选择方面，有研究结果表明，当时域信号将傅里叶基作为稀疏基时，重构过程中出现的少量的对频谱的估计错误，也将会很大程度上影响重构的精度[19]。如果仅是利用相关性来进行原子的选择，会使选择具有盲目性。并且在观测过程中出现大量噪声的情况下，容易出现更多的估计错误，从而导致原子匹配程度和支撑集选择的准确性降低，进而影响信号重构的成功率。因此，应该从如何适应在稀疏度K未知情况下重建信号，以及如何更准确更稳定地选择原子这两方面同时对GOMP算法加以改进。

2.3　改进的GOMP算法

原始信号x与各个原子之间的相关性在持续迭代的过程中有所下降[20]。先前几次迭代中所选择的原子体现的作用更大，选择的不确定性导致的原子错误将会对整个结果产生更大的影响。因此，在早期的迭代过程中，我们将选择原子的个数设置为一个较小的数值，以免选择出大量的错误原子。而后，当残余量减少缓慢的时候，逐渐增大S的取值。

其次，通过把傅里叶变换的共轭对称性与之前利用相关系数这一选择原子的唯一依据相结合，增强原子选择的准确性，以增强整个算法的成功率。下面对傅里叶变换的共轭对称性进行分析。

若f(t)为实信号，则它的傅里叶变换为F(jω)[21]，可以如下表示：

(7)

考虑到r-jωt=cosωt-jsinωt，则式(7)可写为：

R(ω)-jX(ω)=|F(jω)|ejφ(ω)

(8)

式中：频谱函数的实部与虚部以及模量与相角均为ω的实函数，并分别为：

(9)

(10)

(11)

(12)

由式(9)-式(12)可知，频谱函数的实部与模量是频率ω的偶函数，虚部与相位是频率ω的奇函数。

如果f(t)是t的偶函数，则式(10)的积分为零，其频谱函数仅有实部，是ω的实偶函数。即:

(13)

由此可以得到:F(jω)=F*(-jω)。

如果f(t)是t的奇函数，则式(9)的积分为零，其频谱函数仅有虚部，是ω的虚奇函数。即:

(14)

由此可以得到:F(jω)=-F*(-jω)。

研究可知，大多数的时域信号在傅里叶基中都能保持有良好的稀疏性。当把傅里叶基作为稀疏基时，信号的各个采样点都能找到以信号的采样频率的一半为中心与自身对称的点，也就是傅里叶变换的共轭对称性[22-23]。

改进的算法将傅里叶基作为稀疏基，以使信号具有傅里叶共轭对称的性质。在选择原子的时候，只是对相关系数的前一半进行筛选，选择出相关性最高的S个原子，将它们的下标添加进入集合J中。之后利用傅里叶变换的共轭对称性对剩余的原子进行选择，也就是在剩余的相关系数中找出与添加进入集合J的原子的对称点即可，然后一并加入到集合J中。此时，集合J中有2S个原子，只需要在这里挑选出最匹配的S原子再加入新的集合中即可。

虽然OMP与GOMP算法选择原子的数目不相同，但都是以相关性作为选择原子的唯一标准。两者需要将全部相关系数进行比较，从中筛选出相关性最高的一个或几个原子。相比较来说，改进后的算法只需要对前一半相关系数进行处理，另一半可以在前一半的基础上得出，从而提高了原子选择的效率。并且在利用了傅里叶变换的共轭对称性的情况下，两种标准相互辅助，使原子的选择更加针对和可靠，当观测过程出现大量噪声时候仍能有效控制原子选择这一过程，进而提高了原子选择的精度。

改进的GOMP算法的具体步骤如下：

已知观测向量y，传感矩阵Φ，原子选择数S(数值较小)，迭代次数t。

(1) 进行初始化：r0=0,H=φ,t=0,J=φ,Q=φ。

(2) 令迭代次数增加：t=t+1。

(3) 计算相关系数：Ct=ΦTrt-1。

(4) 在步骤(3)计算出的相关系数Ct的前半部分中选出最大的S个原子，然后将这些原子的下标添加到集合J中。

(5) 对于剩余部分，利用傅里叶变换的共轭对称性，将与添加到集合J中的原子下标所对称的点找出来，同样加入到集合J中。最终，在集合J中选出最大的S个原子组成新的集合Q。

(6) 更新索引集：H=H∪Q。

其中,ε1就是GOMP算法中的阈值，它的取值受原始信号中噪声的影响；而ε2是为了判断残差减少的程度，低于这个取值的时候，选择原子的个数将不会再增加。在大量实验的验证下，本文将ε2的取值设置为0.7，并应用于接下来的仿真实验中。

以上就是改进的GOMP算法的具体步骤。针对上文提到的先前算法的不足之处，通过可变步长来实现稀疏自适应匹配，并利用傅里叶变换的共轭对称性增强选择原子的效率和准确性。

3　实验仿真与验证

在理论的基础上，本文通过如下的仿真实验，从不同的参考角度与之前的两种算法进行对比，证明改进后的GOMP算法在信道估计性能方面的优越性。仿真硬件为Intel(R) Core(TM) i5-3230M CPU，主频为2.6 GHz，内存为8 GB，Microsoft Windows 7操作系统，仿真软件为MATLAB。

仿真如下，假设天线方案为2根发射天线和2根接收天线，系统子载波个数为1 024，导频数为25，信道长度为30，并且信道参数在一个OFDM符号内保持不变。利用算法的归一化均方误差(MSE)和误比特(BER)来反映几种算法的估计性能[18]，MSE的定义为：

(10)

二者数值越小，代表估计的性能越好，反之亦然。

图1 是不同信噪比情况下，三种算法的MSE数值大小比较。不难看出，信噪比的不断增大，使得三种算法的MSE数值均呈现一种下降的趋势。但从整体来说，改进后的GOMP算法与另外两种相比数值更小。而在任意相同的条件下，改进后的GOMP算法都比另外两种的MSE数值要低，凸显了性能的优越性。

图1　不同信噪比条件下三种算法的MSE性能比较

图2展示了三种算法在不同信噪比情况下的BER性能比较。可以看出，信噪比的不断增大，说明了信号干扰逐渐减小。因此三种算法的BER数值都会降低。改进的GOMP算法与另外两种对比来说，幅度更大，趋势更强，BER数值更小。由此说明，改进的GOMP算法具有更好的性能。

图2　不同信噪比条件下三种算法的BER性能比较

由于选择原子数量S的不断增大，每一次增大程度n的取值不同也对算法的性能产生影响。图3是改进的GOMP算法在S的数值大小相同而n的不同取值情况下，与OMP算法和GOMP算法在迭代次数方面的比较。从理论上来说，GOMP算法及其改进算法在选择原子的数目上面要多于OMP算法，所以说在这一方面上必然比OMP算法更有效率。由图中还可以看出，改进的GOMP算法对稀疏性具有良好的适应性，无论K值如何，算法都能很好地进行，而OMP算法在这一方面显示出了不足。对于n的取值来说，迭代的次数会随着n取值的增大而减小，但精确度并不会因此而降低。

图3　OMP算法和GOMP算法的比较

峰值信噪比(PSNR)是一种评价图像的客观标准，PSNR公式如下：

(11)

式中:X和X1分别代表原始信号和重构信号。

表1中显示了三种算法的PSNR值和运行时间。由表可以看出，三者的PSNR值相差不多，改进的算法可以很好地适应稀疏性，保证了重构的效果。在运行时间方面，GOMP算法及其改进算法较OMP算法都有大幅度的提高。验证了改进的算法在保证了重构效果的同时提高了效率。

表1　各算法PSNR值和运行时间

4　结　语

本文根据压缩感知理论知识以及信道的特性，提出了一种基于压缩感知改进的广义正交匹配追踪算法。此算法与先前的GOMP算法相比，可以实现自适应匹配，无需预先知道稀疏度，并且在原子选择方面进行了优化。由仿真实验的结果可以看出，提出的算法可以有效地提高重构信号的精度和效率，并在此基础上降低了传统算法的复杂度，使该算法可以更好地应用在信道估计领域中。

[1] 焦李成，杨淑媛，刘芳,等.压缩感知回顾与展望[J].电子学报，2011,39(7)：1651-1662.

[2] Donoho D L, Tsaig Y. Extensions of compressed sensing [J]. Signal Processing, 2006,86(3):533-548.

[3] Tropp J A, Gilbert A C. Signal Recovery from Random Measurements via Orthogonal Matching Pursuit [J]. IEEE Transactions on Information on Information Theory, 2007,53(12):4655-4666.

[4] 李然,干宗良,崔子冠,等.压缩感知图像重建算法的研究现状及其展望[J].电视技术,2013,37(19):192-196.

[5] Kim Seung-Jean, Koh K, Lustig M, et al. An Interior-Point Method for Large-Scale l1-Regularized Least Squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 606-617.

[6] 何雪云，宋荣方，周克琴. 基于压缩感知的OFDM系统系数信道估计新方法研究[J].南京邮电大学学报，2010,30(2)：60-65.

[7] Wang J, Kwon S, Shim B. Generalized orthogonal matching pursuit[J]. IEEE transactions on signal processing, 2012(60):6202-6216.

[8] Cotter S F, Rao B D. Sparse channel estimation via matching pursuit algorithm [J]. IEEE transactions on Communications, 2002,50(3):374-377.

[9] Karabulut G Z, Yongacoglu A. Sparse channel estimation using orthogonal matching pursuit algorithm[J]. IEEE 60th Vehicular Technology Conference, 2004. VTC2004-Fall. 2004.

[10] 甘伟，许录平，罗楠, 等.一种自适应压缩感知重构算法[J].系统工程及电子设计，2011,33(9)：1948-1953.

[11] 吕伟杰，陈霞，刘红珍.基于压缩感知的自适应匹配追踪优化[J].系统工程与电子技术，2015,37(5)：1201-1205.

[12] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.

[13] Fiqueiredo M A T, Nowak R D, Wright S J. Gradient projection for sqarse reconstruction: application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007,1(4):586-597.

[14] 甘伟，许录平，苏哲.一种压缩感知重构算法[J].电子与信息学报，2010,32(9)：2151-2155.

[15] 赵龙慧，潘乐炳，李宝清.OFDM稀疏信道估计中改进的OMP算法[J].计算机工程与设计，2015,36(7)：1701-1705.

[16] Davenport M A, Boufounos P T, Wakin M B, et al. Signal Processing With Compressive Measurements[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):445-460.

[17] 石光明，刘丹华，高大化.压缩感知理论及其研究进展[J].电子学报，2009,37(5)：1070-1081.

[18] 吕方旭, 张金成, 王泉,等. 基于傅里叶基的自适应压缩感知重构算法[J]. 北京航空航天大学学报, 2014, 40(4)：544-550.

[19] 朱延万，赵拥军，孙兵.一种改进的稀疏度自适应匹配追踪算法[J].信号处理，2012,28(1)：80-86.

[20] 王妮娜，桂冠，苏冰涛，等.基于压缩感知的MIMO-OFDM系统稀疏信道估计方法[J].电子科技大学学报，2013,42(1)：59-62.

[21] 赵龙慧，潘乐炳，李宝清.OFDM稀疏信道估计中改进的OMP算法[J].计算机工程与设计，2015,36(7)：1701-1705.

[22] 高西全，丁玉美.数字信号处理[M].西安：西安电子科技大学出版社，2008：84-87.

[23] 杨盼.压缩感知中改进的匹配追踪类算法研究[D].安徽：安徽大学，2015.