劉素娟 崔程凱 鄭麗麗 江書陽

(北京工業(yè)大學微電子學院 北京 100124)

1 引言

壓縮感知(Compressed Sensing, CS)理論的提出避免了奈奎斯特采樣定理在信號處理領域的局限性，實現(xiàn)了稀疏信號的亞奈奎斯特頻率采樣[1-3]。根據(jù)稀疏信號的稀疏特性，利用不相干的測量矩陣將高維稀疏信號投影到低維后進行處理，在濾波之后使用遠低于奈奎斯特頻率的模數(shù)轉換器(Analog to Digital Converter, ADC)進行采樣，采樣后的數(shù)字信號包含了原始信號的全部信息。最后，通過利用重構算法求解線性優(yōu)化問題重構原始信號。

壓縮感知重構算法主要包括貪婪算法、凸優(yōu)化算法和其他算法。貪婪類算法由于其硬件實現(xiàn)的簡便易行得到了廣泛學者的青睞。匹配追蹤算法(Matching Pursuits, MP)[4]奠定了貪婪算法的基礎，其核心思想是利用原子向量的線性運算去逐漸逼近信號向量，經過不斷迭代，最后選擇出以稀疏度為參考個數(shù)的原子。但是在迭代過程中，如果殘差在已選擇原子上的垂直投影是非正交的，則迭代后得到的結果將不是最優(yōu)的而是次優(yōu)的。這會導致在后續(xù)迭代過程中可能會重復選擇到相同的索引，算法收斂需要更多的迭代次數(shù)。正交匹配追蹤算法(Orthogonal Matching Pursuit, OMP)[5]作為貪婪類算法繼續(xù)發(fā)展的重要基礎，克服了MP算法的缺陷。 在OMP算法的迭代過程中，殘差總是能夠與已經選擇過的原子正交，這保證了相同的索引不會被重復選擇，迭代過程將會在有限的幾步內收斂。在OMP算法基礎之上，正則化正交匹配追蹤算法(Regularized Orthogonal Matching Pursuit,ROMP)[6]及其變體[7]，廣義正交匹配追蹤算法(generalized Orthogonal Matching Pursuit,gOMP)[8]及其變體[9]，分段正交匹配追蹤算法(Stagewise Orthogonal Matching Pursuit,StOMP)[10]及其變體[11]，稀疏度自適應匹配追蹤算法(Sparsity Adaptive Matching Pursuit,SAMP)[12]及其變體[13-15]，基于投影的原子選擇正交匹配追蹤算法(Projection-based atom selection in Orthogonal Matching Pursuit, POMP)[16-18]，壓縮采樣匹配追蹤算法(Compressive Sampling Matching Pursuit, CoSaMP)[19,20]及其變體[21,22]，子空間追蹤算法(Subspace Pursuit, SP)[23,24]及其變體[25-28]，向前展望正交匹配追蹤算法(Look Ahead Orthogonal Matching Pursuit, LAOMP)[29]及其變體[17,30-32]等算法陸續(xù)被提出。算法的更新趨勢是在已存在的算法原型上進行改進，使新算法在提高恢復性能、降低計算復雜度以及減少計算時間成本等方面更加具有優(yōu)勢。

作為貪婪類算法的核心，原子識別策略的差異往往決定了算法重構性能的優(yōu)劣。雖然重構算法種類繁多，但嵌入到各類算法中的原子識別策略種類是有限的。據(jù)此，本文在稀疏信號壓縮感知模型的基礎上對貪婪類重構算法的原子識別策略進行了歸納與總結，著重綜述了算法在不同處理階段可以運用的原子選擇策略。目的是通過歸納綜述這些原子識別策略增進對貪婪類算法的理解，通過對原子識別策略的組合優(yōu)化及運用，提出性能更加優(yōu)越的新算法。

2 壓縮感知模型

