一種變步長稀疏度自適應子空間追蹤算法

田金鵬　劉小娟　鄭國莘

一種變步長稀疏度自適應子空間追蹤算法

田金鵬1，2劉小娟1鄭國莘1，2

針對壓縮感知（Compressive sensing，CS）中未知稀疏度信號的重建問題，本文提出一種變步長稀疏度自適應子空間追蹤算法.首先，采用一種匹配測試的方法確定固定步長，然后以該固定步長與變步長方式相結合，通過不同支撐集原子個數下的重建殘差變化確定信號稀疏度，算法采用子空間追蹤方法確定相應支撐集原子，并完成原始信號準確重建.實驗結果表明，與同類算法相比，該算法可以更準確重建原始信號，且信號稀疏度值較高時，運算量低于同類算法.

壓縮感知，信號重建，子空間追蹤，自適應算法，稀疏表示

引用格式田金鵬，劉小娟，鄭國莘.一種變步長稀疏度自適應子空間追蹤算法.自動化學報，2016，42（10）:1512-1519

壓縮感知（Compressive sensing，CS）是Donoho、及Tao等提出的一種新的信息獲取理論［1-4］.對于具有稀疏性或者在特定域上具有稀疏性的原始信號，根據壓縮感知理論，我們能夠采用遠低于Nyquist采樣的速率來對該信號同時進行采樣和壓縮，得到低維觀測信號，并可通過觀測信號準確完成高維原始信號的重建，從而大大降低了原始信號獲取、存儲及傳輸的代價，緩解了高速采樣對硬件系統造成的壓力.

CS理論的一個重要方面是信號重建算法，常用的重建方法主要有貪婪追蹤算法、凸優化算法和組合算法三大類.其中貪婪追蹤算法由于結構簡單、計算復雜度較低而備受關注.傳統的貪婪算法有匹配追蹤（Matching pursuit，MP）［5］以及正交匹配追蹤（Orthogonal matching pursuit，OMP）［6］算法等，這些算法在每一次迭代時對支撐集都只選擇增加一個原子，所以其運算復雜度較大；而后提出的正則化正交匹配追蹤（Regularized orthogonal matching pursuit，ROMP）算法［7］及分段正交匹配追蹤（Stagewise orthogonal matching pursuit，StOMP）算法［8］對此進行了改進，在每次迭代時可一次選擇增加多個支撐集原子，所以提高了重建速度；后來提出的壓縮采樣匹配追蹤（Compressive sampling matching pursuit，CoSaMP）算法［9］和子空間追蹤（Subspace pursuit，SP）算法［10］在每次迭代時均一次選擇多個原子，同時采用回溯檢驗方法，先求得一個原子個數較多的候選支撐集合，再每次迭代中從該集合中增加與殘差相關度高的原子、淘汰權值系數小的原子，直到算法收斂，該方法可提高重建精度.

上述算法實現信號重建的必要條件是必須獲知原始信號稀疏度.但是在現實環境中，這個條件難以滿足，因為大多數實際信號在其稀疏域僅是近似稀疏的，例如圖像信號，不同的圖像其稀疏度各不相同，所以這些算法往往難以處理實際問題.為解決該問題，文獻［11］提出了稀疏度自適應匹配追蹤（Sparsity adaptive matching pursuit，SAMP）算法，該算法采用StOMP算法中的分段的思想來逐段擴充真實支撐集，同時也利用了SP/CoSaMP算法中的回溯的思想，算法不需要知道稀疏度的先驗信息.還有其他一些算法［12-15］也可以實現稀疏度自適應信號重建.

這些算法均可以實現在未知稀疏度時的信號重建，但是算法在迭代確定支撐集原子個數時，一般采用固定步長方式逐步增加原子個數.當步長較小時，迭代次數就多，算法運算量大；步長較大時，可降低運算量，但對稀疏度的估計誤差就會加大.算法在迭代時，對支撐集原子個數是單調遞增的，因此很容易產生過度估計問題，導致重建誤差變大.

