压缩感知重构算法在稀疏信号恢复中的应用

宋晓霞，李 勇

（山西大同大学数学与计算机科学学院，山西 大同 037009）

压缩感知重构算法在稀疏信号恢复中的应用

宋晓霞，李 勇

（山西大同大学数学与计算机科学学院，山西 大同 037009）

阐述了压缩感知理论产生的背景、基本原理和应用方式,研究了两类压缩感知重构算法的重构思想和方法,并将两类重构算法的典型算法正交匹配追踪和基追踪应用于稀疏信号的重构。结果表明：对于无噪观测和含较小噪声的观测，正交匹配追踪算法从重构频率和重构时间两方面显示出更好的性能。

压缩感知；重构算法；稀疏信号；贪婪追踪算法；凸松弛算法

由于Shannon/Nyquist采样定理能为模拟数据采样提供理论基础，因此它的提出是电子信息技术发展史上的一个重要里程碑事件。近半个世纪以来的数据采样均以Shannon/Nyquist采样定理为基础。然而，在诸如图像和视频处理、超宽带信号处理、核磁共振、空间探测、无线传感器网络等实际应用中，均需要两倍带宽的Nyquist采样率，但硬件设备的升级还是无法满足这些应用的需要。2006年D.Donoho、E.Candes和T.Tao等提出了一种被称为压缩感知（compressed sensing,CS）的新的信息获取理论[1-2]。由于CS框架下的数据处理体系能利用稀疏信号的本质特征，用低维投影来捕捉高维信号的特征，并通过重构算法从低维投影中提取出高维信号的信息，因此，在它问世的短短几年里就受到国内外学者的广泛关注和研究。

1 CS理论

CS理论是集采样与压缩为一体的信息获取理论。该理论[1-2]指出：在观测矩阵满足有限等距属性（restricted isometry property,RIP）的条件下，解码端能利用优化算法从O（k log（N/k））次观测以很高的概率来完全地恢复信号，其中N是信号的长度，k是该信号的稀疏度。具体原理[3-4]为：假设一个长度为N的信号X是稀疏的或可压缩的，并令Ψ表示其正交基或紧框架，如果将X的各分量投影到与变换基Ψ不相关的维数为M×N（M=N）的观测矩阵Φ上，则可得观测集合y∶M×1。那么信号X可以凭借这些观测y通过求解优化问题（1）而精确恢复。

令Θ=ΦΨT，如果对于任意一个稀疏度为k的信号X和常数δk∈（0，1），矩阵Θ满足式（2）,

则称Θ满足RIP属性。当Θ满足RIP属性或观测矩阵Φ和稀疏基Ψ不相关的条件下，CS能利用优化算法从少量的观测数据中以很高的概率完全地重构出原始信号。CS的应用可以总结为：首先在采样端对稀疏信号或可压缩信号以远低于Nyquist标准的采样频率进行信号采样的同时，对数据进行了一定程度的压缩，并进行存储，传输到终端用户后，在终端用户通过优化重建的方法从压缩观测中提取原始信号的信息。因此，重构算法和观测矩阵的构造是CS的两个基本问题。本文主要关注压缩感知的重构算法及其在稀疏信号恢复中的应用。

2 压缩感知重构算法

CS中的信号重构问题可以建模成一个最小化l0范数问题。然而，该最小化问题的求解属于NP难问题，需要找到信号分量中非零元素的所有组合，目前的方法均无法直接求解。为了逼近该问题的解，研究者们提出了系列求解的重构算法。它们基本可以归结为贪婪迭代匹配追踪算法和基于最小l1范数的凸松弛算法两大类[5]。

2.1 贪婪追踪算法

贪婪追踪算法（greedy pursuit，GP）的基本思想是：在每次迭代时，确定产生最大信号改进质量的一个或更多分量来选择一个局部最优解来逐步逼近原始信号。最早的贪婪追踪算法可追溯到1993年Mallat与Zhang提出的匹配追踪（matching pursuit，MP）算法[6]。该算法的思想可描述如下：在每一次迭代的过程中，先通过内积来计算相关性，再从过完备原子库里挑选出与信号匹配的最佳原子，并计算残差。然后继续挑选与残差最为匹配的原子，迭代重复上面的过程，信号最终可由选择出的原子线性表示。然而，由于MP算法在每一次迭代中只能够保证残差信号与当前选择的原子相互正交，而不能保证残差信号同当前原子与先前选择的原子所张成的子空间相互正交，因而降低了收敛速度。

为了获得更好的收敛效果，Tropp and Gilbert等提出了更有效的正交匹配追踪（orthogonalmatching pursuit,OMP）算法[7]。该算法采用了和MP算法相似的原子选择准则。不同的是，OMP算法要先对所选择的原子进行施密特正交化处理，然后将信号投影到那些正交原子构成的空间上，获得信号在各个已选出原子上的分量和余量，再继续对余量进行分解。由于每一步分解均要满足内积最大的条件，因此，余量将会随着分解步数的增加而迅速减小。

