基于QR分解的OMPR算法快速实现

杨成竹 李智

摘要：正交匹配追踪算法（Orthogonal Matching Pursuit）因其理论分析完备，且能够快速实现，从而成为解决压缩感知重构问题的重要工具之一。OMPR（Orthogonal Matching Pursuit with Replacement）算法是OMP算法的加强，在理论分析和数值试验中均是性能最卓越的贪婪追踪算法之一。然而OMPR算法在每次迭代中仍然需要利用矩阵求逆运算，时间代价巨大。利用矩阵的QR分解和Givens变换的相关性质，提出OMPR-QR算法。理论分析表明，OMPR-QR算法在数学上完全等价于OMPR算法，且仿真实验表明，在大数据量下其每次迭代的时间代价远远小于OMPR。

关键词：压缩感知；正交匹配追踪；QR分解；Givens变换

DOIDOI：10.11907/rjdk.161595

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）005-0044-03

另一个常见策略是利用贪婪追踪算法（Greedy Pursuit）。贪婪追踪算法将测量矩阵A看作是一个字典，A中所有列向量看作是原子库。贪婪追踪算法的基本思想为：每次在原子库中找到一个或多个与残差最相似的原子进入候选集，并利用候选集中原子构建稀疏逼近并更新残差，继续该过程直到算法达到终止条件。常见贪婪追踪算法包括正交匹配追踪（Orthogonal Matching Pursuit，OMP）、子空间追踪（Subspace Pursuit，SP）、压缩采样匹配追踪（Compressed Sampling Matching Pursuit，CoSaMP）、OMPR算法等[2，4]。其中，OMPR算法结构简单、理论保证强大、数值性能良好，是应用最为广泛的贪婪追踪算法之一。然而，OMPR算法每一次迭代均涉及求逆运算，时间代价巨大。

1 OMPR算法

贪婪重构算法大体可分为两类：一步算法和二步算法。一步贪婪追踪算法在每次迭代中先估计支撑集，然后利用最小二乘估计支撑集上的信号分量。典型的一步算法包括OMP、ROMP、MOMP等[5]。一步算法的缺陷在于，某次迭代中一旦支撑集估计产生错误，支撑集将一直保持该错误而无法得到更正；二步贪婪追踪算法在每次迭代中先估计一个扩张支撑集，在扩张支撑集上利用最小二乘估计扩张支撑集上的信号分量，然后利用一定规则将扩张支撑集删减到与信号支撑集同等大小，在删减的支撑集上再利用一次最小二乘估计信号分量。典型的二步追踪算法包括OMPR、SP、CoMaSP。OMPR算法相当于将OMP算法扩张为二步算法。本文将定义一个有用的算子，然后给出OMPR算法框架。

分析可知，OMPR-QR算法单次迭代的时间代价为Ο（KM+N）+Ο（K2）+O（KM）+Ο（KN）=Ο（KN），远远小于OMPR算法单次迭代所需时间代价Ο（MN+K3）。

3 实验仿真与结果分析

为了比较OMPR-QR算法与OMPR算法，本文设置了两组试验。第1组试验固定信号长度N与采样次数M，在不同的稀疏度K下，比较两种算法准确重构原始稀疏信号的概率；第2组试验探讨在固定信号长度N与采样次数M，在不同的稀疏度K下，两种算法精确重构所消耗的时间。在每组试验中，测量矩阵A均由Matlab随机生成高斯矩阵后，将其列单位化得到，原始稀疏信号x的支撑集和非零值均是随机生成而得，测量信号由y=Ax得到，最大迭代次数设为测量次数M。

在第1组试验中，将信号长度设置为N=1 000，M=100，K=10，11...，35。在每种稀疏度下，每种算法重复1000次试验。当重构信号x#满足||x#-x||2≤10-6时，则认为恢复成功。在每种稀疏度下，精确重构的概率被定义为：η=成功恢复的次数试验总次数。两种算法的成功恢复概率对比如图1所示。

由图1知，OMPR算法与OMPR-QR算法在较小的稀疏度时均能精确重构原始信号，且两个算法在稀疏度小于13时均能实现100%精确重构，在稀疏度大于13时，均不能保证100%重构。这也从侧面表明OMPR与OMPR-QR在数学上是等价的。

由图2可知，在稀疏度较小时，OMPR算法与OMPR-QR算法的运行时间几乎相同。当稀疏度增大时，OMPR算法每次迭代的时间代价Ο（MN+K3）由求逆运算产生，算法运行时间急剧增加。而OMPR-QR算法克服了OMPR算法求逆运算的影响，算法运行时间随稀疏度的增大缓慢增加，这与OMPR-QR算法的时间代价Ο（KN）相吻合。在数据量很大的情况下，OMPR算法的运行时间是OMPR-QR算法运行时间的数十倍。

4 结语

本文利用矩阵的QR分解，提出了OMPR-QR算法。理论分析表明，OMPR-QR算法与OMPR算法在数学上完全等价，但其单次迭代的时间代价远远小于OMPR算法。仿真实验表明，OMPR-QR算法在低稀疏度条件下能100%精确重构稀疏信号，在大数据量情况下，算法运行时间远远少于OMPR算法。利用本文算法思想，还可以对其它具有回溯思想的贪婪追踪算法进行加速。

参考文献：

[1]DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory，2006，52（4）： 1289-1306.

[2]FOUCART S，RAUHUT H.A mathematical introduction to compressive sensing[M].Basel： Birkhauser，2013：25-100.

[3]JAIN P，TEWARI A，DHILLON I S.Orthogonal matching pursuit with replacement[C].Advances in Neural Information Processing Systems，2011：1215-1223.

[4]KIM S J，KOH K，LUSTIG M，et al.An interior-point method for large-scale regularized least squares[J].Selected Topics in Signal Processing，2007，1（4）： 606-617.

[5]BLUMENSATH，M E DAVIES，G RILLING.Greedy algorithms for compressed sensing[M].Cambridge：Cambridge University Press，2012.

[6]蔡大用，峰杉.现代科学计算[M].北京：科学出版社，2000.

[7]STURM，BOB L，MADS G CHRISTENSEN.Comparison of orthogonal matching pursuit implementations[J].Conference article in Journal，2012，27（8）：220-224.

（责任编辑：孙 娟）