為解決上述問題，本文根據重建殘差與支撐集原子個數及信號稀疏度之間的關系，針對由于SAMP算法采用固定增加步長所帶來的精度較低和可能由此產生的過度估計問題［12］，提出了一種新的變步長稀疏度自適應子空間追蹤算法（Variable step size sparsity adaptive subspace pursuit，Vss-SASP）算法.該算法不需要知道信號稀疏度信息，先采用固定步長確定信號稀疏度的范圍，再用可變步長逐步縮小該范圍并確定稀疏度，對支撐集原子選擇采用子空間追蹤算法的回溯方法，仿真實驗結果表明該算法信號重建運算量較小，重建精度高.

1　壓縮感知基本理論框架

這里要求Φ與Ψ是不相關的，結合式（1）有

其中，Θ=ΦΨ為M×N維矩陣，定義為傳感矩陣，針對具體應用，Φ與Ψ均為確定的，所以傳感矩陣Θ是固定的.壓縮感知中常用的觀測矩陣有伯努利矩陣、高斯隨機矩陣等.

由于l0范數下求解只能通過對所有可能的稀疏情況進行求解，所以式（4）的求解是個NP-hard問題.為解決該問題，研究人員根據信號稀疏分解的相關理論，尋找到了更有效的求解途徑.文獻［4］表明，在一定條件下，l1最小范數與l0最小范數具有等價性，那么式（4）可轉化為

l1最小范數可用凸優化算法求解式（5）中的α，如內點法、BP算法等，這類算法重構精度較高，復雜度也高，不適合處理維數較高數據.相對而言，基于l0最小范數的貪婪追蹤算法計算復雜度低，算法結構簡單，但重建精度稍低，研究快速有效的貪婪追蹤算法，是本文要研究的主要內容.

2　變步長稀疏度自適應子空間追蹤算法

CS的信號重建可以看成信號稀疏分解問題，如果把Θ的各列向量 θi（1≤i≤N）看作原子并將其作歸一化處理，那么這些列向量就組成超完備字典D.根據設定，在 α中只有K個非零元素，那么觀測值就能用D中K個原子線性組合來表示.我們把這K個原子的索引組成集合 Γ，可以表示成ΘΓαΓ，其中ΘΓ、 αΓ分別表示根據 Γ索引在對應Θi、 α中的子集.

y在字典D上具有稀疏的表示，我們的目標就是尋找最少的一組原子使得殘差r=y-ΘΓαΓ信號能量最小.

已有的SAMP算法及其他改進算法可以在未知信號的稀疏度K的情況下，采用逐步擴充支撐集數量并回溯驗證的方法來選擇支撐集，逐步逼近原始信號.但這些算法在每次迭代中采用增加固定數目（步長）原子的方法估計信號稀疏度，存在計算量過大及過度估計的問題.

2.1算法描述

本文提出的VssSASP算法在K未知的條件下，首先通過一種測試方法確定固定步長值，再將固定步長與可變步長相結合，通過殘差變化精確估計K值，在每個階段的迭代均采用SP算法迭代選擇支撐集原子.算法分為以下三個階段：

1）確定固定迭代步長.在文獻［16］中給出了一種稀疏度估計方法，通過測試找到滿足

的最大K0值.其中，δk為傳感矩陣Θ的K階有限等距常數（Restricted isometry constant，RIC），Γ0為中前K0個最大值的索引.K0為接近且小于信號稀疏度值K，我們可以把它作為固定迭代步長.

2）確定K的范圍.以K0作為固定步長，分步增加信號支撐集的個數L=nK0，并以SP算法迭代計算出相應信號支撐集及殘差，當L＜K時，增加的支撐集含有效原子，所以殘差會迅速減小；而當L≥K后，新增加的支撐集一般不含有效原子，殘差基本不變甚至變大.所以根據殘差在L=nK0各階段的變化，可以粗略確定K的范圍（在一個固定步長K0區間內）.

