塊稀疏廣義正交匹配追蹤算法*

楊恩蘋，周 三，王彥帥，隋天宇

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

壓縮感知作為一種可以突破Shannon-Nyquist定理局限的采樣理論，近十年來受到了廣泛的關注，在通信、遙感、遙測、醫療圖像等領域得到了廣泛的應用。對于稀疏信號或可被稀疏分解的信號，壓縮感知能夠以遠低于信號Nyquist 速率的采樣率完成采樣，其理論基礎如下，

其中，x 是長度為n 的稀疏（或可稀疏分解）信號，Φ 是維度為m×n（m<

不難發現，在m<

一般說來，上述算法適用于重構非零元完全隨機分布的稀疏信號。然而，一些研究發現在某些稀疏基的約束下，例如傅里葉基和小波基等，塊稀疏信號更加符合人造信號的特點[6-9]。此類信號的非零元呈“塊狀”隨機分布，而非單個非零元隨機分布。文獻[10]提出了針對一種特殊塊稀疏信號的重構方法，但要求所有非零塊的長度相等，零塊的長度為非零塊的整數倍。文獻[11]提出的算法，不要求非零塊長度相等，但是需要利用信號中關于塊結構的先驗知識，即知道信號中每個塊的長度，只是不知道某個具體的塊是全零塊還是非零塊。

綜上，現有塊稀疏信號重構算法仍存在局限，有進一步提升的空間。因此，本文針對塊稀疏信號重構問題，基于計算量較小的且性能優異的gOMP，提出了適用于塊稀疏信號的BgOMP 算法，給出了算法的詳細介紹，證明了算法的無失真重構的充分條件，并通過仿真證實了算法的有效性與優越性。

1 塊稀疏信號模型

設信號總長為n，信號中非零元素的個數為K，若K<

其中，ψ 是維度為n 的稀疏分解基（若信號無需稀疏分解，則表示單位矩陣），θ 為非零塊的系數，I 是包含所有非零塊的索引值的集合，集合I 的勢為|I|=||I||0=K。

為方便理解，這里通過圖示的方式說明塊稀疏信號特點。圖1 表示一個信號向量，每個方塊表示一個元素，白色方塊表示0 元素，著色方塊表示非零元素。可以看出，該信號包含3 個非零塊，稀疏度K 等于9，集合I={3,4,5,7,8,10,11,12,13}。

圖1 塊稀疏信號示意

2 塊稀疏廣義正交匹配追蹤算法

所有的匹配追蹤算法都具有相通的基礎原理：計算y 與Φ 的相關值，通過相關值的大小估計出x的非零元。不同的匹配追蹤算法的區別主要體現在潛在非零元的選取方法，以及最終確定潛在非零元的方法上。本文提出的BgOMP 與gOMP 的主要區別在于，利用了塊稀疏信號的稀疏特性——非零元在信號向量中分段連續[9]。換句話說，如果通過相關計算找到了一個正確的潛在非零元，那么索引值與該非零元相鄰的元素（如果存在的話），必然也為非零。例如，若通過相關運算，估計出圖1 中索引值為10 的元素非零，那么索引值與10 相鄰的9和11 中，至少有一個為非零元素。算法偽代碼如下：

表1 BgOMP 偽代碼

算法所需的輸入值有傳感矩陣、采樣值、稀疏度與算法的估計步長。前三項輸入是大多數匹配追蹤算法的必備輸入，當然目前也存在一些能夠估計信號稀疏度的算法，但通常計算復雜度較高。算法的估計步長是指每次迭代時，通過相關運算選取的非零元個數。

算法需對迭代次數、集合I、殘差r、塊的選取范圍進行初始化。在初始狀態下，顯然有，迭代次數為0，集合I 為空集，殘差r 等于采樣值。需要說明的是塊的選取范圍，通常壓縮感知要求信號的稀疏度不超過m/2，否則任何重構算法都無法重構信號，因此，在這個極限范圍內，利用塊稀疏信號特性選取潛在的非零元素。