壓縮感知理論摒棄先采樣后壓縮的傳統(tǒng)做法，實現(xiàn)了采樣和壓縮的同步進行，降低了采樣速率，減少了處理成本和存儲成本[1]。如式(1)所示，原始信號x在正交基矩陣θ上被稀疏表示為θα，其中α為僅包含有限非0元素的投影系數(shù)向量。使用與正交基矩陣θ滿足約束等距條件(Restricted Isometry Propetry, RIP)的觀測矩陣Ψ∈RM×N對稀疏信號x進行線性測量，并將觀測矩陣與正交基矩陣的乘積稱為感知矩陣A∈RM×N。濾波采樣后得到從維度為N的高維向量x壓縮到維度為M的低維觀測向量y ∈RM×1,y包含了原始信號的全部信息。其中，

3 貪婪類重構算法原子識別策略

作為貪婪類算法最重要的一環(huán)，原子識別過程指的是通過以內積、投影或殘差等變量作為判斷依據(jù)，在感知矩陣A中選擇出以稀疏度作為參考個數(shù)的列向量構成索引集。將索引集中的列向量稱為原子，則可以通過求解最小二乘問題得到原始觀測向量y在由這些原子所構成的矩陣上的投影系數(shù)向量α，繼而通過等式x=θα恢復出原始信號。

為了便于描述，每次迭代過程中所選擇出的列向量集合稱為最終支撐集，最終支撐集以外的其他列向量所構成的集合稱為潛在支撐集，最終支撐集與潛在支撐集的并集中需要進一步識別處理的原子集合稱為候選支撐集。A代表感知矩陣，y表示觀測向量，K表示信號稀疏度，M表示感知矩陣的行數(shù)，N表示感知矩陣的列數(shù)，r表示殘差，t表示迭代次數(shù)。t作為下標時表示變量處于第t次迭代狀態(tài)。集合符號作為矩陣下標時表示取矩陣中集合所指定位置的列向量。AT表示A矩陣的轉置，A?表示A矩陣的偽逆矩陣。l ength()表示取向量的長度。下文中信號估計值的計算過程是對最小二乘問題的求解，如式(4)所示

圖1 壓縮感知模型

本文根據(jù)原子識別策略的不同應用場景將其分為兩類。其中，3.1節(jié)與3.2節(jié)所涉及策略對應稀疏度已知的應用場景，本文稱其為直接原子識別策略；3.3節(jié)所介紹的策略對應稀疏度未知的應用場景，本文稱其為原子個數(shù)識別策略。

3.1 一步式原子識別策略

此類策略可以將選中的索引直接并入最終索引集，也可以作為后續(xù)原子識別的中間媒介。

3.1.1 內積原則選取策略

內積原則選取策略依據(jù)感知矩陣A的列向量與殘差r的內積絕對值大小選擇原子，根據(jù)St=arg max(|〈A,rt-1〉|)從內積絕對值中選擇最大元素對應的一個索引并入最終支撐集，這里稱為內積原則，它是所有貪婪算法的起點。此外，為了進一步加快算法收斂速度，可以通過內積原則并行選擇出前L個內積絕對值較大元素對應的原子并入最終支撐集以減少迭代次數(shù)。用到該策略的貪婪類算法有很多，區(qū)別在于不同算法對于L值大小的要求是不同的，例如：OMP[5,33-35]要求L=1，gOMP[8]要求1≤L ＜min{K,M/K}，POMP[21-23]要求其滿足1≤L ≤K，CoSaMP[20,36]要求L=2K，而SP[23,24]要求L=K。為方便在本文后續(xù)的其他策略中調用此原則，將其記為式(5)中的函數(shù)supp_max_L

3.1.2 弱選擇策略

原子的弱選擇策略以當前迭代過程中最大內積絕對值的ρ倍為判斷標準，將內積絕對值中大于該標準的原子選擇出來，其中，0＜ρ ＜1[11]，其形式如式(6)所示

該操作將其他原子對應的內積絕對值與最大的內積絕對值在大小關系上聯(lián)系起來。由于最大內積絕對值在每次的迭代過程中是動態(tài)變化的，使得算法每次選取索引的個數(shù)也保持動態(tài)變化。

3.1.3 閾值分段選擇策略

閾值分段選擇策略的核心思想是通過設定一個動態(tài)更新的閾值作為原子的選擇標準來并行地更新最終索引集，可用式(7)表示

