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

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

0 引 言

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

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

不難發(fā)現(xiàn)，在m<

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

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

1 塊稀疏信號模型

設(shè)信號總長為n，信號中非零元素的個數(shù)為K，若K<

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

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

圖1 塊稀疏信號示意

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

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

表1 BgOMP 偽代碼

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

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

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

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

3 算法無失真重構(gòu)條件

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

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

那么稱Φ 滿足K 階RIP。

下面，利用gOMP 的相關(guān)結(jié)論證明BgOMP 的有效性。

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

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

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

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

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

證明：由引理1 可知，當(dāng)成立時(shí)，有：

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

可得：

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

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

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

定理2：設(shè)s ≤min{K,m/K}，那么當(dāng)滿足以下條件時(shí)，BgOMP 必然能夠重構(gòu)原始信號：

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

因此，BgOMP 滿足即可保證信號重構(gòu)。

此外，從可以看出，當(dāng)s=N 且K ≥2 時(shí)，強(qiáng)于，因此，在處理塊稀疏信號時(shí)，BgOMP 的約束條件較原始gOMP 的約束條件更加嚴(yán)格。

4 仿真驗(yàn)證

4.1 仿真條件設(shè)置

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

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

仿真中包含的參數(shù)有：

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

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

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

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

（5）仿真圖片中，每一個概率數(shù)值均由1000次仿真實(shí)驗(yàn)得出。

4.2 重構(gòu)性能對比

仿真實(shí)驗(yàn)一對比各種算法在不同稀疏度場景下的經(jīng)驗(yàn)重構(gòu)概率，參數(shù)設(shè)置如下：

（1）m=128；

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

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

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

圖2 不同稀疏度下的重構(gòu)概率對比

仿真實(shí)驗(yàn)二對比BgOMP 和gOMP 的不同估計(jì)步長對經(jīng)驗(yàn)重構(gòu)概率的影響，與仿真實(shí)驗(yàn)一存在區(qū)別的參數(shù)如下：

（1）僅對BgOMP 和gOMP 進(jìn)行仿真；

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

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

仿真實(shí)驗(yàn)三對比各種算法在不同測量值（測量值的數(shù)值等于y 的維度）下的經(jīng)驗(yàn)重構(gòu)概率，與仿真實(shí)驗(yàn)一存在區(qū)別的參數(shù)如下：

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

（2）K=20。

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

圖3 BgOMP 和gOMP 對比

圖4 不同測量值下的重構(gòu)概率對比

仿真實(shí)驗(yàn)四對比各種算法在不同稀疏度場景下的迭代次數(shù)，參數(shù)設(shè)置與仿真實(shí)驗(yàn)一完全相同。需要說明的是本次實(shí)驗(yàn)中，圖中的每個數(shù)據(jù)通過1000次仿真實(shí)驗(yàn)中正確重構(gòu)的實(shí)驗(yàn)次數(shù)統(tǒng)計(jì)而出。

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

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

圖5 不同稀疏度下的迭代次數(shù)對比

5 結(jié) 語

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