3）K值逐步逼近.采用二分法，取信號支撐集個數為上個階段確定K的范圍中間值，再利用SP算法求出當前支撐個數下的殘差值，將該殘差值與K 的范圍兩端對應的殘差值對比，根據若殘差基本不變，則對應范圍的信號支撐集個數大于K的原則，逐步縮小對K值的估計，直到最終確定K值，并求出對應支撐集及其系數，進而實現原信號的重建.

2.2算法步驟

VssSASP算法具體步驟如下.流程中，rrrt表示殘差，t表示迭代次數，?表示空集，Γt表示t次迭代的索引（列序號）集合（元素個數為L），θj表示矩陣Θ的第j列，表示按索引集合選出的矩陣Θ的列集合（列數為Lt），αt為 Lt×1的列向量，符號∪表示集合并運算，〈·，·〉表示求向量內積，abs［·］表示求模值（絕對值）.

輸入.M維測量向量y，M×N維傳感矩陣Θ，判定閾值ε.

步驟1.確定固定迭代步長.

步驟1.1.初始化:K0=1，計算（即計算

步驟1.4.得到稀疏度估計K0=K0-1，固定迭代步長step0=K0.

步驟2.確定K的范圍.

步驟3.變步長逐步逼近.

步驟3.2.同步驟2.2～2.7，利用SP算法計算出在支撐集為L最優估計時的殘差

步驟3.4.重復步驟3.2～3.3，不斷縮小K值范圍［Kl，Ku］，直到最終確定K值和相應的支撐集及其系數以及殘差.

算法中閾值ε用于增大支撐集個數時，根據殘差判斷恢復精度是否提高.沒有環境噪聲，當信號為理想K稀疏（α僅有K個非零系數）時，ε可取任意小于α中最小系數的值；當信號為近似稀疏（α的系數按大小滿足指數衰減）時，ε取期望的重建精度，ε越小，重建所需的支撐集越多，重建精度越高.如果存在環境噪聲，則閾值ε與信號噪聲水平、能量等有密切關系，根據大量實驗結果，ε取取0.12時重建效果較好.

2.3算法分析

對于稀疏度為K的原始信號，進行壓縮采樣，信號重建時，若選擇的支撐集原子個數L＜K，設α的K個稀疏系數中較大的L個對應的索引集為ΓL，其余較小的K-L個稀疏系數對應的索引集為ΓR，則各種重建算法的最優結果是選擇集合 ΓL對應的Θ的各列向量作為支撐集，且殘差的能量最小為

由于Θ的各列向量作為支撐集滿足RIP條件，則

一般δk? 1，殘差的能量主要取決于而由K-L個較小的稀疏系數組成，所以隨著L的增加，重建殘差迅速減小.

類似分析可知，當支撐集原子個數L≥K時，則成功重建時K個稀疏系數都會被選中，那么殘差能量為

其中，Γ0為α 中除了K個稀疏系數外，其他為零或接近于零系數的索引集，共有N-L個元素.很明顯這時隨著L增加，重建殘差將保持為一個很小的值，且基本穩定在較小范圍內.不同支撐集原子個數L與重建殘差大小的變化趨勢如圖1所示，此即為本文算法用來估計信號稀疏度的基本依據.

圖1　支撐集原子個數與殘差對應關系示意圖Fig.1　The relationship of residual error and the number of support set atom

在本文算法的步驟2，確定殘差變化拐點的大致位置，在步驟3用二分法確定拐點準確位置，該位置即對應稀疏度的估計.我們計算得到殘差接近最小的情況下L的最小值，計算過程中，可知能量單調遞減，算法至少收斂到一個局部最小點.

