基于隨機(jī)支撐挑選的廣義正交匹配追蹤算法

徐志強(qiáng)，蔣鐵鋼，楊立波

（廣東科技學(xué)院機(jī)電工程系，廣東東莞523083）

（?通信作者電子郵箱jiangtiegang5201@163.com）

0 引言

作為一種新的亞采樣技術(shù)，壓縮感知（Compressed Sensing，CS）理論［1］以其以遠(yuǎn)低于香農(nóng)-奈奎斯特采樣定理所要求的采樣數(shù)重構(gòu)原始信號(hào)的特點(diǎn)，在過(guò)去的幾年引起了研究人員的廣泛關(guān)注。CS 理論自提出以來(lái)，在信號(hào)處理、圖像處理、人工智能、無(wú)線(xiàn)通信等領(lǐng)域得到了廣泛的應(yīng)用［2］。CS理論的主要思想是在已知信號(hào)的稀疏先驗(yàn)信息情況下，將稀疏信號(hào)投影到低維空間，再通過(guò)求解一個(gè)稀疏約束的優(yōu)化問(wèn)題來(lái)重建原信號(hào)。根據(jù)這一思想，壓縮感知的研究范圍主要包括信號(hào)的稀疏表示、測(cè)量矩陣的設(shè)計(jì)和重構(gòu)算法的設(shè)計(jì)。

重構(gòu)算法作為影響信號(hào)重建性能的關(guān)鍵因素，吸引了眾多學(xué)者的研究，近年來(lái)已提出了一大批有效的重構(gòu)算法。這些算法主要包括基于?1范數(shù)的凸優(yōu)化算法和基于?0范數(shù)的貪婪追蹤算法。凸優(yōu)化類(lèi)算法將稀疏約束的欠定問(wèn)題轉(zhuǎn)化為凸問(wèn)題來(lái)求解，如基追蹤（Basis Pursuit，BP）方法［3］、內(nèi)點(diǎn)法［4］、梯 度 投 影 法（Gradient Projection for Sparse Reconstruction，GPSR）［5］等。凸優(yōu)化類(lèi)算法具有良好的理論保證和重構(gòu)性能，但是其復(fù)雜度很高，在求解大規(guī)模問(wèn)題時(shí)并不實(shí)際。基于?0范數(shù)的貪婪追蹤算法則是通過(guò)迭代地尋找待恢復(fù)信號(hào)的正確支撐，并以此支撐來(lái)構(gòu)造原信號(hào)的逼近信號(hào)，直到滿(mǎn)足一定的誤差條件。這類(lèi)算法復(fù)雜度較低，算法操作簡(jiǎn)單，但是其重構(gòu)精度表現(xiàn)不如凸優(yōu)化類(lèi)算法。經(jīng)典的貪婪算法包括正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法［6］、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）算 法［7］、子 空 間 追 蹤（Subspace Pursuit，SP）算法［8］、壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）算 法［9］和 廣 義 正 交 匹 配 追 蹤（Generalized Orthogonal Matching Pursuit，GOMP）算法［10］等。這些算法通過(guò)在每次迭代中挑選一個(gè)或多個(gè)原子來(lái)逐步逼近原始信號(hào)，具有較強(qiáng)的理論保證。然而大多數(shù)實(shí)際應(yīng)用中信號(hào)的稀疏度不可知，這限制了上述算法的應(yīng)用，為了解決這一問(wèn)題，文獻(xiàn)［11］提出了稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）算法，該算法將信號(hào)的重構(gòu)過(guò)程劃分為具有固定步長(zhǎng)的幾個(gè)階段，并且無(wú)需稀疏度先驗(yàn)信息。文獻(xiàn)［12］在共軛梯度迭代硬閾值算法［13］的基礎(chǔ)上，結(jié)合SP 算法的回溯思想，提出了基于回溯的共軛梯度硬閾值迭代（Backtracking-based Conjugate Gradient Iterative Hard Thresholding，BCGIHT）算法，該算法結(jié)合了硬閾值類(lèi)算法支撐集挑選的優(yōu)勢(shì)和貪婪追蹤類(lèi)算法系數(shù)更新精確的優(yōu)勢(shì)，在一定程度上減少了算法的迭代次數(shù)。

