基于CS的稀疏度變步長自適應(yīng)壓縮采樣匹配追蹤算法

雷麗婷 李 剛 蔣常升 梁 壯

1(蘭州交通大學(xué)機(jī)電技術(shù)研究所 甘肅 蘭州 730070)2(甘肅省物流及運輸裝備信息化工程技術(shù)研究中心 甘肅 蘭州 730070)3(蘭州交通大學(xué)機(jī)電工程學(xué)院 甘肅 蘭州 730070)

0 引 言

Donoho[1]在2006年首次提出了壓縮感知理論，成為了信號領(lǐng)域的一種新理論[1-3]。Nyquist采樣定理局限性在于先采樣后壓縮，CS可以實現(xiàn)壓縮與采樣同時進(jìn)行，并且縮短了重構(gòu)時間。

重構(gòu)作為壓縮感知中最重要的部分，主要是指用低維的壓縮信號通過某種算法還原出高維原始信號的過程，因此，重構(gòu)算法的性能好壞將直接影響重構(gòu)結(jié)果的精度。目前重構(gòu)算法主要包括凸優(yōu)化算法和迭代貪婪算法[4]，其中使用較為廣泛的是迭代貪婪算法，因為它具有復(fù)雜度低和重構(gòu)用時短的優(yōu)勢。起初此算法主要包括匹配追蹤算法(Matching Pursuit，MP)和正交匹配追蹤算法(Orthogonal Matching Pursuit，OMP)[5]兩種，但將其廣泛運用于多個信號處理領(lǐng)域后發(fā)現(xiàn)其并不能滿足要求。許多學(xué)者針對其在殘差內(nèi)積的選擇過程中效率較低，處理能力與抗干擾能力隨著數(shù)據(jù)的復(fù)雜將變得均較弱等不足，提出了大量優(yōu)化和改進(jìn)的新算法。文獻(xiàn)[6]和文獻(xiàn)[7]分別提出了廣義正交匹配追蹤算法(generalized OMP，gOMP)及正則化正交匹配追蹤(Regularized OMP，ROMP)，通過每次迭代選取多個原子擴(kuò)充支撐集來提高重構(gòu)速度。文獻(xiàn)[8]為了找到重構(gòu)復(fù)雜度和重構(gòu)精度更好的折衷點，提出基于回溯思想的子空間追蹤(Subspace Pursuit，SP)算法。文獻(xiàn)[9]提出一個具有較大影響力的重構(gòu)算法——壓縮采樣匹配追蹤(Compressive sampling matching pursuit，CoSaMP)算法，對候選原子進(jìn)行了“二次”檢驗，提高了原子的正確匹配率。以上為第一類迭代貪婪算法，均要求已知稀疏度K，而實際稀疏度K是未知的。文獻(xiàn)[10]提出了稀疏度自適應(yīng)匹配追蹤算法(SAMP)，它具有計算速度快、算法簡單的優(yōu)點，但通過增加固定步長S的倍數(shù)，可逐漸增加至信號的真實稀疏度。因此，步長S的取值在重構(gòu)過程中顯得特別重要，取大或取小都將會影響重構(gòu)精度，甚至可能出現(xiàn)較大的重構(gòu)誤差[11]。

SAMP算法是目前使用較為廣泛的重構(gòu)算法之一，但其以固定步長逼近真實稀疏度K，初始步長的選取對于重構(gòu)性能影響很大。由于對于壓縮信號誤差來源于測量與恢復(fù)，原有的重構(gòu)算法中將殘差的2范數(shù)作為停止迭代的條件，這不能判斷迭代的準(zhǔn)確性。因此，本文以SAMP算法為主體，提出了一種稀疏度變步長自適應(yīng)壓縮采樣匹配追蹤(CSVssAMP)算法，采用CoSaMP算法中選出內(nèi)積值最大的2L列的思想，使用相鄰兩次迭代最小二乘解的差的2范數(shù)作為停止迭代的條件，再通過變步長的方式逼近稀疏度的真值。

1 壓縮感知理論