在SAMP及其他稀疏度自適應算法中，通過遞增方式估計K值，步長和運算量與K的準確估計存在矛盾，特別是有噪聲存在時，K值估計誤差大，恢復精度不高.而VssSASP算法通過恢復殘差的變化估計稀疏度K值大小范圍，可以得到比較準確的K值估計，具有較高的恢復精度.

關于運算量方面，在確定固定迭代步長階段主要運算為一次內積運算及小于K次范數運算，計算量較??；確定K的范圍階段主要運算為K/K0+1次SP運算（K0略小于K），變步長階段逐步逼近采用二分法，主要運算為log2K0次SP運算，后兩個階段計算量較大，總的運算復雜度上限為O（MNK log2K）.除了第1次，后面每次SP運算可以利用上次的SP運算結果，所以單次SP運算迭代次數均很少；與SAMP算法相比，當K很大時，VssSASP算法的運算復雜度小于SAMP算法運算復雜度O（MNK2）.

3　仿真實驗結果及分析

為驗證本文提出的VssSASP算法對各種原始信號的重建效果及性能，對算法進行了一系列仿真驗證實驗，將典型貪婪追蹤算法OMP、ROMP、SP以及SAMP算法與本文算法進行了性能仿真比較.其中SAMP算法由于不同步長相應的算法性能不同，所以這里取步長值s為1，5和10三個值分別進行測試.

這些實驗均是在惠普g14筆記本（4GB DDR3內存，i5-4200U）上運行，采用的仿真軟件版本為Matlab R2009a，若非特殊說明，對于不同的數據點均為運行500次的平均值.

3.1稀疏度估計實驗

為驗證本文算法對稀疏度K估計的準確度，通過仿真實驗加以測試.實驗中，取N=256，M=128，觀測矩陣為M×N階獨立分布、零均值、單位方差的高斯隨機矩陣，原始信號為直接構造的K稀疏信號（從中隨機取K個元素，每一項值為獨立分布、零均值、單位方差高斯隨機變量，其他元素值為零），所以稀疏基Ψ為單位陣，通過得到觀測向量.實驗中對原始信號疊加了不同強度的高斯白噪聲.

圖2為不同噪聲環境下對稀疏度K值的估計誤差，圖中橫坐標表示原始信號的實際稀疏度K，縱坐標表示K的估計誤差.在信噪比較小時，由于加入的噪聲信號較大，算法會將能量較大的部分噪聲當成實際信號，所以估計誤差較大；而隨著信噪比增加，噪聲減小，估計誤差也逐漸變小，當沒有噪聲時，本文算法可以準確估計信號的實際稀疏度K.

3.2信號重建性能實驗

將本文的VssSASP算法與OMP、ROMP、SP、SAMP其他典型貪婪追蹤算法進行了性能仿真比較，檢驗各算法在準確重建概率、重建精度及重建運行時間方面的對比.實驗仿真中基本設置與前面相同，并根據仿真需要改變其中部分參數.

圖2　不同信噪比下稀疏度K估計誤差Fig.2　Estimating error of signal sparsity under different noise level

首先對信號的準確重建概率進行比較，這里信號準確重建定義為在無噪聲的理想情況下，實際信號與恢復信號中非零元素的位置相同，且誤差的能量小于某一個閾值，這里閾值取10-6.

圖3（a）中給出了K=20時，不同采樣點M的信號準確重建率.從圖3（a）可以看出，對于所有重建算法，原始信號的準確重建概率均隨著采樣點數M的增加而增大；對于本文算法，當M＞80時，VssSASP算法重建概率接近于1；當M ＞60時，VssSASP算法重建概率明顯超過OMP、ROMP和SP算法，與SAMP算法重建概率相當.相對而言，對于同樣的信號，VssSASP算法能穩定重建信號所需的采樣點數較少.