作為貪婪算法中具有代表性的一種算法，GOMP 算法在迭代過(guò)程中引入回溯操作，允許支撐集中的元素個(gè)數(shù)大于稀疏度，這一方面加大了稀疏系數(shù)更新的計(jì)算量，另一方面影響了殘差的更新。針對(duì)這一問(wèn)題，文獻(xiàn)［14］提出一種支撐回溯的GOMP 算法（BGOMP），該算法確保了每次迭代中支撐集的大小不超過(guò)稀疏度，在一定程度上降低了算法的復(fù)雜度。針對(duì)GOMP 算法重構(gòu)精度不高的問(wèn)題，文獻(xiàn)［15］提出了一種多候選集GOMP 算法，該算法在迭代初始設(shè)置了多個(gè)候選支撐集，并迭代地將新匹配的原子加入到候選集中，最后挑選出殘差能量最小的候選集作為支撐集，使算法的重構(gòu)精度有了較大提高，但是同時(shí)也加大了其算法復(fù)雜度。

最近，受隨機(jī)梯度（Stochastic Gradient）方法的影響，針對(duì)稀疏約束優(yōu)化問(wèn)題，文獻(xiàn)［16］提出了隨機(jī)硬閾值迭代（Stochastic Iterative Hard Thresholding，StoIHT）算法和隨機(jī)梯度匹配追蹤（Stochastic Gradient Matching Pursuit，StoGraMP）算法，StoIHT 算法與IHT 算法的不同之處在于前者在每次迭代中只隨機(jī)地計(jì)算了部分梯度，而后者則需計(jì)算全部梯度。與之類(lèi)似的有最近提出的隨機(jī)壓縮采樣匹配追蹤算法［17］（Stochastic Compressive Sampling Matching Pursuit，StoCoSaMP）和 隨 機(jī) 梯 度 追 蹤（Stochastic Gradient Pursuit，SGP）算法［18］。這類(lèi)算法在求解大規(guī)模問(wèn)題時(shí)能大幅減少計(jì)算量，但是由于梯度信息的不全面，該類(lèi)算法通常需要比具有完整梯度信息的算法需要更多的迭代次數(shù)。

本文針對(duì)GOMP 算法在每次迭代中需要對(duì)測(cè)量矩陣和殘差進(jìn)行匹配計(jì)算，導(dǎo)致其算法復(fù)雜度高、重構(gòu)時(shí)間長(zhǎng)的問(wèn)題，引入隨機(jī)支撐挑選的思想，提出了一種基于隨機(jī)支撐挑選的廣義正交匹配追蹤（Stochastic Support Selection based Generalized Orthogonal Matching Pursuit，StoGOMP）算法。該算法在迭代過(guò)程中根據(jù)給定的概率來(lái)判斷是否需要進(jìn)行匹配計(jì)算，如果判斷為需要進(jìn)行匹配計(jì)算，則按照GOMP算法的流程繼續(xù)執(zhí)行；如果判斷為不需要進(jìn)行匹配計(jì)算，則生成一個(gè)隨機(jī)支撐集作為候選集。這種方式在一定程度上考慮了單次迭代的計(jì)算復(fù)雜度與迭代總次數(shù)的相互影響，在選擇合適的初始概率時(shí)，能有效降低算法的計(jì)算量。

1 壓縮感知理論

對(duì)于長(zhǎng)度為N × 1 的信號(hào)h ∈RN×1，它可以表示成一組正交基的線(xiàn)性組合，即:

如果其表示系數(shù)x 中僅有K(K ?N)個(gè)元素的絕對(duì)值大于零，則稱(chēng)信號(hào)h 在基ψ ={ψi}Ni=1上是K-稀疏的。這里ψi表示基矩陣ψ ∈RN×N的列原子。在壓縮感知理論中，稀疏信號(hào)通過(guò)一個(gè)大小為M × N(M ?N)的采樣矩陣Φ 進(jìn)行采樣，得到測(cè)量值向量y ∈RM×1，這一過(guò)程可以描述為:

其中:A = Φψ稱(chēng)為測(cè)量矩陣。由式（2）可知，測(cè)量值向量的維度遠(yuǎn)低于信號(hào)的維度，因此式（2）是一個(gè)欠定問(wèn)題，有無(wú)窮多個(gè)解，這意味著很難從測(cè)量值向量y中重構(gòu)出稀疏系數(shù)x。由文獻(xiàn)［2］可知，當(dāng)測(cè)量矩陣滿(mǎn)足有限等距限制（Restricted Isometry Property，RIP）時(shí)，重構(gòu)x的過(guò)程就等價(jià)于求解如下?0范數(shù)最小化問(wèn)題:

其中:||?||0表示x 中非零元素的個(gè)數(shù)。有限等距性質(zhì)可以描述成:

其中:δK表示對(duì)于所有x 滿(mǎn)足式（4）的最小常數(shù)。當(dāng)有限等距常數(shù)δK≤ 2 - 1 時(shí)，式（3）可以轉(zhuǎn)化為如下?1范數(shù)最小化問(wèn)題:

其中:||?||1為向量的?1范數(shù)，表示向量元素的絕對(duì)值之和。文獻(xiàn)［2］表明，對(duì)于給定的稀疏基，當(dāng)采樣矩陣為服從高斯分布的隨機(jī)矩陣時(shí)，測(cè)量矩陣在很大概率上滿(mǎn)足RIP條件。

2 基于隨機(jī)支撐挑選的GOMP算法

2.1 算法描述

StoGOMP 算法（具體見(jiàn)算法1）的輸入?yún)?shù)包括測(cè)量矩陣、測(cè)量向量、稀疏度、每次迭代挑選的索引數(shù)、給定的誤差閾值和給定的概率值。在迭代過(guò)程中，StoGOMP 算法的迭代主體為步驟2～7:步驟2 在區(qū)間［0，1］內(nèi)隨機(jī)挑選一個(gè)值p，將該值與輸入的概率Pr進(jìn)行比較；步驟3中，若p小于Pr，則在測(cè)量矩陣的列原子中隨機(jī)挑選S 個(gè)原子的位置用于合并支撐集；步驟4 中，若p 大于Pr，則在測(cè)量矩陣與殘差的內(nèi)積中挑選絕對(duì)值最大的S個(gè)元素的位置用于合并支撐集；步驟5中將當(dāng)前迭代中選擇的支撐位置合并到前一次迭代的支撐集中，將合并的支撐集作為候選支撐集，這類(lèi)似于子空間追蹤算法中的支撐集回溯操作；步驟6 使用最小二乘法來(lái)更新稀疏系數(shù)，可以起到去偏作用，使更新結(jié)果更加精確；步驟7 更新殘差。步驟2～4是StoGOMP 算法與原GOMP 算法不同的地方。由文獻(xiàn)［10］可知，GOMP 算法的計(jì)算量主要集中在測(cè)量矩陣與殘差的內(nèi)積計(jì)算上。StoGOMP 算法采用隨機(jī)的方式挑選支撐集，一定程度上減少了匹配計(jì)算的次數(shù)，然而隨機(jī)挑選支撐由于存在很大的不確定性，使迭代過(guò)程中某些支撐被反復(fù)選擇，導(dǎo)致迭代次數(shù)增加。為了控制支撐集挑選的精確性和迭代計(jì)算量，StoGOMP 算法將是否需要計(jì)算測(cè)量矩陣與殘差的內(nèi)積劃分到了2 個(gè)概率區(qū)間，可以根據(jù)預(yù)先設(shè)定的概率值來(lái)進(jìn)行決策，從而起到平衡計(jì)算量與迭代次數(shù)的作用。

2.2 StoGOMP算法性能分析

以下分三種情況對(duì)StoGOMP算法進(jìn)行分析:

第一種情況:Pr= 1。此時(shí)StoGOMP 算法退化為GOMP算法，根據(jù)文獻(xiàn)［10］可知，對(duì)于高斯隨機(jī)采樣矩陣，StoGOMP算法的采樣數(shù)僅需要M = O(K log (N/K))個(gè)，并且具有與GOMP算法相同的理論保證。

第二種情況:Pr= 0。此時(shí)，StoGOMP 算法無(wú)需計(jì)算測(cè)量矩陣與殘差的內(nèi)積，完全隨機(jī)地從測(cè)量矩陣的列原子中挑選支撐集，這大大減少了算法的計(jì)算量。然而，每次迭代中隨機(jī)挑選支撐集可能會(huì)導(dǎo)致某些原子在當(dāng)前迭代中被選擇，而在下一次迭代中又被丟棄，導(dǎo)致支撐被反復(fù)選擇，增加算法的迭代次數(shù)。由文獻(xiàn)［18］可知，在有限迭代次數(shù)內(nèi)，即使Pr= 0，算法最終能找到正確的支撐集。

第三種情況:0 ＜Pr＜1。此時(shí)StoGOMP 算法需要計(jì)算測(cè)量矩陣跟殘差的內(nèi)積的概率為1- Pr，這意味著Pr的大小影響著算法的計(jì)算復(fù)雜度。同時(shí)，隨機(jī)挑選的支撐并不精確，導(dǎo)致迭代次數(shù)過(guò)多。因此，計(jì)算復(fù)雜度和迭代次數(shù)需要通過(guò)控制Pr的大小來(lái)調(diào)節(jié)。

算法復(fù)雜度分析:GOMP 算法中，測(cè)量矩陣與殘差的內(nèi)積計(jì)算量約為2MN 次乘法運(yùn)算，稀疏系數(shù)估計(jì)的計(jì)算量約為4S2M 次乘法運(yùn)算，殘差更新計(jì)算量大約為2SM 次乘法運(yùn)算。設(shè)GOMP算法迭代次數(shù)為k，則重構(gòu)過(guò)程總的計(jì)算量可以估計(jì)為k(MN +(4S + 2)SM)次乘法運(yùn)算。StoGOMP 算法中，設(shè)迭代次數(shù)為j，計(jì)算測(cè)量矩陣與殘差的概率為1- Pr，則其總的算法復(fù)雜度可以估計(jì)為j(1- Pr)(MN +(4S2+ 2S)M)次乘法運(yùn)算。從GOMP算法和StoGOMP算法的復(fù)雜度對(duì)比可以看出概率值Pr的選擇是決定StoGOMP算法復(fù)雜度的關(guān)鍵因素。

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

本章使用隨機(jī)高斯信號(hào)和數(shù)字圖像作為測(cè)試信號(hào)，對(duì)比了OMP 算法、SP 算法、CoSaMP 算法、GOMP 算法、BGOMP 算法和StoGOMP 算法的重構(gòu)性能。所有實(shí)驗(yàn)均在Intel（i5-7500，8 GB 內(nèi)存）平臺(tái)上完成，所使用的仿真軟件為Matlab2018B。

3.1 隨機(jī)高斯信號(hào)重構(gòu)實(shí)驗(yàn)

圖1 不同稀疏度情況下，GOMP算法和StoGOMP算法在不同采樣數(shù)情況下的重構(gòu)成功率比較(S = K 2，Pr = 0.5)Fig. 1 Comparison of reconstruction success rates of GOMP algorithm and StogoMP algorithm under different sparsity conditions(S = K 2，Pr = 0.5)

