一種稀疏度自適應分段正交匹配追蹤算法

唐朝偉，王雪鋒，杜永光

(重慶大學 通信工程學院，重慶，400044)

一種稀疏度自適應分段正交匹配追蹤算法

唐朝偉，王雪鋒，杜永光

(重慶大學 通信工程學院，重慶，400044)

針對分段正交匹配追蹤(StOMP)算法需要信號的稀疏度作為先驗信息且重構精度較低的特點，提出一種稀疏度自適應分段正交匹配追蹤算法。首先，通過對觀測矩陣與初始殘差相乘所得的殘余相關性向量進行離散余弦變換，估算出支撐集所要擴充的最大原子數；其次，采用與抽樣率成正相關的因子對較大的閾值參數進行適當修正，并對通過設定閾值所選取的原子進行優化處理；最后在StOMP算法的框架下采用變步長的方法實現稀疏度的逼近和信號的精確重構。仿真結果表明：本文所提出的算法對信號的稀疏度具有很好的自適應特性，并且在保持了較低重構復雜度的同時具有更穩定的重構質量。

壓縮感知；分段正交匹配追蹤；稀疏度自適應；重構性能

傳統的信號采樣理論Nyquist采樣定理要求信號的采樣頻率至少為信號帶寬的2倍，才能無失真地恢復原始信號。DONOHO等[1?2]提出的壓縮感知理論，從信號稀疏分解和逼近角度建立了一種新的信號描述和處理的理論框架，能夠在保證信息不損失的情況下，采用遠低于奈奎斯特采樣定理要求的速率來采樣信號，即如果信號在某個變換域是稀疏的或者是可壓縮的，壓縮感知理論便可以利用一個與變換基不相關的觀測矩陣，將變換所得的高維信號投影到一個低維空間上，根據這些少量的觀測值，通過求解凸優化問題就能實現信號的精確重構。這一理論能夠有效降低信號在獲取、存儲及傳輸過程中的數據量，在信號采集與處理方面帶來了新的變革。重構算法是壓縮感知理論中的關鍵問題之一，它要求在已知觀測矩陣和觀測向量的前提下，能高效且精確地對原始信號進行重建。目前較常用的重構算法有凸優化、組合優化和貪婪算法等，而其中的貪婪算法(通過貪婪迭代的方法來更新支撐集，并逐步逼近原始解)因其運算量小、算法簡單且具有一定的重構精度而被廣泛采用。貪婪算法中最早提出的有匹配追蹤(matching pursuit, MP)、正交匹配追蹤(orthogonal matching pursuit, OMP)[3]算法，但是這2種算法在重構效率和精度上不夠理想；正則化正交匹配追蹤(regularized orthogonal matching pursuit, ROMP)[4]利用正則化的方法找出候選原子集合中能量最大的原子集合來更新支撐集，壓縮采樣匹配追蹤(compressive sampling matching pursuit, CoSaMP)[5]采用“回溯”思想來更新支撐集，這2種算法都在一定程度上提高了重構精度；分段正交匹配追蹤(stagewise orthogonal matching pursuit, StOMP)[6]算法通過設定閾值進行原子的批量選取，是一種運行效率較高的重構算法，但重構精度較差；同時，上述貪婪算法均要求信號的稀疏度已知，如果對稀疏度的估計不準確，很多信號將不能得到精確重建，但是這種前提在實際應用中難以滿足，稀疏度自適應匹配追蹤(sparsity adaptive matching pursuit, SAMP)[7]是一種不受信號稀疏度影響的重構算法，它通過預設初始步長，并在每次迭代中增加固定的步長來逐步實現對信號稀疏度的估計，同時更新殘差及支撐集以逼近原始信號，但從總體上來說該算法的重構效率較低。本文作者針對StOMP算法，提出一種稀疏度自適應且重構性能較好的改進算法，利用離散余弦變換具有能量集中的特性，估算出支撐集所要擴充的最大原子數目，并對較大的閾值參數進行修正來調節所選取的原子數目，同時對所選取的原子進行預處理并引入自適應調節步長的方法，保證用于更新支撐集原子的最佳匹配性，實現信號稀疏度的逼近和精確重構，仿真結果驗證了本文所提算法在信號稀疏度自適應性和重構性能上的優越性。

1　壓縮感知與StOMP算法

1.1壓縮感知理論

壓縮感知理論的本質是一種非適應性的、非線性的可壓縮信號的重建方法，它包含3個重要的內容：信號的稀疏表示、觀測矩陣測量和重構算法。