1.1 信號的稀疏分解

在實際應(yīng)用場景中，需要稀疏化目標(biāo)信號，表示如下：

x=Ψs

(1)

式中：Ψ為N×N的稀疏矩陣；s為K稀疏的矩陣。

1.2 信號的觀測矩陣φ的設(shè)計

在觀測矩陣的設(shè)計過程中，采用降低維度的方法使信號應(yīng)用更加簡單，為保證其信號的完整性，從觀測數(shù)據(jù)中準(zhǔn)確地還原原始信息，必須滿足有限等距理論(RIP)。在CS編碼測量模型中，可以通過式(2)得出原始信號x：

x=φx=φΨs=A

(2)

式中：φ可以選用高斯隨機(jī)矩陣。

1.3 信號的重構(gòu)算法設(shè)計

重構(gòu)算法就是利用觀測數(shù)據(jù)來恢復(fù)原始信號。當(dāng)測量矩陣滿足RIP條件時，經(jīng)過一系列的運算，通過y值重構(gòu)出目標(biāo)信號x，利用l0范數(shù)求解以下最優(yōu)化問題：

minα‖α‖l0s.t.y=φΨα

(3)

2 算法設(shè)計

根據(jù)稀疏度是否已知，將迭代算法分為兩類：第一類以O(shè)MP算法為基礎(chǔ)；第二類算法以SAMP算法[11]為代表。表1為本文中參與比較算法的簡單性能介紹。

表1 本文中參與比較算法性能的簡單介紹

2.1 算法描述

設(shè)Λt是t次迭代的索引集合，aj表示矩陣A的第j列，At={aj|j∈Ck}表示由索引集Ck選擇出的矩陣A的列集合(列數(shù)為Lt)，θt為Lt×1的列向量，〈·,·〉表示向量的內(nèi)積，abs[·]表示求模值(絕對值)。

步驟1初始化：r0=y，Λ0=?，L=S，t=1。

步驟2計算u=abs[ATrt-1](即計算〈rt-1,aj〉,1≤j≤N)，在u中選擇2L個最大值，其對應(yīng)于矩陣A的列序號j構(gòu)成集合Sk。

步驟3令Ck=Λt-1∪Sk，At={aj|j∈Ck}。

步驟4求y=Atθt的最小二乘解：

步驟8當(dāng)‖rnew‖2≥‖rt-1‖2時，如果‖rnew‖2/‖rt-1‖2≥β，(β是步長變換條件參數(shù)，取值為1.2)更新步長，L=L+S,t=t+1返回步驟2，當(dāng)時t=M，跳出迭代，進(jìn)入步驟9；如果1≤‖rnew‖2/‖rt-1‖2<β，更新步長：L=L+aS，t=t+1，返回步驟2，其中自適應(yīng)參數(shù)a∈(0,1)，當(dāng)t=M時，停止迭代，進(jìn)入步驟9。

2.2 算法流程

CSVssAMP算法流程如圖1所示。在整個流程圖中，要分別設(shè)置4個參數(shù)。步長S的值可以設(shè)置得大一些，以快速逼近K的真實值，從而縮短重構(gòu)時間。步驟7中，相鄰兩次迭代的最小二乘解的差的2范數(shù)被用作判斷迭代是否停止的條件，用α表示，通常取值為10-6。為了執(zhí)行步長變換，需要β來比較新舊殘差，使用自適應(yīng)參數(shù)a來調(diào)整步長，實現(xiàn)以小步長精準(zhǔn)逼近真實稀疏度。

圖1 CSVssAMP算法流程圖

2.3 算法應(yīng)用