圖3（b）中給出了M=128時，各重建算法對不同稀疏度K 信號的準確重建率.同樣可以看出，信號準確重建概率隨著信號稀疏度K的增大而減小，當K＜45時，VssSASP算法重建概率接近于1；當K＞45時，重建概率開始明顯下降，但重建概率明顯高于OMP、ROMP和SP算法，與SAMP算法重建概率相當.相對而言，對于同樣的采樣點數，VssSASP算法能穩定重建稀疏度更高的信號.

圖3　不同算法信號準確重建率Fig.3　Exact recovery ratio of recovery algorithms by different reconstruction algorithms

值得注意的是，在采樣點較少或稀疏度較大時，VssSASP算法重建概率要低于SAMP算法.這兩種算法都是以SP算法為基礎，SAMP算法以線性增加稀疏度K估計的方式進行搜索，盡管此時單次SP算法重建成功概率較低，但在搜索過程中只要有一次重建成功，即認為SAMP算法重建完成，所以這時SAMP算法重建成功率遠高于SP算法，且步長s越小成功率越高，但實際上此時算法估計稀疏度一般要明顯高于原信號實際稀疏度K.VssSASP算法采用殘差判定稀疏度K的區間，然后再進行二分法搜索，搜索次數較少，且此時殘差變化的不規律也可能導致區間定位錯誤，所以算法重建成功率提高有限，低于SAMP算法.

綜上所述，VssSASP算法在無噪聲環境下重建概率超過OMP、ROMP和SP算法，而與SAMP算法性能相近，信號重建概率較高.

圖4　噪聲環境下的重建精度（M=80，N=256，K=20）Fig.4　Reconstruction accuracy in noise environment（M=80，N=256，K=20）

圖5是各種算法運行時間的對比，為體現對高K值信號的重建性能，這里N和M 值均取較大值.從圖5可以看出，各算法的運算時間均隨著K的增大而增加.總體而言，由于ROMP和SP算法已知稀疏度K，每次迭代時可選擇支撐集原子個數多，迭代次數少，運算時間最少；OMP算法每次迭代只增加支撐集中的一個原子，運算時間較多；對于SAMP和本文的稀疏度自適應算法，在K較小時，VssSASP算法的運行時間與SAMP算法相差不大，但隨著K的增加，SAMP算法運算時間迅速增加（步長越小，增加越多），而VssSASP算法變步長優勢逐漸體現，運算速度很快超過SAMP算法.

圖5　算法運行時間對比（M=1024，N=2048）Fig.5　Running time by different reconstruction algorithms（M=1024，N=2048）

3.3圖像重建實驗

在實驗中采用的是大小為256像素×256像素的Lena灰度圖像，因為圖像各列（行）的稀疏性較差，為提高重建效果，這里先將其用雙正交小波（bior3.7）進行變換，然后將變換后矩陣的各行作為一維列信號進行壓縮采樣，再用不同算法進行重建，重建完成后再通過同樣的小波反變換得到重建圖像.其中觀測矩陣Φ采用正交觀測矩陣，稀疏基Ψ仍為單位陣.

定義圖像的采樣率為M/N，重建圖像的質量用峰值信噪比（Peak signal to noise ratio，PSNR）來表示.圖6給出了在采樣率為0.5的條件下，Lena圖像的原圖像及OMP，ROMP，SP，SAMP，Vss-SASP算法重建圖像和PSNR值.從圖6可以看出，VssSASP算法的重建質量略優于ROMP算法，優于OMP、SP及各種步長的SAMP算法，經Vss-SASP算法重建后的圖像與原始圖像比較接近，且細節保持較好，具有良好的視覺效果.

表1給出了不同算法在不同壓縮比條件下重建圖像的PSNR和運算時間對比，每個數據均為50次實驗的平均結果.

從表1可以看出，隨著采樣率的增大，各種重建算法重建圖像的PSNR均顯著增大，通過增加觀測數目可以提高重建圖像的重建質量；在相同壓縮比的條件下，VssSASP算法重建圖像的PSNR值均為最大，說明該算法對圖像重建精度較高.