1) 信號的稀疏表示。如果長度為N的信號x∈RN在某變換域中只有K個系數不為0(或者明顯大于其他系數)，且 K＜＜N，那么可以認為信號x在該變換域中是稀疏的，也可稱為K-稀疏。若信號在稀疏基上的表示為S，則該稀疏變換過程可以表述如下：

3) 壓縮感知算法重構。從M個測量值出發，借助觀測矩陣Φ和重構算法來重建或者逼近原始信號x。在x是K-稀疏的情況下，可以把信號的重構等價于一個尋求在約束條件下的最優解問題[8?9]，表述如下：

1.2觀測矩陣的選取

為了能夠精確地重建稀疏或可壓縮信號，對任意的K-稀疏信號x，觀測矩陣Φ必須要滿足限制等容特性(restricted isometry property, RIP)：

其中：ΦP為Φ中由P為索引的相關列所構成的矩陣；δk為對所有K稀疏信號滿足上述特性的最小常數；c為投影到ΦP的系數序列。并且約束等距性說明Φ的行不能由Ψ的列稀疏表示，而Ψ的列也不能由Φ的行稀疏表示，即觀測矩陣Φ與稀疏基Ψ不相關與約束等距性是等價的[2]，由于高斯隨機矩陣與大多數由正交基構成的矩陣不相關，因此，選擇高斯隨機矩陣作為觀測矩陣可以很好地滿足RIP特性。

此外，選擇對高斯隨機矩陣進行正交化處理，將會使觀測矩陣具有很好的去相關性[10]：

其中：Λ為特征值矩陣，是對角陣。從式(5)可以看出：信號從高維到低維投影之后的樣本之間相關系數為0，即不相關，因此，在觀測矩陣的選取上，正交化高斯隨機矩陣是一個很好的選擇。當觀測矩陣Φ與稀疏基Ψ滿足RIP準則時，在觀測過程中能夠保 證信號的重要信息不丟失，這將有助于信號的精確重建。

1.3分段正交匹配追蹤(StOMP)算法

對于壓縮感知中的正交匹配追蹤算法而言，它每次從觀測矩陣中僅選取1個最佳原子，雖然這種方式在一定程度上保證了圖像重構的精確度，但不可避免地造成該算法在整個原子選取的過程中，因匹配次數太多而增大計算量并最終降低整個重構過程的效率。而StOMP算法本質就在于每次匹配時選出的并不是1個原子，而是通過設定閾值選取多個原子，形成1個初始的原子集合，然后更新支撐集，并利用最小二乘法求得近似解，同時完成對殘差的更新，最后來檢查是否滿足終止條件，若不滿足，則以更新的殘差繼續進行原子的匹配追蹤，從而大大減少匹配次數，提高重構效率。

StOMP算法步驟：

StOMP算法在選取原子時進行了一定程度的簡化，提高了算法執行速度，但它也有自身的不足：1) 由于其在每次迭代的過程中尋找的都不是信號最佳匹配原子，因此導致信號的重構精度低于OMP算法的重構精度，重構的穩定性也不能得到保證[11]；2) 該算法通過設定閾值ts=θδs每次選取多個原子更新支撐集，但在實際操作中，閾值參數θ的選擇較難[11]；3) 需要指出的是StOMP算法需要信號的稀疏度作為先驗知識，只有正確估計了信號的稀疏度，才能精確地重構原始信號。然而，對于實際信號(如語音和圖像在其稀疏域上僅是近似稀疏的)，難以準確估計其稀疏度。

2　稀疏度自適應StOMP算法

針對上述StOMP算法的不足，本文在深入研究離散余弦變換(discrete cosine transform, DCT)變換的特點、閾值參數對原子選取的影響和稀疏度自適應算法[12?13]的基礎上，提出了一種具有稀疏度自適應且重構性能較好的算法。其主要思想是：首先對觀測矩陣與初始殘差相乘所得的殘余相關性向量進行DCT變換，估算出支撐集所要擴充的最大原子數；然后，采用一個與抽樣率成正相關的因子對較大閾值參數進行修正，并對通過設定閾值所選取的原子進行優化排序，再比較原子集合內原子的數目和此時的步長，確定所要選取的原子數目，更新支撐集；最后在StOMP算法框架下，不斷更新步長和擴充支撐集，在逐步逼近信號稀疏度的同時獲得信號的精確重構。以下從支撐集最大原子數目估計及原子預處理、閾值參數修正、稀疏度自適應和算法步驟等4個方面對稀疏度自適應StOMP算法進行描述。