算法更新迭代次數后，首先計算矩陣Φ 與殘差r 的相關值，并構建兩個集合，第一個集合Λ 包含最大s 個相關值對應的索引值，第二個集合包含最大m/2 個相關值對應的索引值（僅需一次相關計算，偽代碼中兩項相關計算是為了區分兩個集合）。然后，尋找Λ 中所有元素的相鄰元素，若這些相鄰元素同時也屬于第二個集合，那么判定為有效。最后，將上次迭代產生的估計集合與本次迭代找到的最大值集合，以及這些最大值的有效相鄰元素集合這三個集合合并，進而計算殘差，更新殘差并進入下一次迭代。

眾所周知，迭代算法必須設置停止條件，在本算法中停止條件與gOMP 完全相同，停止條件1 可以設置為一個極小的固定常數，當殘差大于該常數時，將進行下一次迭代；停止條件2 為迭代次數，因知曉信號稀疏度，且估計的信號支撐集不應超過m，所以，若迭代次數大于稀疏度或m/s，需要停止迭代。

3 算法無失真重構條件

與眾多壓縮感知重構算法類似，本文仍然使用受限等距特性（RIP）對算法進行約束。首先說明RIP 的定義，

定義1[12]：若對于任意的K 稀疏向量x，矩陣Φ 以常數δ（0<δ<1）滿足

那么稱Φ 滿足K 階RIP。

下面，利用gOMP 的相關結論證明BgOMP 的有效性。

引理1[4]：假設nx∈R 是一個K 稀疏的信號，N為gOMP 的估計步長，只要其RIP 常數滿足

那么gOMP 在第一次迭代時，必然能夠找到至少一個非零元的正確位置。

定理1：假設nx∈R 是一個總稀疏度為K 的塊稀疏信號（K ≥2），s 為BgOMP 的估計步長，只要其RIP 常數滿足

那么BgOMP 在第一次迭代時，必然能夠找到一個非零塊的正確位置。

實際上，在定理1 中，步長s 等效于gOMP 的步長N，區別在于第一次迭代，完成相關計算后，BgOMP 將選擇相鄰元素，加入估計的支持集。下面證明選擇相鄰元素，不會消除已有的正確元素。

證明：由引理1 可知，當成立時，有：

Λ1中的所有s 個元素，從數值上來看，可能完全不相鄰，也可能是連續的s 個數字，因此，

可得：

可知只要在第一次相關計算時，能夠找到至少一個正確的非零元，這些正確的原始必然被保留在估計支撐集中。

類似地，可以利用gOMP 后續迭代的約束條件給出BgOMP 的約束條件。

引理2[4]：設N ≤min{K,m/K}且gOMP 進行了l次有效的迭代，那么當滿足以下條件時，第l+1 次迭代必然成功，

定理2：設s ≤min{K,m/K}，那么當滿足以下條件時，BgOMP 必然能夠重構原始信號：

證明：由引理2，并結合增加向量元素后集合勢的大小，可知，當BgOMP 進行了l 次有效的迭代，那么當滿足時，第l+1 次迭代必然成功。同時，考慮到：

因此，BgOMP 滿足即可保證信號重構。

此外，從可以看出，當s=N 且K ≥2 時，強于，因此，在處理塊稀疏信號時，BgOMP 的約束條件較原始gOMP 的約束條件更加嚴格。

4 仿真驗證

4.1 仿真條件設置

在本文的仿真實驗中，塊稀疏信號產生方法為：首先根據算法稀疏度，生成一個長度為K 的向量，其元素的數值符合高斯分布，然后計算K 個非零元可構成的塊的個數k，從滿足k 取值范圍的整數中，隨機選取一個值k′，將長度為K 的向量劃分成為k′個塊，最后將這些塊隨機插入長度為n-K 的零向量當中。

本文算法是經改進gOMP 而來，所以核心的仿真對比算法為gOMP。考慮到，gOMP 和BgOMP 均為需要已知稀疏度K 的匹配追蹤算法，所以將業界較為著名的，同樣也需利用該先驗信息的幾種匹配追蹤算法也作為對比對象，包括OMP，ROMP，StOMP，SP，CoSaMP。

仿真中包含的參數有：

（1）傳感矩陣的維度，m、n，在后續所有仿真中，n=256；

（2）信號的總稀疏度K 和塊稀疏度k′；

（3）特別地，對于gOMP 和BgOMP 還包括估計步長，N 和s；

