基于QR分解的OMPR算法快速實(shí)現(xiàn)

楊成竹 李智

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

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

DOIDOI：10.11907/rjdk.161595

中圖分類號(hào)：TP312

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

另一個(gè)常見策略是利用貪婪追蹤算法（Greedy Pursuit）。貪婪追蹤算法將測(cè)量矩陣A看作是一個(gè)字典，A中所有列向量看作是原子庫(kù)。貪婪追蹤算法的基本思想為：每次在原子庫(kù)中找到一個(gè)或多個(gè)與殘差最相似的原子進(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)簡(jiǎn)單、理論保證強(qiáng)大、數(shù)值性能良好，是應(yīng)用最為廣泛的貪婪追蹤算法之一。然而，OMPR算法每一次迭代均涉及求逆運(yùn)算，時(shí)間代價(jià)巨大。

1 OMPR算法

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

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

3 實(shí)驗(yàn)仿真與結(jié)果分析

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

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

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

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

4 結(jié)語(yǔ)

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