由于OMP算法的每一次迭代仅从原子库中选择一个原子，这使得残差信号能量的衰减速度较慢。另外，该算法依据给定的最大迭代次数来终止迭代的过程使得它需要更多的观测来保证信号的完全重构。为了加速残差信号能量的衰减速度和减少信号重构所需要的观测数据量，研究者们又给出了如下一系列追踪算法。

（1）分段正交匹配追踪（stagwise orthogonal matching pursuit，StOMP）算法。该算法每次匹配追踪时选出多个匹配原子而不是单个原子，减少了总的匹配次数。在每一次迭代中，选择所有与残差内积系数幅度大于给定阈值的原子，然后计算当前残差信号与所有选择原子的最小二乘逼近，将逼近误差作为新的残差继续迭代直到满足停机条件为止。StOMP算法将OMP算法进行一定程度的简化，提高了计算速度，但是由于其在每次迭代的过程中寻找的不一定是信号的最佳表示，降低了稀疏分解的精度，因此其分解速度是以逼近精度为代价的。

（2）正则正交匹配追踪（regularized orthogonal matching pursuit，ROMP）算法[8]。与StOMP算法相似的是，ROMP算法每次匹配追踪时也选出多个匹配原子而不是单个原子。与StOMP算法不同的是，ROMP算法不用阈值而用一个和目标向量相似的点积向量来选择原子。在ROMP算法中，先依据相关性进行原子的一次筛选，再求观测矩阵中各原子和余量之间的内积绝对值，并计算相关系数，依此将相关系数大的原子选入候选集合以便进行原子的二次筛选。然后采用正则化过程对原子进行二次筛选，将能量最大的一组相关系数对应的原子索引值加入支撑集。对未进入支撑集的那些原子，正则化过程可以保证它们的能量一定远小于被选入原子的能量。由此可见它是一种简单有效的原子筛选方法。ROMP算法是第一种有RIP界支撑的贪婪技术，它根据相关性增加了正则化后的二次筛选易获得更精确的解。但是，它需要估测信号的稀疏度。若信号的稀疏度估计过小将会导致多次迭代也无法达到迭代终止条件；若信号的稀疏度估计过大将导致不理想的重构效果。因此，信号稀疏度的估计是ROMP算法的关键问题。

（3）压缩采样匹配追踪（compressive sampling matching pursuit,CoSaMP）算法。该算法是一种引入回溯思想的压缩采样匹配追踪算法，它融入了组合算法的思想来保证速度并提供了严格的错误界。CoSaMP算法不仅从原子库中选择多个较相关的原子，而且从候选集中剔除多个原子，因而可以提高算法的效率。该算法引入了回溯思想，重构质量与线性规划算法相当，而且重构复杂度低，提供了更全面的理论保证。但是，它也是以估测信号稀疏度为前提的。对于稀疏度估测困难的

情况，可借用其它自适应的算法来实现。

2.2 凸松弛算法

除了贪婪追踪算法之外，CS的另一类重构算法是在一定条件下将求解式（3）的l0优化问题松弛为求解式（4）的l1凸优化问题。

由于l0模型的求解属于非凸问题的求解，而l1模型是与l0模型最接近的凸函数，因此很自然采用这种放松方式。并且一些文献已经证明当观测矩阵满足RIP属性时，l1模型的解与l0模型的解是等价的。

当观测被噪声污染的时候，可以通过求解下面的一些优化问题来重构信号。其中式（5）描述的模型为带有不等式约束的BP模型。该模型需要知道噪声的功率限，而对于实际情况，噪声的功率限通常是未知的。式（6）描述的模型为另一类替代的凸优化方法，常称为Dantzig Selector模型，当观测足够时，可通过求解该模型重构原始信号。然而，该优化方法需要噪声和稀疏度的先验知识。式（7）描述的模型为无约束的l1优化问题[9]，常称为BPDN模型，它通过放松重构误差幅度的硬约束为模型中软权值λ。式（8）描述的模型为LASSO模型[10]。当λ从0取到无穷的时候，BPDN模型的解等价于当q从无限到0时LASSO模型的解。上面的这些优化算法均基于相同的原理：在观测向量和稀疏基已知的条件下，用l1最小化来恢复稀疏逼近的非零系数的支撑集。通常在优化算法之后可以用去偏处理来减少重构误差。

3 两类算法在稀疏信号重构中的应用

该部分以稀疏信号作为测试信号，分别用两类重构算法从无噪和含噪两类压缩观测中提取信号。

3.1 无噪压缩观测