（4）對于擁有常數迭代停止條件的算法，設置為ε=10e-6；

（5）仿真圖片中，每一個概率數值均由1000次仿真實驗得出。

4.2 重構性能對比

仿真實驗一對比各種算法在不同稀疏度場景下的經驗重構概率，參數設置如下：

（1）m=128；

（2）5 ≤K ≤70，且取值間隔為5；

（4）N 和s 均選 取2 和4 兩 個 值。

從圖2 中可以看出，僅對OMP 進行了簡單修改的gOMP 算法性能明顯優于SP 和CoSaMP 等復雜且具備精煉能力的算法，同時，能夠看到在塊稀疏場景下BgOMP 具有最優的重構概率，且在對應的步長選擇情況下，較gOMP 具有明顯的重構概率提升。當K=45 時，gOMP 的重構概率開始下降，而BgOMP 在K=50 時才下降。此外，在K=50 時，BgOMP仍然能以97%的重構概率恢復出原始信號，而gOMP 的重構概率以低于90%。

圖2 不同稀疏度下的重構概率對比

仿真實驗二對比BgOMP 和gOMP 的不同估計步長對經驗重構概率的影響，與仿真實驗一存在區別的參數如下：

（1）僅對BgOMP 和gOMP 進行仿真；

（2）s 和N 的取值包括，2、4、8、16。

從圖3 中可以看出對應的步長情況下BgOMP重構性能均優于gOMP，且步長越小，重構性能越好。但是，小的步長必然導致更多的迭代次數，增加運算量，因此，步長需折中選擇。不過，受篇幅限制，步長選擇問題，此處不作過多討論。

仿真實驗三對比各種算法在不同測量值（測量值的數值等于y 的維度）下的經驗重構概率，與仿真實驗一存在區別的參數如下：

（1）50 ≤m ≤100，且取值間隔為5；

（2）K=20。

從圖4 中可以看出在固定信號稀疏度的情況下，測量值數目相同時，BgOMP 的重構概率最高；在重構概率相同時，不論步長為何值，BgOMP 所需的測量值最少。在壓縮感知框架中，通常認為測量值數目越少，算法能夠適應的壓縮比就越高，重構性能越好。此外，圖4 中也能明顯看出BgOMP 的性能優于gOMP。

圖3 BgOMP 和gOMP 對比

圖4 不同測量值下的重構概率對比

仿真實驗四對比各種算法在不同稀疏度場景下的迭代次數，參數設置與仿真實驗一完全相同。需要說明的是本次實驗中，圖中的每個數據通過1000次仿真實驗中正確重構的實驗次數統計而出。

從圖5 中可以看出，OMP 需求的迭代次數均最多，等于稀疏度，符合該算法原理。StOMP 需求的迭代次數相對較少，但重構性能一般，K=35 時，重構概率極具下降，K=55 時，已無法重構信號。SP 和CoSaMP 這兩種復雜的算法在稀疏度低時，重構概率高，需求的迭代次數少，但一旦稀疏度超過一個臨界值，迭代次數將極具上升。

特別地，從圖5 中可以看出，gOMP 和BgOMP是僅有的兩種算法在稀疏度為70 的時候，還有部分仿真實驗成功，迭代次數增長也較為平穩。同時，不難看出，相同情況下BgOMP 需求的迭代次數少于gOMP，且總的看來稀疏度越高越明顯，這充分說明非零塊的尋找是成功的，BgOMP 較gOMP 的改進優化是成功的。

圖5 不同稀疏度下的迭代次數對比

5 結 語

本文針對壓縮感知中的塊稀疏信號重構問題，提出了塊稀疏廣義正交匹配追蹤算法。該算法以原理簡單，計算量小且重構性能優異的廣義正交匹配追蹤算法（gOMP）為基礎，通過在gOMP 的迭代環節增加最大相關值相鄰元素搜索步驟，實現了尋找信號非零塊的功能，以簡單的集合運算為代價，大幅提升了塊稀疏場景下的重構概率。基于gOMP的理論分析表明若傳感矩陣以一定條件滿足RIP，那么BgOMP 必然能夠重構信號，同時，數值仿真證明了BgOMP 是有效的，且較其他匹配追蹤算法更適用于塊稀疏重構場景。