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

徐志強，蔣鐵鋼，楊立波

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

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

0 引言

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

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

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

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

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

1 壓縮感知理論

對于長度為N × 1 的信號h ∈RN×1，它可以表示成一組正交基的線性組合，即:

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

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

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

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

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

2 基于隨機支撐挑選的GOMP算法

2.1 算法描述

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

2.2 StoGOMP算法性能分析

以下分三種情況對StoGOMP算法進行分析:

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

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

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

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

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

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

3.1 隨機高斯信號重構(gòu)實驗

圖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)

為了驗證StoGOMP算法的重構(gòu)精度，以長度為400 × 1的高斯信號為測試信號，大小為100 × 400的隨機高斯矩陣作為采樣矩陣，稀疏度設(shè)置為K = 24，每次迭代挑選的索引數(shù)設(shè)置為［5，10，15］，Pr= 0.3。圖2 記錄了平均重構(gòu)誤差與迭代次數(shù)的關(guān)系。由圖2可知:在迭代次數(shù)小于20次時，GOMP 算法與BGOMP 算法收斂速度相當(dāng)，且都比StoGOMP 算法快；當(dāng)?shù)螖?shù)大于20時，GOMP算法的重構(gòu)誤差下降緩慢，誤差曲線基本保持水平，而StoGOMP 算法的誤差曲線還有明顯下降。這說明在迭代后期，StoGOMP 算法在重構(gòu)精度上具有優(yōu)勢。這是因為在迭代后期GOMP 算法挑選的原子基本不再變化，因此其重構(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

為了驗證給定概率Pr對StoGOMP 算法重構(gòu)性能的影響，采用長度為N = 200，500，1 000，2 000 的高斯信號作為測試信號，稀疏度設(shè)置為K = 40，100，200，400，采樣數(shù)設(shè)置為M =N 2。從圖3 所示的實驗結(jié)果可看出，當(dāng)Pr接近0 或1 時，StoGOMP算法的重構(gòu)成功率最低，當(dāng)0.2 ＜Pr＜0.8時，重構(gòu)成功率保持在較高的水平，這說明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

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

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

3.2 二維圖像重構(gòu)實驗

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

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

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

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

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

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

表1 某型號汽車法蘭盤圖像用不同算法重構(gòu)得到的PSNR和重構(gòu)時間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

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

4 結(jié)語

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