其中，Pt=〈A,rt-1〉表示感知矩陣和殘差的內積，tht為預先設定的閾值參數(shù)。σt表示形式噪聲水平。由于殘差在每一次的迭代過程中是動態(tài)變化的，所以即便閾值參數(shù) tht是一個固定值，閾值t htσt仍然可以保持動態(tài)變化。閾值分段選擇策略在每次迭代過程中可以實現(xiàn)多個原子的并行選擇，但閾值參數(shù)針對高斯矩陣只有經驗值，一般為 tht ∈[2,3]，且還沒有充分的理論推導確保該范圍的精準性。實際應用中需要根據(jù)實際情況進行選取。

3.2 進階式原子識別

進階式原子識別策略是在選擇出潛在支撐集或候選支撐集的基礎上進一步精確挑選原子，以此提高算法的重構準確度。

3.2.1 模糊閾值策略

模糊閾值策略的核心思想是通過設定一個動態(tài)變化的閾值，將標準之外的原子剔除掉，以此減少在后續(xù)求解最小二乘問題中的計算負擔。閾值的大小在每次迭代過程中與內積相關，其浮動設定保證了原子選擇的準確性。其偽代碼如算法1所示。

算法1 模糊閾值策略[37]

在閾值的設定標準中，α=P2/P1， 其中P1,P2代表每次迭代過程中內積向量P降序排列后前2個元素值。τ表示閾值，其理想范圍為τ∈[0.3,0.5]?？s減過程中，該策略只保留潛在支撐集中內積值大于閾值標準的原子。模糊閾值策略可以被應用于潛在支撐集原子數(shù)目過多的情況，Λt作為輸出表示潛在支撐集中滿足閾值標準的原子集合。

3.2.2 部分最小二乘投影策略[38]

部分最小二乘投影策略的核心思想是將投影值作為原子選擇的判斷標準。通過比較投影值的大小，將最大的投影值所對應的原子作為當前迭代過程選中的結果，其過程如式(8)所示

3.2.3 增量最小二乘投影回溯策略

索引集原子逐漸增加的算法在執(zhí)行前期找到的索引大概率是正確的，但隨著迭代次數(shù)增加，執(zhí)行后期找到正確索引的概率越來越小。增量最小二乘投影回溯策略的核心思想是通過回溯的手段，在算法的執(zhí)行后期將原子增補方式改為每2次迭代新增1個原子，以提高原子選擇的準確度。其偽代碼如算法2所示。

算法2 增量最小二乘投影回溯策略[41]

增量最小二乘投影回溯策略中， T R表示開始標志，即為算法執(zhí)行前期與執(zhí)行后期的分界線，且TR＜K。在迭代次數(shù)大于開始標志后，該策略每兩次迭代回溯1次，即增加2個索引后再通過回溯剔除掉1個，剔除的標準以投影值的大小為依據(jù)。

此外，與此類似的原子識別方法還有最小二乘投影閾值回溯策略[39,40]，該策略將模糊閾值策略與投影回溯策略有機融合，其核心思想是在得到投影向量以后，通過設定一個動態(tài)變化的投影值標準作為原子的選擇依據(jù)，將不滿足此標準的原子全部剔除掉，以此提高算法的重構精度，且該策略適用于稀疏度不先驗的情況。

3.2.4 基于投影的原子選擇策略

基于投影的原子選擇策略的核心思想是以投影值作為原子選擇標準，將投影值較大的原子所對應的索引并入最終支撐集。其偽代碼如算法3所示。

算法3 基于投影的原子選擇策略[17]

基于投影的原子選擇策略將潛在支撐集Ct并入上一次迭代后得到的最終索引集It-1，組成候選支撐集St，并求出其投影值向量。其次，將潛在支撐集Ct之外的索引所對應的投影值置0，則本次迭代過程中選中的結果為處理后的投影值中較大的L個值所對應的索引。文獻[17]中L的取值大于1，表示每次迭代并行選擇出多個原子，但是選擇出來的原子會被后續(xù)操作處理，最后從L個原子中選擇出1個最相關的原子。

3.2.5 壓縮采樣原子選擇策略