2.1支撐集最大原子數目估計及原子預處理

2.1.1支撐集最大原子數目估計

在圖像視頻編碼中，經常采用DCT或者基于DCT的變換(如H.264的整數變換)來提高編碼效率，同時取DCT變換之后的局部DCT系數進行反變換或者對DCT系數的局部測量值進行壓縮感知重構，通常能以極大的概率來恢復原始數據[14]。重構算法中，需要從觀測矩陣Φ和M維觀測向量y出發，得到1個N維的重構向量。在本文中利用DCT變換來估計支撐集最大原子數目：首先，觀測矩陣與該觀測向量(初始殘差)相乘得到殘余相關性向量；然后對向量VCR進行DCT變換，將所得向量中的元素按絕對值大小進行排序，并把該向量最后M個數值較小的系數置0，利用離散余弦變換較強的能量集中特性，找出最能代表該向量能量的一批原子 (在該算法中，所選取原子的能量占原子總能量的90%)，并設定這批原子的數目為支撐集所要擴充的最大數目Lmax。

2.1.2原子預處理

通過設定閾值，每次迭代時都將選取一批原子，定義觀測矩陣Φ與更新殘差rs的內積為Cs，即，那么這些原子就是Cs中大于閾值的數值對應的索引值所形成的候選集。在本文中對候選集中的原子做一定的處理：首先，找出候選集中的原子對應在向量Cs中的數值，然后對這些數值進行降序排列，并依次返回這些數值對應在向量Cs中的位置，形成新的候選集，此時該候選集中的第1個索引值就對應向量Cs中的最大值，即該索引值為最優匹配原子，第2個索引值為次優匹配原子。這樣，在算法進程中，總能優先選出最為匹配的一些原子來擴充支撐集。

2.2閾值參數修正

選取Lena和Boat 2幅標準測試圖像，設定不同的抽樣率r，測試StOMP算法在不同閾值參數θ下重構圖像的峰值信噪比(peak signal to noise ratio，PSNR)，結果分別如表1和表2所示。

由表1和表2可知：對于Lena和Boat 2幅圖像，在抽樣率相對較低的條件下，當閾值參數較低時，由于篩選出的候選集原子較多，造成過度估計而影響重建效果，從而峰值信噪比較低；當閾值參數過高時，由于篩選出的候選集原子數較少而降低了重建質量，峰值信噪比也較低。因此，閾值參數的選取對圖像的重建效果有著很大的影響。

圖像處理中，低抽樣率具有較好的實用意義，而且，當閾值參數較大時(θ取值范圍為[2.6,3])，StOMP算法因候選集選取的原子較少而具有更高的重構效率，但圖像的重構質量不佳。因此，綜合考慮重構效率與重構精度，當閾值參數較大時，可以適當修正閾值參數[15?16]，本文通過一個與抽樣率成正相關的因子來調節閾值參數，即(本文采用的修正因子為)，通過適當降低閾值參數來增加候選集原子數，達到提升重建精度的目的。

表1　不同閾值參數下Lena重構圖像的峰值信噪比Table 1 PSNR of reconstructed Lena image with different threshold parameters　dB

表2　不同閾值參數下Boat重構圖像的峰值信噪比Table 2 PSNR of reconstructed Boat image with different threshold parameter　dB

2.3稀疏度自適應

在信號稀疏度未知的情況下，本文算法將迭代過程分為若干個階段，在每個階段均進行步長的調整，并根據步長實現對候選集中原子的階段性選取[17?18]，隨著迭代過程的分段進行，步長不斷地更新，稀疏度的近似估計和支撐集的擴充也同步進行。首先，設定初始步長；然后通過設定閾值形成原子候選集，經過原子預處理之后，對此時候選集內的原子數目與當前步長進行判定，如果候選集內原子數目大于步長Ls，那么僅選取候選集中前Ls個索引值用于擴充支撐集，否則全部用于支撐集的擴充，隨著重構過程的進行，逐步對步長進行更新，并完成稀疏度的近似估計，此時支撐集得到了有效擴充，能夠用于信號的精確重構。

增設算法的終止條件為支撐集內的原子數目達到一定的數量Lmax，這樣在保證用于重構信號時有一定的原子數目，提高重構精度的同時，也在一定程度上彌補了當信號稀疏度較大時，會因迭代次數較多導致運算量過大的不足，即在原子數目達到一定數量后，算法不再進行迭代運算，從而保證了算法的重構效率。