CSVssAMP算法的應(yīng)用意義非常重要，特別是在需要高重構(gòu)效率的領(lǐng)域，如衛(wèi)星遙感數(shù)據(jù)的實時監(jiān)測。研究人員實時監(jiān)測衛(wèi)星有效載荷和運行的狀態(tài)，就是通過實時監(jiān)測遙感數(shù)據(jù)完成的。為了實現(xiàn)精準(zhǔn)的監(jiān)控，需要測量多個參數(shù)，并進(jìn)行長時間的實時數(shù)據(jù)采集，因此，需要考慮如何解決大量數(shù)據(jù)的采集和存儲的問題。經(jīng)大量相關(guān)研究，研究人員提出利用壓縮感知方法在信號采集端實現(xiàn)同步采樣和壓縮。為了實時分析和監(jiān)測衛(wèi)星運行狀態(tài)，測量數(shù)據(jù)通過無線傳感器網(wǎng)絡(luò)(WSN)實時傳輸?shù)降孛婵刂浦行模粸榱藗鬏數(shù)男枰瑴y量數(shù)據(jù)將被壓縮再傳輸給控制中心；為了保證能真實地反映衛(wèi)星的運行狀態(tài)，控制中心要對接收到的數(shù)據(jù)進(jìn)行實時重構(gòu)和信息交互。

3 實 驗

本節(jié)將對CSVssAMP算法的重構(gòu)效果進(jìn)行評估。實驗主要分為兩部分，一是不同稀疏度下重構(gòu)算法性能比較，二是不同觀測值下的重構(gòu)算法的性能比較分析。算法執(zhí)行的硬件條件為Intel(R) Core(TM)(i5-3470 CPU)和MATLAB 7.0。

3.1 不同稀疏度下算法性能比較

本文選取高斯稀疏信號作為評價指標(biāo)，通過信號在不同稀疏度K下的重構(gòu)成功率和平均重構(gòu)時間進(jìn)行對比，對新算法的重構(gòu)效果進(jìn)行驗證。實驗設(shè)置數(shù)據(jù)長度N=256，測量值M=128。

3.1.1 重構(gòu)成功概率比較

本文分別對第2節(jié)介紹的6種算法和本文算法進(jìn)行了仿真，得出重構(gòu)成功率-K值的變化趨勢圖，如圖2所示。不同K值循環(huán)迭代1 000次，閾值γ=10-6。實驗參數(shù)設(shè)定如下：CSVssAMP算法中S=5，α=10-6和β=1.2。

圖2 不同K值下7種算法的重構(gòu)成功概率比較

可以看出，對于所有重構(gòu)算法，如果保持N和M始終不變，則重構(gòu)成功的概率曲線將隨著K值的增加而呈現(xiàn)下降趨勢，這是由于具有較高不確定性的原始信號限制了信息的獲取。總體而言，CSVssAMP算法的重構(gòu)能力明顯優(yōu)于已有的重構(gòu)算法，在相同的K值下，其重構(gòu)能力也有相應(yīng)的提高，100%重構(gòu)時算法的K值最大。

3.1.2 平均重構(gòu)時間比較

考慮到CSVssAMP算法以SAMP算法為主體進(jìn)行了相應(yīng)的改進(jìn)，通過考察兩種算法的重構(gòu)時間，來驗證本文算法的優(yōu)越性。步長設(shè)置如下：SAMP算法中S=5，CSVssAMP算法中S=10。不同K值下兩者的重構(gòu)時間比較如圖3所示。

圖3 不同K值下SAMP算法和改進(jìn)算法的重構(gòu)時間比較

可以看出，當(dāng)稀疏度K為45、50、55和60時，重構(gòu)時間分別縮短了22.2%、38.4%、41.5%和45.8%。因此， CSVssAMP算法的重構(gòu)效果更好。

3.2 不同測量值下算法性能比較

對于目標(biāo)信號，由于傳感器數(shù)據(jù)傳輸?shù)臄?shù)量有限，由迭代算法恢復(fù)的觀測信號的長度將會受到限制。本文通過將稀疏度一定時信號在不同測量值M下的重構(gòu)成功率和平均重構(gòu)時間進(jìn)行對比，對新提出算法的性能進(jìn)行評估。

3.2.1 重構(gòu)成功概率比較

