基于壓縮感知的貪婪類重構(gòu)算法原子識(shí)別策略綜述

劉素娟 崔程凱 鄭麗麗 江書(shū)陽(yáng)

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

1 引言

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

壓縮感知重構(gòu)算法主要包括貪婪算法、凸優(yōu)化算法和其他算法。貪婪類算法由于其硬件實(shí)現(xiàn)的簡(jiǎn)便易行得到了廣泛學(xué)者的青睞。匹配追蹤算法(Matching Pursuits, MP)[4]奠定了貪婪算法的基礎(chǔ)，其核心思想是利用原子向量的線性運(yùn)算去逐漸逼近信號(hào)向量，經(jīng)過(guò)不斷迭代，最后選擇出以稀疏度為參考個(gè)數(shù)的原子。但是在迭代過(guò)程中，如果殘差在已選擇原子上的垂直投影是非正交的，則迭代后得到的結(jié)果將不是最優(yōu)的而是次優(yōu)的。這會(huì)導(dǎo)致在后續(xù)迭代過(guò)程中可能會(huì)重復(fù)選擇到相同的索引，算法收斂需要更多的迭代次數(shù)。正交匹配追蹤算法(Orthogonal Matching Pursuit, OMP)[5]作為貪婪類算法繼續(xù)發(fā)展的重要基礎(chǔ)，克服了MP算法的缺陷。 在OMP算法的迭代過(guò)程中，殘差總是能夠與已經(jīng)選擇過(guò)的原子正交，這保證了相同的索引不會(huì)被重復(fù)選擇，迭代過(guò)程將會(huì)在有限的幾步內(nèi)收斂。在OMP算法基礎(chǔ)之上，正則化正交匹配追蹤算法(Regularized Orthogonal Matching Pursuit,ROMP)[6]及其變體[7]，廣義正交匹配追蹤算法(generalized Orthogonal Matching Pursuit,gOMP)[8]及其變體[9]，分段正交匹配追蹤算法(Stagewise Orthogonal Matching Pursuit,StOMP)[10]及其變體[11]，稀疏度自適應(yīng)匹配追蹤算法(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ù)被提出。算法的更新趨勢(shì)是在已存在的算法原型上進(jìn)行改進(jìn)，使新算法在提高恢復(fù)性能、降低計(jì)算復(fù)雜度以及減少計(jì)算時(shí)間成本等方面更加具有優(yōu)勢(shì)。

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

2 壓縮感知模型

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

3 貪婪類重構(gòu)算法原子識(shí)別策略

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

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

圖1 壓縮感知模型

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

3.1 一步式原子識(shí)別策略

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

3.1.1 內(nèi)積原則選取策略

內(nèi)積原則選取策略依據(jù)感知矩陣A的列向量與殘差r的內(nèi)積絕對(duì)值大小選擇原子，根據(jù)St=arg max(|〈A,rt-1〉|)從內(nèi)積絕對(duì)值中選擇最大元素對(duì)應(yīng)的一個(gè)索引并入最終支撐集，這里稱為內(nèi)積原則，它是所有貪婪算法的起點(diǎn)。此外，為了進(jìn)一步加快算法收斂速度，可以通過(guò)內(nèi)積原則并行選擇出前L個(gè)內(nèi)積絕對(duì)值較大元素對(duì)應(yīng)的原子并入最終支撐集以減少迭代次數(shù)。用到該策略的貪婪類算法有很多，區(qū)別在于不同算法對(duì)于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ù)的其他策略中調(diào)用此原則，將其記為式(5)中的函數(shù)supp_max_L

3.1.2 弱選擇策略

原子的弱選擇策略以當(dāng)前迭代過(guò)程中最大內(nèi)積絕對(duì)值的ρ倍為判斷標(biāo)準(zhǔn)，將內(nèi)積絕對(duì)值中大于該標(biāo)準(zhǔn)的原子選擇出來(lái)，其中，0＜ρ ＜1[11]，其形式如式(6)所示

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

