基于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.

（責任編輯：孫 娟）