壓縮采樣原子選擇策略在每次迭代過程中通過內積原則選擇 2K個原子并入最終索引集，而后通過比較投影系數(shù)的大小，回溯掉K個投影系數(shù)較小值對應的原子。壓縮采樣原子選擇策略的核心思想是采用并行原子選擇的方式使算法運行得更快，而其回溯手段使算法在重構精度方面也得到了保證。壓縮采樣原子選擇策略的偽代碼如算法4所示。

算法4 壓縮采樣原子選擇策略

此外，子空間追蹤算法[23,24]采取的原子選擇策略與壓縮采樣原子選擇策略類似，核心本質均是采用并行原子選擇以減少迭代次數(shù)，再通過回溯手段提高重構成功率。二者的區(qū)別在于，子空間追蹤原子選擇策略每次迭代過程中通過內積原則選擇K個原子，而不再是 2K個。其次，子空間追蹤原子選擇策略在更新殘差時需要重新計算投影系數(shù)，即每次迭代過程中需要求解兩次最小二乘問題。

3.2.6 展望策略

展望策略的核心思想在于它的原子選擇標準不僅取決于內積絕對值的大小，還取決這些原子將來對最小化最終殘差的影響能力。通過選擇能夠最小化最終殘差的一組索引作為最終支撐集，展望策略在同類算法中的重構準確度首屈一指。其偽代碼如算法5所示。

算法5 展望策略[17,29]

展望策略相當于已知部分支撐集的OMP算法，對于潛在索引i，在其并入最終支撐集后，該策略每次迭代從內積中選擇一個相關性最大的原子索引，直到滿足迭代停止的判斷條件，并評估該原子在迭代過程中對最小化最終殘差影響能力的大小。因此，在給定稀疏度K、最終支撐集It-1和潛在索引i的情況下，算法可以在最后找到包含K個元素的最終支撐集，并返回最終殘差。該策略可被記為式(9)

3.2.7 并行展望策略

并行展望策略以展望策略為基礎，其核心思想在于每次迭代過程中并行選取原子以減少迭代次數(shù)。并行展望策略的偽代碼如算法6所示。

算法6 并行展望策略[30]

并行展望策略在迭代過程中需要輸出相應的索引集Λj，當確定支撐集選取對象后，將該索引集Λt與 潛在支撐集Ct的 交集中所包含的索引集Γt并入最終支撐集中完成并行選取。

3.2.8 正交最小二乘一步展望策略

正交最小二乘一步展望策略與展望策略的核心思想類似，不同之處在于前者以待選原子在當前迭代過程中最小化殘差的能力大小為標準來選擇原子，即正交最小二乘一步展望策略側重于當前迭代過程對下一個原子選擇的影響，而展望策略側重于當前迭代過程對最終結果的影響。其偽代碼如算法7所示。

算法7 正交最小二乘一步展望策略[17]

在文獻[17]中，OLS算法調用該策略的形式可稱為剩余支撐集遍歷策略，如式(10)所示

剩余支撐集遍歷策略調用正交最小二乘一步展望策略，遍歷了所有未被選入最終支撐集的索引，即將每個索引放入最終索引集后，計算其殘差l2范數(shù)，最后將殘差l2范數(shù)最小值所對應的索引選擇出來。剩余支撐集遍歷策略的計算量非常大，適合對長度較短的稀疏信號進行恢復。

3.3 稀疏度自適應策略

本節(jié)所介紹的內容與直接原子識別策略不同。當稀疏度未知時，需要通過自適應策略得出信號稀疏度的估計數(shù)值。稀疏度的估計值決定了原子識別過程所選取的原子個數(shù)。將稀疏度自適應的過程稱為原子個數(shù)識別。在稀疏度未知的情況下，對稀疏度的準確估計能夠保證重構信號的精度。

3.3.1 固定步長稀疏度自適應策略

固定步長稀疏度自適應策略的核心思想是設定一個固定步長s作為步進標準，并以殘差為判斷依據(jù)匹配稀疏度的具體數(shù)值。其偽代碼如算法8所示。

算法8 固定步長稀疏度自適應策略[12,26]