3.1.3 閾值分段選擇策略

閾值分段選擇策略的核心思想是通過(guò)設(shè)定一個(gè)動(dòng)態(tài)更新的閾值作為原子的選擇標(biāo)準(zhǔn)來(lái)并行地更新最終索引集，可用式(7)表示

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

3.2 進(jìn)階式原子識(shí)別

進(jìn)階式原子識(shí)別策略是在選擇出潛在支撐集或候選支撐集的基礎(chǔ)上進(jìn)一步精確挑選原子，以此提高算法的重構(gòu)準(zhǔn)確度。

3.2.1 模糊閾值策略

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

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

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

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

部分最小二乘投影策略的核心思想是將投影值作為原子選擇的判斷標(biāo)準(zhǔn)。通過(guò)比較投影值的大小，將最大的投影值所對(duì)應(yīng)的原子作為當(dāng)前迭代過(guò)程選中的結(jié)果，其過(guò)程如式(8)所示

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

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

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

增量最小二乘投影回溯策略中， T R表示開(kāi)始標(biāo)志，即為算法執(zhí)行前期與執(zhí)行后期的分界線，且TR＜K。在迭代次數(shù)大于開(kāi)始標(biāo)志后，該策略每?jī)纱蔚厮?次，即增加2個(gè)索引后再通過(guò)回溯剔除掉1個(gè)，剔除的標(biāo)準(zhǔn)以投影值的大小為依據(jù)。

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

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

基于投影的原子選擇策略的核心思想是以投影值作為原子選擇標(biāo)準(zhǔn)，將投影值較大的原子所對(duì)應(yīng)的索引并入最終支撐集。其偽代碼如算法3所示。

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

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

3.2.5 壓縮采樣原子選擇策略

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

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

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

3.2.6 展望策略

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

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

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

3.2.7 并行展望策略

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

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

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

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

正交最小二乘一步展望策略與展望策略的核心思想類似，不同之處在于前者以待選原子在當(dāng)前迭代過(guò)程中最小化殘差的能力大小為標(biāo)準(zhǔn)來(lái)選擇原子，即正交最小二乘一步展望策略側(cè)重于當(dāng)前迭代過(guò)程對(duì)下一個(gè)原子選擇的影響，而展望策略側(cè)重于當(dāng)前迭代過(guò)程對(duì)最終結(jié)果的影響。其偽代碼如算法7所示。

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

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

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

3.3 稀疏度自適應(yīng)策略

本節(jié)所介紹的內(nèi)容與直接原子識(shí)別策略不同。當(dāng)稀疏度未知時(shí)，需要通過(guò)自適應(yīng)策略得出信號(hào)稀疏度的估計(jì)數(shù)值。稀疏度的估計(jì)值決定了原子識(shí)別過(guò)程所選取的原子個(gè)數(shù)。將稀疏度自適應(yīng)的過(guò)程稱為原子個(gè)數(shù)識(shí)別。在稀疏度未知的情況下，對(duì)稀疏度的準(zhǔn)確估計(jì)能夠保證重構(gòu)信號(hào)的精度。

3.3.1 固定步長(zhǎng)稀疏度自適應(yīng)策略

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

算法8 固定步長(zhǎng)稀疏度自適應(yīng)策略[12,26]

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

3.3.2 變步長(zhǎng)稀疏度自適應(yīng)策略

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

算法9 兩閾值變步長(zhǎng)稀疏度自適應(yīng)策略[16]

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

3.3.3 基于能量的變步長(zhǎng)稀疏度自適應(yīng)策略

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

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

算法10 基于能量的變步長(zhǎng)稀疏度自適應(yīng)策略[12,33]

3.4 重構(gòu)性能結(jié)果分析

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

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

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

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

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

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

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

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

圖2 原子識(shí)別策略原始算法重構(gòu)性能對(duì)比結(jié)果

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

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

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

圖3 稀疏度自適應(yīng)策略類算法重構(gòu)性能對(duì)比結(jié)果

4 結(jié)論

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