首先采用一个N=200，k=10的稀疏信号作为测试信号。对于M为3 k到7 k，间隔为k的高斯观测分别独立运行100次，采用OMP的贪婪匹配追踪算法和BP的凸松弛算法进行信号重构，重构结果如表1所示。在无噪情况下，重构误差小于1e-10，可以认为信号被重构。

从表1的数据能看出：OMP的贪婪匹配追踪算法更适合于从无噪观测中恢复稀疏信号。实际上，在上面的实验中，BP算法并不是不能重构信号，而是重构的精度达不到1e-10，仅能达到1e-4。

3.2 含噪压缩观测

假设对上面的信号进行高斯观测后，又被均值为0，标准差为0.01的高斯噪声污染，采用OMP的贪婪匹配追踪算法和BP的凸松弛算法进行信号重构，重构结果如表2所示。在此种含噪情况下，重构误差小于0.02，认为信号被重构。

从表2的数据能看出：OMP的贪婪匹配追踪算法更适合于小噪声的压缩观测。对于噪声较大的压缩观测，需要事先估测重构误差，再进行实验验证，将在后续的工作中继续研究和探讨。

4 结束语

本文介绍了压缩感知理论产生的背景，基本原理和应用方式。对压缩感知重构算法的重要问题，进行了分析和总结。最后，将两类重构算法的代表性算法OMP和BP应用于稀疏信号的重构。结果表明：对于无噪观测和含较小噪声的观测，OMP算法从重构频率和重构时间两方面显示出更好的性能。对于观测噪声较大的情况，需要通过估测噪声后进行深入研究。

表1 OMP和BP算法从无噪观测中恢复信号的重构结果

表2 OMP和BP算法从含噪观测中恢复信号的重构结果

[1]Donoho D.Compressed sensing[J].IEEE Transaction.on Information Theory,2006,52（4）：1289-1306.

[2]Candes E,Wakin M.An introduction to compressive sampling[J].IEEE Signal Processing Magazine,2008,25（2）：21-30.

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

[4]宋晓霞，石光明.低冗余的压缩感知观测[J].西安电子科技大学学报，2012,39（4）：144-148.

[5]Tropp J，Wright S.Computationalmethods for sparse solution of linear inverse problems[J].Proceedings of the IEEE,2010,98（6）：948-958.

[6]Mallat S，Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transaction on Signal Processing,1993,41（12）：3397-3415.

[7]Tropp J，Gilbert A.Signal recovery from random measurements via orthogonalmatching pursuit[J].IEEE Transaction on Information Theory,2007,53（12）：4655-4666.

[8]Needell D,Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of ComputationalMathematics,2009,9（3）：317-334.

[9]Chen S,Donoho D,Saunders M.Atomic decomposition by basis pursuit[J].SIAMJournal on Scientific Computing,1999,20（1）：33 -61.

[10]TibshiraniR.Regression shrinkage and selection via the lasso[J].Journalof the Royal Statistical Society,1996,58（1）：267-288.

Abstract:To improve the security and success rate of transaction in B2C E-commerce and reflect the credibility of customer objectively,a trust evaluation mechanism is proposed base on cloud model theory.It aims to analyze the factors which affect online perception trust in B2C E-commerce from historical transaction evaluation,site popularity,commodity price,Logistics and services. By creating definition of the trust cloud,the qualitative description and quantitative representation of trust is unified.A new trust evaluationmodel is established based on algorithm of converse trust cloud generator and trustmerging and algorithm of similarity.At last,by the result of calculation combining with subjective inference decision-making of trust is realized.The results of simulation experiments show that the trustevaluationmodel is valid and rational.

Key words:B2C E-commerce；trust evaluation；cloud model；trust cloud

〔责任编辑 高 海〕

App lication of Sparse Signal Restoration via Reconstruction Algorithm s of Compressed Sensing

SONG Xiao-xia,LIYong
（School ofMathematics and Computer Science,ShanxiDatong University,Datong Shanxi,037009）

This paper illustrates the background,the basic principle and application of compressed sensing theory.Two kinds of reconstruction algorithms are studied from the idea and method.And then typical algorithms including orthogonalmatching pursuit and basis pursuit are applied to the reconstruction of sparse signals.The results suggest that orthogonalmatching pursuit algorithm shows better performances from the two aspects of reconstruction frequency and time for compressivemeasurements without noise or with small noise.

compressed sensing；reconstruction algorithm；sparse signal；greedy pursuit algorithm；convex relaxation algorithm

〔责任编辑 高 海〕

（School ofMathematics and Computer Science,ShanxiDatong University,Datong Shanxi,037009）

TN911

A

2013-08-01

国家自然科学基金资助项目[61307121]

宋晓霞（1975-），女，山西广灵人，博士，副教授,研究方向：压缩感知与无线传感器网络。

1674－0874（2013）05－0004－06