2.4算法步驟及分析

算法中步驟1)～3)通過對殘余相關性向量的DCT變換處理，估計了迭代中支撐集所要擴充的最大原子數目，步驟4)通過設定閾值來選取一部分原子形成候選集，通過步驟5)的原子預處理，使候選集的索引值順序對應內積Cs中從大到小的數值，從而保證在步驟6)中總能優先選出最為匹配的一些原子來擴充支撐集Is，步驟6)和7)實現了利用最小二乘法逼近原始信號和余量的更新，在步驟8)中，首先檢查算法是否終止，否則進入下一階段并更新步長后轉入步驟4)。

3　實驗結果及分析

本文實驗中，稀疏變換采用離散小波變換DWT (discrete wavelet transform)；觀測矩陣為高斯隨機矩陣(gaussian random matrix，GRM)和正交化高斯隨機矩陣(orthogonalized gaussian random matrix，OGRM)，具體使用將在各部分實驗中作出說明；對于本文的仿真結果，采用主客觀相結合的標準進行評價：對各算法的重構圖像進行主觀評價，用峰值信噪比(dB)來客觀評價各種算法的重構質量，用重構時間(s)來客觀評價各種算法的重構復雜度；各算法的峰值信噪比和運行時間均為200次實驗的平均結果。本實驗在酷睿雙核2.20 GHz，2 GB內存的PC機上，通過MATLAB R2010a仿真完成。

3.1不同閾值參數條件下信號重構性能仿真及分析

本節實驗采用大小為256×256的Lena圖像、512×384的Peppers圖像、346×207的Canoe圖像和240×320的Football圖像作測試，觀測矩陣分別采用高斯隨機矩陣(GRM)和正交化高斯隨機矩陣(OGRM)，取固定的抽樣率r=0.5，閾值參數θ取值范圍為[1,3]，其他條件保持一致，在不同閾值參數條件下，StOMP和本文算法對四幅圖像的重構曲線如圖1所示。

由圖1可知：對于4幅測試圖像，當觀測矩陣為高斯隨機矩陣時，StOMP算法在閾值參數為[2, 3]時具有較好的重構效果；當觀測矩陣為正交化高斯隨機矩陣時，StOMP算法在閾值參數為[1.6, 2.4]時具有較好的重構效果。而本文提出的算法，選取相同的觀測矩陣時，在不同閾值參數條件下均比StOMP算法具有更好地重構效果，且重構效果較為穩定。因此，本文所提出的算法在閾值參數的選取上會具有更大的靈活性，能更好地應用于圖像處理領域。

3.2不同稀疏度條件下信號重構性能仿真及分析

本節實驗比較MP，OMP，CoSaMP，SAMP，StOMP和本文算法在不同稀疏度條件下的正確重構概率和重構時間。采用長度為N=256的高斯稀疏信號，測量數目M=128，K的取值范圍為[1, 80]。在本部分實驗中，當觀測矩陣為高斯隨機矩陣時，StOMP和本文算法的閾值參數取值范圍選擇[2, 3]；當觀測矩陣為正交化高斯隨機矩陣時，2種算法的閾值參數取值范圍選擇[1.6, 2.4]，2種情況下各取10個閾值參數，以不同閾值參數下的正確重構概率的平均值作為該算法的正確重構概率。定義信號正確重構的原則是重構信號與原始信號x中的非零元素的位置相同，并且殘差能量小于一定閾值，取。實驗中MP， OMP和StOMP算法的實現采用的是Sparselab工具箱，CoSaMP和SAMP算法參考的是Compressive Sensing Resources程序包。觀測矩陣為高斯隨機矩陣和正交化高斯隨機矩陣時，各算法在不同的稀疏度下的重構性能見圖2和圖3。

由圖2(a)可知：當觀測矩陣為高斯隨機矩陣時，本文算法的正確重構率高于MP，OMP，CoSaMP和StOMP等算法，在一定程度上低于SAMP算法；圖3(a)表明：當觀測矩陣為正交化高斯隨機矩陣時，本文算法比MP，OMP，CoSaMP和StOMP算法具有更高的正確重構率，與SAMP算法的重構精度相當，只是在稀疏度大于0.25時才會有較多的信息不能夠正確重構。由圖2(b)和3(b)可知：采用不同的觀測矩陣時，本文算法通過設置最大擴充原子數目，相比于SAMP算法而言，避免了過多的迭代計算，運行效率遠高于SAMP算法，與StOMP算法重構效率相當。可見，本文所提出的算法提高了稀疏度較大時的信號正確重構率，尤其是采用正交化高斯隨機矩陣作為觀測矩陣時，具有更好的稀疏度自適應性。