另外，根據表1中時間數據可以看出，隨著采樣率的增大，各種重建算法運算時間均增大，且稀疏度自適應算法SAMP和VssSASP運算時間明顯高于其他非稀疏度自適應算法.其中ROMP算法在每次迭代時會選取多個原子，其運算時間少于OMP算法；SAMP算法要進行多次類SP運算，其運行時間高于SP算法，且步長s越小，運算時間越長；VssVSASP算法也是進行多次類SP運算，由于我們進行實驗時，分別對每一行進行壓縮重建，N值較小，算法變步長優勢不明顯，算法運算時間低于步長為1的SAMP算法，而高于步長為10的SAMP算法.

圖6　樣率0.5時，Lena原圖像及各算法重建圖像Fig.6　Original image and reconstructed image of different algorithms for Lena when sampling rate is 0.5

表1　各算法的重建質量及運行時間對比Table 1　Comparison of the qualities of images reconstructed and running time by different algorithms

4　結論

本文提出了一種變步長稀疏度自適應子空間追蹤算法VssSASP，可在未知原始信號稀疏度的先驗信息的情況下準確重建信號.算法采用固定步長與可變步長相結合的方式，采用子空間追蹤通過迭代估計的更新，根據各階段殘差變化確定信號稀疏度，可精確重建原信號.實驗結果表明，VssSASP算法可以高概率重建稀疏信號，在噪聲環境下具有高重建精度，當信號稀疏度較大時，算法的運算速度也高于SAMP稀疏度自適應算法.

References

1 Donoho D L.Compressed sensing.IEEE Transactions on Information Theory，2006，52（4）:1289-1306

4 Jing Nan，Bi Wei-Hong，Hu Zheng-Ping，Wang Lin.A survey on dynamic compressed sensing.Acta Automatica Sinica，2015，41（1）:22-37（荊楠，畢衛紅，胡正平，王林.動態壓縮感知綜述.自動化學報，2015，41（1）:22-37）

5 Mallat S G，Zhang Z F.Matching pursuits with timefrequency dictionaries.IEEE Transactions on Signal Processing，1993，41（12）:3397-3415

6 Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit.IEEE Transactions on Information Theory，2007，53（12）:4655-4666

7 Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Foundations of Computational Mathematics，2009，9（3）: 317-334

8 Donoho D L，Tsaig Y，Drori I，Starck J L.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit.IEEE Transactions on Information Theory，2012，58（2）:1094-1121

9 Needell D，Tropp J A.CoSaMP:iterative signal recovery from incomplete and inaccurate samples.Communications of the ACM，2010，53（12）:93-100

10 Dai W，Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction.IEEE Transactions on Information Theory，2009，55（5）:2230-2249

11 Do T T，Gan L，Nguyen N，Tran T D.Sparsity adaptive matching pursuit algorithm for practical compressed sensing.In:Proceedings of the 42nd Asilomar Conference on Signals，Systems，and Computers.Pacific Grove，California: IEEE Press，2008.581-587

12 Shen Yan-Fei，Li Jin-Tao，Zhu Zhen-Min，Zhang Yong-Dong，Dai Feng.Image reconstruction algorithm of compressed sensing based on nonlocal similarity model.Acta Automatica Sinica，2015，41（2）:261-272（沈燕飛，李錦濤，朱珍民，張勇東，代鋒.基于非局部相似模型的壓縮感知圖像恢復算法.自動化學報，2015，41（2）:261-272）

13 Wu Fei-Yun，Zhou Yue-Hai，Tong Feng.A fast sparse signal recovery algorithm based on approximate l0norm and hybrid optimization.Acta Automatica Sinica，2014，40（10）: 2145-2150（伍飛云，周躍海，童峰.基于似零范數和混合優化的壓縮感知信號快速重構算法.自動化學報，2014，40（10）:2145-2150）