為了驗(yàn)證StoGOMP算法的重構(gòu)精度，以長(zhǎng)度為400 × 1的高斯信號(hào)為測(cè)試信號(hào)，大小為100 × 400的隨機(jī)高斯矩陣作為采樣矩陣，稀疏度設(shè)置為K = 24，每次迭代挑選的索引數(shù)設(shè)置為［5，10，15］，Pr= 0.3。圖2 記錄了平均重構(gòu)誤差與迭代次數(shù)的關(guān)系。由圖2可知:在迭代次數(shù)小于20次時(shí)，GOMP 算法與BGOMP 算法收斂速度相當(dāng)，且都比StoGOMP 算法快；當(dāng)?shù)螖?shù)大于20時(shí)，GOMP算法的重構(gòu)誤差下降緩慢，誤差曲線(xiàn)基本保持水平，而StoGOMP 算法的誤差曲線(xiàn)還有明顯下降。這說(shuō)明在迭代后期，StoGOMP 算法在重構(gòu)精度上具有優(yōu)勢(shì)。這是因?yàn)樵诘笃贕OMP 算法挑選的原子基本不再變化，因此其重構(gòu)誤差變化非常緩慢，而在StoGOMP 算法中，在某些步驟可能有新原子的加入，這些新原子的索引構(gòu)成的支撐集可能是比GOMP 算法得到的支撐集更優(yōu)的支撐集，其重構(gòu)誤差因此更小。

圖2 不同算法平均重構(gòu)誤差與迭代次數(shù)的關(guān)系Fig. 2 Relationship between average reconstruction error and number of iterations of different algorithms

為了驗(yàn)證給定概率Pr對(duì)StoGOMP 算法重構(gòu)性能的影響，采用長(zhǎng)度為N = 200，500，1 000，2 000 的高斯信號(hào)作為測(cè)試信號(hào)，稀疏度設(shè)置為K = 40，100，200，400，采樣數(shù)設(shè)置為M =N 2。從圖3 所示的實(shí)驗(yàn)結(jié)果可看出，當(dāng)Pr接近0 或1 時(shí)，StoGOMP算法的重構(gòu)成功率最低，當(dāng)0.2 ＜Pr＜0.8時(shí)，重構(gòu)成功率保持在較高的水平，這說(shuō)明Pr在區(qū)間［0.2，0.8］內(nèi)取值比較好。

圖3 重構(gòu)成功率與設(shè)定概率Pr的關(guān)系Fig. 3 Relationship between reconstruction success rate and set probability Pr

為了驗(yàn)證StoGOMP 算法的重構(gòu)性能，與其他常見(jiàn)貪婪追蹤類(lèi)算法進(jìn)行重構(gòu)對(duì)比實(shí)驗(yàn)。待測(cè)試高斯信號(hào)長(zhǎng)度為256 ×1，采樣矩陣大小為128× 256的隨機(jī)高斯矩陣，稀疏度設(shè)置為8～80，間隔為4。從圖4所示的實(shí)驗(yàn)結(jié)果中可看出，在Pr= 0.5時(shí)，在重構(gòu)成功率方面，StoGOMP 算法的表現(xiàn)要優(yōu)于其他算法。這是因?yàn)镾toGOMP 算法在迭代過(guò)程中不僅將殘差與測(cè)量矩陣內(nèi)積的前K 個(gè)最大值作為候選支撐，而且還通過(guò)隨機(jī)方式從所有位置挑選候選支撐，這在一定程度上增加了正確支撐集挑選的概率。

圖4 不同算法重構(gòu)成功率與稀疏度關(guān)系Fig. 4 Relationship between reconstruction success rate and sparsity of different algorithms

3.2 二維圖像重構(gòu)實(shí)驗(yàn)

實(shí)驗(yàn)采用大小為512 × 512 像素的某型號(hào)汽車(chē)法蘭盤(pán)圖像作為測(cè)試圖像來(lái)驗(yàn)證本文算法的重構(gòu)性能。實(shí)驗(yàn)中采用小波基作為稀疏基，稀疏度設(shè)置為K = M 4，定義采樣率r =M/N。所有的重構(gòu)算法均獨(dú)立重復(fù)200 次取均值作為實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)采用峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）作為圖像重構(gòu)質(zhì)量的評(píng)判標(biāo)準(zhǔn)，PSNR的計(jì)算公式為:

采樣率為r = 0.3 時(shí)不同算法重構(gòu)得到的直觀效果如圖5所示。從圖5 可知，BGOMP 算法重構(gòu)效果與GOMP 算法相差不大，在Pr取0.2 時(shí)StoGOMP 算法的重構(gòu)效果與GOMP 算法相當(dāng)，當(dāng)Pr取0.4時(shí)重構(gòu)效果稍差。

圖5 不同算法重構(gòu)結(jié)果對(duì)比Fig.5 Comparison of reconstruction results of diffident algorithms

表1 為在不同采樣率下不同算法重構(gòu)汽車(chē)法蘭盤(pán)圖像的PSNR 值和耗時(shí)統(tǒng)計(jì)。表1 中:GOMP 算法參數(shù)為S = K 2，StoGOMP算法的概率值設(shè)為Pr= 0.2和Pr= 0.4。

從表1可知，當(dāng)Pr= 0.2時(shí)，StoGOMP算法的重構(gòu)PSNR值均高于同采樣率下其他算法的PSNR 值，隨著Pr的增大，StoGOMP 算法的重構(gòu)PSNR 值呈現(xiàn)下降趨勢(shì)。在不同采樣率情況下，StoGOMP 算法重構(gòu)時(shí)間均小于GOMP 算法和BGOMP算法，在采樣率為r = 0.5 時(shí)，StoGOMP 算法的重構(gòu)時(shí)間相比GOMP 算法減少了27%以上。在采樣率較低時(shí)，GOMP 算法和StoGOMP 算法所需的重構(gòu)時(shí)間高于OMP 算法和SP 算法，在采樣率r = 0.3 和r = 0.5 時(shí)，前者所需重構(gòu)時(shí)間明顯低于后者。

為了驗(yàn)證StoGOMP 算法的抗噪性，對(duì)原始的汽車(chē)法蘭盤(pán)圖像加上不同程度的高斯白噪聲，在采樣率為0.3 時(shí)用各算法對(duì)加噪后的圖像進(jìn)行重構(gòu)，重構(gòu)結(jié)果記錄在表2中。從表2可知隨著噪聲強(qiáng)度增加，各算法的PSNR值也逐漸降低。

表1 某型號(hào)汽車(chē)法蘭盤(pán)圖像用不同算法重構(gòu)得到的PSNR和重構(gòu)時(shí)間Tab. 1 PSNR and reconstruction time of flange image of a type of vehicle reconstructed by different algorithms

表2 高斯噪聲環(huán)境下不同算法重建PSNR（r = 0.3）單位：dBTab. 2 Reconstruction PSNR of different algorithms in Gaussian noise environment（r = 0.3） unit:dB

對(duì)比表1 和表2 可以看出，StoGOMP 算法的重構(gòu)PSNR 值變化幅度相對(duì)GOMP 算法較小，這說(shuō)明其抗噪性能較好。這是因?yàn)镾toGOMP 算法在迭代過(guò)程中某些支撐集是通過(guò)隨機(jī)方式挑選，使其具有良好的抗干擾性能。

4 結(jié)語(yǔ)

為了減少GOMP 算法的計(jì)算量和重構(gòu)時(shí)間，在GOMP 算法的基礎(chǔ)上，引入隨機(jī)支撐集挑選的策略，提出了StoGOMP算法，并對(duì)算法性能作了分析。StoGOMP 算法在某些步驟只需從測(cè)量矩陣中隨機(jī)挑選支撐，無(wú)需計(jì)算測(cè)量矩陣和殘差的內(nèi)積，在一定程度上降低了算法的復(fù)雜度。一維隨機(jī)高斯信號(hào)和現(xiàn)實(shí)圖像重構(gòu)實(shí)驗(yàn)結(jié)果表明，StoGOMP 算法相比GOMP算法在保證重構(gòu)成功率的情況下，所需的采樣數(shù)有大幅減少；相對(duì)于同類(lèi)貪婪追蹤類(lèi)算法，StoGOMP 算法具有更高的重構(gòu)成功率和良好的抗噪性能。