圖1　不同閾值參數下StOMP和本文算法的重構曲線Fig. 1 Reconstruction curve of StOMP and the proposed algorithm with different threshold parameters

圖2　各算法基于高斯隨機觀測矩陣在不同稀疏度下的重構性能Fig. 2 Reconstruction performance of algorithms with different sparsity when sensing matrix is GRM

3.3算法在圖像處理中的應用

本節實驗驗證MP，OMP，CoSaMP，SAMP，StOMP和本文算法等在圖像處理中的實用性。測試圖像選擇Lena圖像，其中SAMP和本文算法的初始步長取值均為Ls=9，StOMP和本文算法的閾值參數均取θ=2，觀測矩陣均采用正交化高斯隨機矩陣，抽樣率取值分別為0.4，0.5和0.6，其他條件均保持一致，圖4所示為抽樣率r=0.5時各算法的重構圖像，表3所示為不同抽樣率下各算法的重構性能。

由圖4可知：本文算法和SAMP算法具有較好的圖像重構效果。由表3可知，從重構峰值信噪比的角度來看，在相同的抽樣率下，SAMP和本文算法的峰值信噪比要明顯高于其他幾種算法，其中，在r=0.5時，本文算法的PSNR比StOMP算法的峰值信噪比高1.2 dB左右，與SAMP算法重構精度相當，這主要歸因于用于更新支撐集的原子都是最為匹配的，即本文算法能獲得比StOMP算法更好的圖像重構效果。從運行效率的角度來看，在相同的抽樣率下，StOMP和本文算法的重構時間要小于其他幾種算法的重構時間，其中，本文算法的重構時間要遠遠小于SAMP算法的重構時間，這主要歸因于支撐集最大擴充原子數目的估計，相較于SAMP算法，受到步長的影響較小，且本文算法的重構時間略大于StOMP算法的重構時間，即本文算法保持了StOMP算法重構復雜度較低的優點。綜合來說，本文所提出的算法在保持了原算法較高運行效率的同時，具有了更好的圖像重構精度，在圖像處理領域中會具有很好的實用意義。

圖3　各算法基于正交化高斯隨機觀測矩陣在不同稀疏度下的重構性能Fig. 3 Reconstruction performance of algorithms with different sparsity when sensing matrix is OGRM

表3　不同抽樣率下各算法的重構性能對比Table 3 Performance comparison of the algorithms with different sampling rate

圖4　相同抽樣率r=0.5時各算法的重構圖像Fig. 4 Reconstructed image of algorithms with the same sampling rate (r=0.5)

4　結論

1) 提出了一種稀疏度自適應且重構性能較好的StOMP算法，該算法首先估計出每次迭代時支撐集所要擴充的最大原子數，在一定程度上保證了算法的重構效率；然后對較大的閾值參數通過一個與抽樣率成正相關的因子進行修正，同時對設定閾值所選取的原子進行優化處理，保證了用于更新支撐集的均為最佳匹配的候選原子；最后根據當前步長來選取一定數目的原子更新支撐集，在逐步調整步長的同時實現稀疏度的逼近和信號的精確重構。

2) 該算法大大提高了信號稀疏度較大時的正確重構率，具有較好的稀疏度自適應性，并能很好地兼顧圖像重構的效率和精度，在圖像處理領域具有很好的實際應用價值。

[1] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289?1306.

[2] CANDèS E J, WAKIN M B. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 21?30.

[3] TROPP J A, GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655?4666.

[4] NEEDELL D, VERSHYNIN R. Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pursuit[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 310?316.

[5] NEEDELL D, TROPP J A. CoSaMP: iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2009, 26(3): 301?321.

[6] DONOHO D L, TSAIG Y, DRORI I, et al. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2012, 58(2): 1094?1121.

[7] DO T T, GAN L, NGUYEN N, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]// Proceedings of the Asilomar Conference on Signals, Systems and Computers. Pacific Grove, CA: IEEE Computer Society, 2008: 581?587.

[8] 楊海蓉, 張成, 丁大為, 等. 壓縮傳感理論與重構算[J]. 電子學報, 2011, 39(1): 142?148.YANG Hairong, ZHANG Cheng, DING Dawei, et al. Theory of compressed sensing and reconstruction algorithm[J]. Acta Electronica Sinica, 2011, 39(1): 142?148.