14 Xu Ze-Fang，Liu Shun-Lan.Adaptive regularized subspace pursuit algorithm.Computer Engineering and Applications，2015，51（3）:208-211（徐澤芳，劉順蘭.一種自適應正則化子空間追蹤算法.計算機工程與應用，2015，51（3）:208-211）

15 Zhang Cheng，Shen Chuan，Cheng Hong，Zhang Quan-Bing，Chen Lan，Wei Sui.Compressed reconstruction of color holography.Acta Automatica Sinica，2015，41（2）:419-428（張成，沈川，程鴻，章權兵，陳嵐，韋穗.彩色全息壓縮重構.自動化學報，2015，41（2）:419-428）

16 Yang Cheng，Feng Wei，Feng Hui，Yang Tao，Hu Bo.A sparsity adaptive subspace pursuit algorithm for compressive sampling.Acta Electronica Sinica，2010，38（8）:1914-1917（楊成，馮巍，馮輝，楊濤，胡波.一種壓縮采樣中的稀疏度自適應子空間追蹤算法.電子學報，2010，38（8）:1914-1917）

田金鵬博士，上海大學通信與信息工程學院講師.主要研究方向為信號處理，模式識別.本文通信作者.

E-mail:adaline@163.com

（TIAN Jin-PengPh.D.，lecturer at the School of Communication and Information Engineering，Shanghai University.His research interest covers signal processing and pattern recognition.Corresponding author of this paper.）

劉小娟上海大學通信與信息工程學院碩士研究生.主要研究方向為圖像處理，壓縮感知.E-mail:xjliumail@163.com

（LIU Xiao-JuanMaster student at the School of Communication and Information Engineering，Shanghai University.Her research interest covers image processing and compressed sensing.）

鄭國莘上海大學通信與信息工程學院教授.主要研究方向為信號處理，限定空間無線電通信.

E-mail:gxzheng@staff.shu.edu.cn

（ZHENGGuo-XinProfessor at the School of Communication and Information Engineering，Shanghai University.His research interest covers signal processing and confined space radio communications.）

A Variable Step Size Sparsity Adaptive Subspace Pursuit Algorithm

TIAN Jin-Peng1，2LIU Xiao-Juan1ZHENG Guo-Xin1，2

A novel variable step size sparsity adaptive subspace pursuit algorithm is proposed to rebuild the sparse signals with unknown sparsity in compressive sensing.Firstly，the initial fixed step size is obtained by matching test，which is combined with the variable step size method.Then，the sparsity is accurately estimated according to the change of signal rebuilding residual error under vary support set.Subspace pursuit algorithm is used to determine the support set and exactly rebuild the sparse signal.Simulation results show that the proposed algorithm is competitive in recovering accuracy and running speed，compared to other similar algorithms，when sparsity is large.

Compressed sensing（CS），signal reconstruction，subspace pursuit algorithm，adaptation algorithm，sparse representation

Manuscript November 26，2015；accepted April 18，2016

10.16383/j.aas.2016.c150801

Tian Jin-Peng，Liu Xiao-Juan，Zheng Guo-Xin.A variable step size sparsity adaptive subspace pursuit algorithm.Acta Automatica Sinica，2016，42（10）:1512-1519

2015-11-26錄用日期2016-04-18

國家自然科學基金（61132003，61571282），上海大學創新基金（sdcx2 012041）資助

Supported by National Natural Science Foundation of China（61132003，61571282）and Innovation Foundation of Shanghai University（sdcx2012041）

本文責任編委劉成林

Recommended by Associate Editor LIU Cheng-Lin

1.上海大學通信與信息工程學院上海2004442.上海大學特種光纖與光接入網重點實驗室上海200072

1.School of Communication and Information Engineering，Shanghai University，Shanghai 2004442.Key Laboratory of Specialty Fiber Optics and Optical Access Networks，Shanghai University，Shanghai 200072