楊成竹 李智

摘要：正交匹配追蹤算法（Orthogonal Matching Pursuit）因其理論分析完備，且能夠快速實現(xiàn)，從而成為解決壓縮感知重構(gòu)問題的重要工具之一。OMPR（Orthogonal Matching Pursuit with Replacement）算法是OMP算法的加強(qiáng)，在理論分析和數(shù)值試驗中均是性能最卓越的貪婪追蹤算法之一。然而OMPR算法在每次迭代中仍然需要利用矩陣求逆運(yùn)算，時間代價巨大。利用矩陣的QR分解和Givens變換的相關(guān)性質(zhì)，提出OMPR-QR算法。理論分析表明，OMPR-QR算法在數(shù)學(xué)上完全等價于OMPR算法，且仿真實驗表明，在大數(shù)據(jù)量下其每次迭代的時間代價遠(yuǎn)遠(yuǎn)小于OMPR。

關(guān)鍵詞：壓縮感知；正交匹配追蹤；QR分解；Givens變換

DOIDOI：10.11907/rjdk.161595

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2016）005-0044-03

另一個常見策略是利用貪婪追蹤算法（Greedy Pursuit）。貪婪追蹤算法將測量矩陣A看作是一個字典，A中所有列向量看作是原子庫。貪婪追蹤算法的基本思想為：每次在原子庫中找到一個或多個與殘差最相似的原子進(jìn)入候選集，并利用候選集中原子構(gòu)建稀疏逼近并更新殘差，繼續(xù)該過程直到算法達(dá)到終止條件。常見貪婪追蹤算法包括正交匹配追蹤（Orthogonal Matching Pursuit，OMP）、子空間追蹤（Subspace Pursuit，SP）、壓縮采樣匹配追蹤（Compressed Sampling Matching Pursuit，CoSaMP）、OMPR算法等[2，4]。其中，OMPR算法結(jié)構(gòu)簡單、理論保證強(qiáng)大、數(shù)值性能良好，是應(yīng)用最為廣泛的貪婪追蹤算法之一。然而，OMPR算法每一次迭代均涉及求逆運(yùn)算，時間代價巨大。

1 OMPR算法

貪婪重構(gòu)算法大體可分為兩類：一步算法和二步算法。一步貪婪追蹤算法在每次迭代中先估計支撐集，然后利用最小二乘估計支撐集上的信號分量。典型的一步算法包括OMP、ROMP、MOMP等[5]。一步算法的缺陷在于，某次迭代中一旦支撐集估計產(chǎn)生錯誤，支撐集將一直保持該錯誤而無法得到更正；二步貪婪追蹤算法在每次迭代中先估計一個擴(kuò)張支撐集，在擴(kuò)張支撐集上利用最小二乘估計擴(kuò)張支撐集上的信號分量，然后利用一定規(guī)則將擴(kuò)張支撐集刪減到與信號支撐集同等大小，在刪減的支撐集上再利用一次最小二乘估計信號分量。典型的二步追蹤算法包括OMPR、SP、CoMaSP。OMPR算法相當(dāng)于將OMP算法擴(kuò)張為二步算法。本文將定義一個有用的算子，然后給出OMPR算法框架。

分析可知，OMPR-QR算法單次迭代的時間代價為Ο（KM+N）+Ο（K2）+O（KM）+Ο（KN）=Ο（KN），遠(yuǎn)遠(yuǎn)小于OMPR算法單次迭代所需時間代價Ο（MN+K3）。

3 實驗仿真與結(jié)果分析

為了比較OMPR-QR算法與OMPR算法，本文設(shè)置了兩組試驗。第1組試驗固定信號長度N與采樣次數(shù)M，在不同的稀疏度K下，比較兩種算法準(zhǔn)確重構(gòu)原始稀疏信號的概率；第2組試驗探討在固定信號長度N與采樣次數(shù)M，在不同的稀疏度K下，兩種算法精確重構(gòu)所消耗的時間。在每組試驗中，測量矩陣A均由Matlab隨機(jī)生成高斯矩陣后，將其列單位化得到，原始稀疏信號x的支撐集和非零值均是隨機(jī)生成而得，測量信號由y=Ax得到，最大迭代次數(shù)設(shè)為測量次數(shù)M。

在第1組試驗中，將信號長度設(shè)置為N=1 000，M=100，K=10，11...，35。在每種稀疏度下，每種算法重復(fù)1000次試驗。當(dāng)重構(gòu)信號x#滿足||x#-x||2≤10-6時，則認(rèn)為恢復(fù)成功。在每種稀疏度下，精確重構(gòu)的概率被定義為：η=成功恢復(fù)的次數(shù)試驗總次數(shù)。兩種算法的成功恢復(fù)概率對比如圖1所示。

由圖1知，OMPR算法與OMPR-QR算法在較小的稀疏度時均能精確重構(gòu)原始信號，且兩個算法在稀疏度小于13時均能實現(xiàn)100%精確重構(gòu)，在稀疏度大于13時，均不能保證100%重構(gòu)。這也從側(cè)面表明OMPR與OMPR-QR在數(shù)學(xué)上是等價的。

由圖2可知，在稀疏度較小時，OMPR算法與OMPR-QR算法的運(yùn)行時間幾乎相同。當(dāng)稀疏度增大時，OMPR算法每次迭代的時間代價Ο（MN+K3）由求逆運(yùn)算產(chǎn)生，算法運(yùn)行時間急劇增加。而OMPR-QR算法克服了OMPR算法求逆運(yùn)算的影響，算法運(yùn)行時間隨稀疏度的增大緩慢增加，這與OMPR-QR算法的時間代價Ο（KN）相吻合。在數(shù)據(jù)量很大的情況下，OMPR算法的運(yùn)行時間是OMPR-QR算法運(yùn)行時間的數(shù)十倍。

4 結(jié)語

本文利用矩陣的QR分解，提出了OMPR-QR算法。理論分析表明，OMPR-QR算法與OMPR算法在數(shù)學(xué)上完全等價，但其單次迭代的時間代價遠(yuǎn)遠(yuǎn)小于OMPR算法。仿真實驗表明，OMPR-QR算法在低稀疏度條件下能100%精確重構(gòu)稀疏信號，在大數(shù)據(jù)量情況下，算法運(yùn)行時間遠(yuǎn)遠(yuǎn)少于OMPR算法。利用本文算法思想，還可以對其它具有回溯思想的貪婪追蹤算法進(jìn)行加速。

參考文獻(xiàn)：

[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]蔡大用，峰杉.現(xiàn)代科學(xué)計算[M].北京：科學(xué)出版社，2000.

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

（責(zé)任編輯：孫 娟）