固定步長稀疏度自適應策略中的步長s(1≤s≤K)是一個在迭代過程中不會發(fā)生改變的固定值。該策略以當前迭代過程中得到的殘差與上一次迭代后得到的殘差的能量大小作為支撐集長度是否更新的依據(jù)。策略執(zhí)行過程中若不滿足停止條件，則說明支撐集里的索引還沒有找全面，需要繼續(xù)計算。若當前殘差的能量比上一次迭代后得到的殘差能量大，說明當前支撐集長度較短，則保持步長不變，增加狀態(tài)數(shù)使支撐集的長度增加。若殘差的能量減小，說明當前支撐集長度合適，但是需要繼續(xù)迭代淘汰錯誤的原子。固定步長稀疏度自適應策略的估計精度往往和步長s的設置有關。s越小，估計的準確度越高，但需要迭代的次數(shù)就會越多。

3.3.2 變步長稀疏度自適應策略

變步長稀疏度自適應策略的核心思想是在迭代初期選擇大步長快速逼近真實稀疏度，后續(xù)迭代過程中步長逐漸縮小，慢速逼近真實稀疏度，以此避免算法對稀疏度產生過估計或欠估計的問題。變步長稀疏度自適應策略主要有3種估計稀疏度的方法：運用相鄰階段估計信號的能量差，運用測量值向量與估計信號能量的比值自適應調節(jié)步長，根據(jù)殘差能量的階段大小自適應調節(jié)步長。其偽代碼如算法9所示。

算法9 兩閾值變步長稀疏度自適應策略[16]

兩閾值變步長稀疏度自適應策略引進了兩個閾值ε1,ε2(ε1＞ε2)以控制步長變換和算法的終止迭代。ε1越 接近ε2，其執(zhí)行效率越高，但精度越低。因此，綜合效率與精度的要求，每次的步長變化取上一次迭代時步長的1/2。當支撐集長度未達到稀疏度K時，相鄰兩個階段中重建信號的能量差是不斷減小的，并且此能量差下降速度隨著階段數(shù)的增加而逐漸變緩，最終趨于穩(wěn)定。

3.3.3 基于能量的變步長稀疏度自適應策略

基于能量的變步長稀疏度自適應策略的核心思想是以測量向量與估計信號能量的比值為依據(jù)自適應地調整步長。其偽代碼如算法10所示。

此基礎建立在約束等距條件之上，為了提高稀疏度估計值的準確度，往往將判斷標準值ρ設置得比1.307大。在該策略小步長變換的步驟中(如算法10中(1), (2)所示)，不同文章的方法各有不同。文獻[15]采用支撐集長度每次增加原始步長1/2的方式更新步長；文獻[42]采用的策略是支撐集長度每次減半增加的方式更新步長。文獻[15]沒有擺脫會產生過估計或欠估計的弊端，但可以使算法快速收斂；文獻[42]中步長動態(tài)更新減半的方法更為精確，但是需要更長的時間完成收斂。

算法10 基于能量的變步長稀疏度自適應策略[12,33]

3.4 重構性能結果分析

為了直觀地比較各原子識別策略的重構性能，本文將每種策略所對應的原始算法在相同的實驗設置與硬件條件下進行了仿真對比。原始信號x為 隨機生成的高斯信號；感知矩陣A的參數(shù)選擇為M=32, N=128；稀疏度的仿真范圍為1～20，每個稀疏度下的重復實驗次數(shù)為1000次。所有的實驗均在運行于macOS big Sur 11.6操作系統(tǒng)、8GB RAM和Apple M1的MATLAB R2020b上實現(xiàn)。

第1組實驗比較了直接選取策略以及進階式原子識別策略所對應的原始算法的重構成功率與迭代次數(shù)。其中，重構成功率的定義采用了平均支撐集基數(shù)誤差，它用于測量恢復算法得到的估計支持集與原始信號的實際支持集間的平均誤差，其定義為

其中，I表示實際支持集，I?表示估計支持集。在參數(shù)設置中，閾值分段選擇策略中的閾值參數(shù)ts設置為10；弱選擇策略中的閾值參數(shù)ρ設置為0.75。

原子識別策略原始算法重構性能對比結果如圖2所示。圖2(a)為重構成功率的仿真結果，圖2(b)為迭代次數(shù)的仿真結果。由圖2(a)可得如下結論：