[9] BARANIUK R. Compressive sensing[J]. IEEE Signal Processing Magazine, 2007, 24(4): 118?121.

[10] 蘇雅茹. 高維數據的維數約簡算法研究[D]. 合肥: 中國科學技術大學自動化學院, 2012: 36?39. SU Yaru. Research on dimensionality reduction of high-dimensional data[D]. Hefei: University of Science and Technology of China. College of Automation, 2012: 36?39.

[11] 方紅, 楊海蓉. 貪婪算法與壓縮感知理論[J]. 自動化學報, 2011, 37(12): 1413?1421. FANG Hong, YANG Hairong. Greedy algorithm and compressed sensing theory[J]. Journal of Automation, 2011, 37(12): 1413?1421.

[12] 王良君, 石光明, 李甫, 等. 混合觀測壓縮感知圖像多描述編碼[J]. 光學精密工程, 2013, 21(3): 724?733. WANG Liangjun, SHI Guangming, LI Fu, et al. Compressive sensing multiple description image coding with hybrid sampling[J]. Optics and Precision Engineering, 2013, 21(3): 724?733.

[13] CORMODE G, MUTHUKRISHNAN S. Combinatorial algorithms for compressed sensing[C]// Proceedings of the 40th International Conference on Information Science and Systems. Princeton, NJ: IEEE, 2006: 280?294.

[14] 潘榕, 劉昱, 侯正信, 等. 基于局部DCT系數的圖像壓縮感知編碼與重構[J]. 自動化學報, 2011, 37(6): 674?681. PAN Rong, LIU Yu, HOU Zhengxin, et al. Image coding and reconstruction via compressed sensing based on partial DCT coefficients[J]. Journal of Automation, 2011, 37(6): 674?681.

[15] BLUMENSATH T, DAVIES M. Iterative hard threshold for compressed sensing[J]. Applied and Computational Harmonic Analysis, 2009, 27(3): 265?274.

[16] BECK A, TEBOULLE M. A fast iterative shrinkagethresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1): 183?202.

[17] 高睿, 趙瑞珍, 胡紹海. 基于壓縮感知的變步長自適應匹配追蹤重建算法[J]. 光學學報, 2010, 30(6): 1639?1644. GAO Rui, ZHAO Ruizhen, HU Shaohai. Variable step size adaptive matching pursuit algorithm for image reconstruction based on compressive sensing[J]. Acta Optical Sinica, 2010, 30(6): 1639?1644.

[18] 楊成, 馮巍, 馮輝, 等. 一種壓縮采樣中的稀疏度自適應子空間追蹤算法[J]. 電子學報, 2010, 38(4): 1914?1917. YANG Cheng, FENG Wei, FENG Hui, et al. A sparsity subspace pursuit algorithm for compressive sampling[J]. Acta Electronoca Sinica, 2010, 38(4): 1914?1917.

(編輯 趙俊)

A sparsity adaptive stagewise orthogonal matching pursuit algorithm

TANG Chaowei, WANG Xuefeng, DU Yongguang
(College of Communication Engineering, Chongqing University, Chongqing 400044, China)

An improved stagewise orthogonal matching pursuit (StOMP) algorithm was proposed considering that the algorithm needs signal sparsity as the prior knowledge and has a relatively poorer reconstruction performance. Firstly, discreet cosine transform was applied to the vector of residual correlations to estimate the maximum number of atom needed by the support set. Then the large threshold parameter was adjusted by a factor which is positively correlated with the sampling rate and the atoms chosen by setting a threshold value was optimized. Finally, the close approach of signal sparsity and precise reconstruction of the signal were realized with variable step size within the frame of StOMP. The results show that the proposed algorithm has good adaptability without prior information of the sparsity and this algorithm not only keeps the low reconstruction complexity but also shows better and more stable reconstruction quality than the original StOMP algorithm.

compressive sensing; stagewise orthogonal matching pursuit; sparsity adaptive; reconstruction performance

TN911.7

A

1672?7207(2016)03?0784?09

10.11817/j.issn.1672-7207.2016.03.011

2015?03?28；

2015?05?06

國家科技重大專項項目(2010ZX03004-002-01) (Project(2010ZX03004-002-01) supported by the National Science and Technology Major Program of China)

唐朝偉，博士(后)，教授，從事寬帶無線移動多媒體、智能信息處理等方面的研究；E-mail: cwtang@cqu.edu.cn