目標(biāo)信號的選取與3.1.1節(jié)的相同，實驗設(shè)置數(shù)據(jù)長度N=256，稀疏度K=20，采用OMP、ROMP、CoSaMP、SP、StOMP、SAMP和本文算法在不同測量值M下進(jìn)行仿真，其重構(gòu)成功概率比較如圖4所示。

圖4 不同M值下7種算法的重構(gòu)成功概率比較

為了更好地比較每種迭代算法的恢復(fù)還原能力，設(shè)置信號的測量值M∈[50,100]，通過分析和比較，重構(gòu)成功率的變化曲線圖隨著M值的增加呈現(xiàn)上升趨勢，即重構(gòu)成功的概率隨著測量值的增加而增加，因為隨著測量值的增加，獲得的原始信號的信息越來越多，則恢復(fù)出的原始信號精度更高。當(dāng)測量值M相同時，SAMP算法優(yōu)于其他5種算法，并且CSVssAMP算法的性能也得到進(jìn)一步的提高。100%重構(gòu)時CSVssAMP算法的M值最小。

3.2.2 平均重構(gòu)時間比較

考慮到CSVssAMP算法是以SAMP算法為主體算法進(jìn)行了相應(yīng)的改進(jìn)，通過考察兩種算法的重構(gòu)時間，來驗證本文算法的優(yōu)越性。隨機(jī)選取5個測量值M分別進(jìn)行對比，目標(biāo)信號的平均重構(gòu)時間如圖5所示。步長設(shè)置如下：SAMP算法中S=4，CSVssAMP算法中S=8。

圖5 不同測量值下SAMP算法和改進(jìn)算法的重構(gòu)時間比較

可以看出，當(dāng)測量值M為50、55、60、65和70時，重構(gòu)時間分別縮短了33.3%、29.6%、35.7%、33.8%和30.6%。因此，不同M值下，CSVssAMP算法具有更好的恢復(fù)性能。

3.3 不同步長下算法性能比較

為了更好地驗證CSVssAMP算法具有更好的恢復(fù)能力，通過使用不同的步長，繪制M值與重構(gòu)成功概率之間的關(guān)系曲線圖，其中步長S為2和8的情況如圖6所示。

圖6 不同步長下SAMP算法和改進(jìn)算法重構(gòu)成功率比較

可以看出：總體上，重構(gòu)成功率隨著步長減小而增加，因為步長減小的同時可以實現(xiàn)以小步長逼近真實稀疏度值。在相同S下，CSVssAMP算法和SAMP算法的兩條曲線非常接近，特別是當(dāng)S=2時，前者略好于后者；當(dāng)S=8時，可以更好地體現(xiàn)CSVssAMP算法的高重構(gòu)性能。

4 結(jié) 語

本文通過對多種重構(gòu)算法的重構(gòu)性能進(jìn)行分析和比較，發(fā)現(xiàn)第一類迭代算法無法解決稀疏度未知的信號的重構(gòu)問題，并且它們均采用固定步長進(jìn)行迭代實驗。針對原始算法中存在的問題，以SAMP算法為主體算法，采用自適應(yīng)調(diào)整方法來選擇最優(yōu)的稀疏度K。綜上，本文提出了稀疏度變步長自適應(yīng)壓縮采樣匹配追蹤 (CSVssAMP)算法。與SAMP算法相比，本文算法采用了CoSaMP的思想(CoSaMP選2L個原子，而SAMP選L個)，保證了每次迭代都有2L個原子留下來，實現(xiàn)了在低噪聲信號下高精度的重構(gòu)。應(yīng)用雙閾值以實現(xiàn)步長的自適應(yīng)變化，以更大的步長快速靠近真實的K值，然后再以小步長完成精準(zhǔn)逼近，通過提高重構(gòu)速率來實現(xiàn)更高的恢復(fù)精度。仿真結(jié)果表明，當(dāng)稀疏度K和測量值M不同時，本文算法的性能均有明顯提升。本文算法能夠縮短重構(gòu)時間，使用步長自適應(yīng)對原始的固定步長進(jìn)行了替換，重構(gòu)效果得到進(jìn)一步的提高。