(1)采用正交最小二乘投影回溯策略的BAOMP在投影的基礎上利用回溯的手段而獲得了最優(yōu)秀的恢復效果。采用投影原子選擇策略的POMP、采用部分最小二乘投影策略的OMP-LS以及采用展望類策略的LAOMP, BLAOMP與OLS同樣以高額計算量為基礎獲得了良好的恢復成功率。其中，LAOMP的重構成功率最高，但其計算量與其他算法相比較高；BLAOMP采用并行選取手段在恢復精度上雖不如LAOMP，但極大地縮減了迭代次數(shù)；POMP在重構精度上略低于LAOMP，而由于在迭代過程中僅需比較投影系數(shù)值大小而不需要比較殘差值，其計算量遠小于LAOMP；OLS的重構精度同樣低于LAOMP，因其在每一次迭代過程中需要遍歷所有剩余原子，該算法的計算負擔較高。

(2)閾值類策略的重構精度因閾值設定方式的不同而略有差別。其中，采用弱選擇策略的SWOMP算法通過多原子選取方式并行更新投影系數(shù)，其恢復效果比OMP更加具有優(yōu)勢；采用閾值分段選擇策略的StOMP與采用模糊閾值策略的Fuzzy-OMP因其更簡單的計算復雜度犧牲了部分恢復精度。

(3)與采用壓縮采樣原子選擇策略的CoSaMP算法相比，采用子空間追蹤原子選擇策略的SP算法在更新殘差時多求解一步最小二乘問題，這使得后者的重構精度略高于前者。

迭代次數(shù)的仿真結果如圖2(b)所示。采用并行原子選擇方式的StOMP, Fuzzy-OMP, SWOMP以及BLAOMP算法均在6～8次迭代內收斂； BAOMP與GOMP使迭代次數(shù)相比于稀疏度量級降低了1～2次； CoSaMP以及SP算法均在5次迭代左右收斂，其中，前者的迭代次數(shù)略低于后者1～2次。此外，采用串行原子選取方式的OMP, POMP, LAOMP以及OLS算法，其迭代次數(shù)與稀疏度量級保持一致。

圖2 原子識別策略原始算法重構性能對比結果

第2組實驗比較了稀疏度自適應策略類算法的重構性能。在參數(shù)選擇中，步長統(tǒng)一設定為S=6。變步長稀疏度自適應策略中的閾值參數(shù)ε1,ε2分別設定為2和0.001；基于能量的變步長稀疏度自適應策略中能量閾值參數(shù)ρ設定為2，支撐集長度的更新方式采用了文獻[15]所提出的策略。

稀疏度自適應策略類算法重構成功率結果如圖3(a)所示。3種原子個數(shù)識別策略的重構成功率趨同。其中，采用基于能量的變步長稀疏度自適應策略的e-SAMP算法因其在變步長的基礎上以能量作為更新步長的依據(jù)，其重構成功率最高；采用固定步長稀疏度自適應策略的SAMP算法由于更新步長時的局限性，其恢復精度最低。

稀疏度自適應策略類算法迭代次數(shù)結果如圖3(b)所示。其中，采用基于能量的變步長稀疏度自適應策略的e-SAMP需要更多的迭代次數(shù)完成收斂； 采用變步長稀疏度自適應策略的MSAMP利用更精確的步長更新方式，使其恢復精度高于采用固定步長稀疏度自適應策略的SAMP，同時前者的迭代次數(shù)略高于后者。

圖3 稀疏度自適應策略類算法重構性能對比結果

4 結論

本文以貪婪類算法的原子識別策略為研究對象，對貪婪類重構算法的原子識別策略進行了歸納與總結，著重綜述了算法在不同處理階段可以運用的原子識別策略，并對其所對應原始算法的重構性能進行了分類仿真對比。在該綜述的基礎上，稀疏信號壓縮感知模型的重構算法創(chuàng)新更加便于實現(xiàn)，綜述中的原子識別策略也可以被拓展到聯(lián)合稀疏信號壓縮感知模型[43]以及塊稀疏信號壓縮感知模型的信號恢復算法中，從而實現(xiàn)跨模型算法的創(chuàng)新。