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

雷麗婷 李 剛 蔣常升 梁 壯

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

0 引 言

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

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

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

1 壓縮感知理論

1.1 信號的稀疏分解

在實際應用場景中，需要稀疏化目標信號，表示如下：

x=Ψs

(1)

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

1.2 信號的觀測矩陣φ的設計

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

x=φx=φΨs=A

(2)

式中：φ可以選用高斯隨機矩陣。

1.3 信號的重構算法設計

重構算法就是利用觀測數據來恢復原始信號。當測量矩陣滿足RIP條件時，經過一系列的運算，通過y值重構出目標信號x，利用l0范數求解以下最優化問題：

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

(3)

2 算法設計

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

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

2.1 算法描述

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

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

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

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

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

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

2.2 算法流程

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

圖1 CSVssAMP算法流程圖

2.3 算法應用

CSVssAMP算法的應用意義非常重要，特別是在需要高重構效率的領域，如衛星遙感數據的實時監測。研究人員實時監測衛星有效載荷和運行的狀態，就是通過實時監測遙感數據完成的。為了實現精準的監控，需要測量多個參數，并進行長時間的實時數據采集，因此，需要考慮如何解決大量數據的采集和存儲的問題。經大量相關研究，研究人員提出利用壓縮感知方法在信號采集端實現同步采樣和壓縮。為了實時分析和監測衛星運行狀態，測量數據通過無線傳感器網絡(WSN)實時傳輸到地面控制中心；為了傳輸的需要，測量數據將被壓縮再傳輸給控制中心；為了保證能真實地反映衛星的運行狀態，控制中心要對接收到的數據進行實時重構和信息交互。

3 實 驗

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

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

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

3.1.1 重構成功概率比較

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

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

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

3.1.2 平均重構時間比較

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

圖3 不同K值下SAMP算法和改進算法的重構時間比較

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

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

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

3.2.1 重構成功概率比較

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

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

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

3.2.2 平均重構時間比較

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

圖5 不同測量值下SAMP算法和改進算法的重構時間比較

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

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

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

圖6 不同步長下SAMP算法和改進算法重構成功率比較

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

4 結 語

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