一種變步長稀疏度自適應(yīng)子空間追蹤算法

田金鵬　劉小娟　鄭國莘

一種變步長稀疏度自適應(yīng)子空間追蹤算法

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

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

壓縮感知，信號(hào)重建，子空間追蹤，自適應(yīng)算法，稀疏表示

引用格式田金鵬，劉小娟，鄭國莘.一種變步長稀疏度自適應(yīng)子空間追蹤算法.自動(dòng)化學(xué)報(bào)，2016，42（10）:1512-1519

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

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

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

這些算法均可以實(shí)現(xiàn)在未知稀疏度時(shí)的信號(hào)重建，但是算法在迭代確定支撐集原子個(gè)數(shù)時(shí)，一般采用固定步長方式逐步增加原子個(gè)數(shù).當(dāng)步長較小時(shí)，迭代次數(shù)就多，算法運(yùn)算量大；步長較大時(shí)，可降低運(yùn)算量，但對稀疏度的估計(jì)誤差就會(huì)加大.算法在迭代時(shí)，對支撐集原子個(gè)數(shù)是單調(diào)遞增的，因此很容易產(chǎn)生過度估計(jì)問題，導(dǎo)致重建誤差變大.

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

1　壓縮感知基本理論框架

這里要求Φ與Ψ是不相關(guān)的，結(jié)合式（1）有

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

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

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

2　變步長稀疏度自適應(yīng)子空間追蹤算法

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

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

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

2.1算法描述

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

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

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

2）確定K的范圍.以K0作為固定步長，分步增加信號(hào)支撐集的個(gè)數(shù)L=nK0，并以SP算法迭代計(jì)算出相應(yīng)信號(hào)支撐集及殘差，當(dāng)L＜K時(shí)，增加的支撐集含有效原子，所以殘差會(huì)迅速減小；而當(dāng)L≥K后，新增加的支撐集一般不含有效原子，殘差基本不變甚至變大.所以根據(jù)殘差在L=nK0各階段的變化，可以粗略確定K的范圍（在一個(gè)固定步長K0區(qū)間內(nèi)）.

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

2.2算法步驟

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

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

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

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

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

步驟2.確定K的范圍.

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

步驟3.2.同步驟2.2～2.7，利用SP算法計(jì)算出在支撐集為L最優(yōu)估計(jì)時(shí)的殘差

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

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

2.3算法分析

對于稀疏度為K的原始信號(hào)，進(jìn)行壓縮采樣，信號(hào)重建時(shí)，若選擇的支撐集原子個(gè)數(shù)L＜K，設(shè)α的K個(gè)稀疏系數(shù)中較大的L個(gè)對應(yīng)的索引集為ΓL，其余較小的K-L個(gè)稀疏系數(shù)對應(yīng)的索引集為ΓR，則各種重建算法的最優(yōu)結(jié)果是選擇集合 ΓL對應(yīng)的Θ的各列向量作為支撐集，且殘差的能量最小為

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

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

類似分析可知，當(dāng)支撐集原子個(gè)數(shù)L≥K時(shí)，則成功重建時(shí)K個(gè)稀疏系數(shù)都會(huì)被選中，那么殘差能量為

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

圖1　支撐集原子個(gè)數(shù)與殘差對應(yīng)關(guān)系示意圖Fig.1　The relationship of residual error and the number of support set atom

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

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

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

3　仿真實(shí)驗(yàn)結(jié)果及分析

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

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

3.1稀疏度估計(jì)實(shí)驗(yàn)

為驗(yàn)證本文算法對稀疏度K估計(jì)的準(zhǔn)確度，通過仿真實(shí)驗(yàn)加以測試.實(shí)驗(yàn)中，取N=256，M=128，觀測矩陣為M×N階獨(dú)立分布、零均值、單位方差的高斯隨機(jī)矩陣，原始信號(hào)為直接構(gòu)造的K稀疏信號(hào)（從中隨機(jī)取K個(gè)元素，每一項(xiàng)值為獨(dú)立分布、零均值、單位方差高斯隨機(jī)變量，其他元素值為零），所以稀疏基Ψ為單位陣，通過得到觀測向量.實(shí)驗(yàn)中對原始信號(hào)疊加了不同強(qiáng)度的高斯白噪聲.

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

3.2信號(hào)重建性能實(shí)驗(yàn)

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

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

首先對信號(hào)的準(zhǔn)確重建概率進(jìn)行比較，這里信號(hào)準(zhǔn)確重建定義為在無噪聲的理想情況下，實(shí)際信號(hào)與恢復(fù)信號(hào)中非零元素的位置相同，且誤差的能量小于某一個(gè)閾值，這里閾值取10-6.

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

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

圖3　不同算法信號(hào)準(zhǔn)確重建率Fig.3　Exact recovery ratio of recovery algorithms by different reconstruction algorithms

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

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

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

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

圖5　算法運(yùn)行時(shí)間對比（M=1024，N=2048）Fig.5　Running time by different reconstruction algorithms（M=1024，N=2048）

3.3圖像重建實(shí)驗(yàn)

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

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

表1給出了不同算法在不同壓縮比條件下重建圖像的PSNR和運(yùn)算時(shí)間對比，每個(gè)數(shù)據(jù)均為50次實(shí)驗(yàn)的平均結(jié)果.

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

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

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

表1　各算法的重建質(zhì)量及運(yùn)行時(shí)間對比Table 1　Comparison of the qualities of images reconstructed and running time by different algorithms

4　結(jié)論

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

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（荊楠，畢衛(wèi)紅，胡正平，王林.動(dòng)態(tài)壓縮感知綜述.自動(dòng)化學(xué)報(bào)，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（沈燕飛，李錦濤，朱珍民，張勇東，代鋒.基于非局部相似模型的壓縮感知圖像恢復(fù)算法.自動(dòng)化學(xué)報(bào)，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（伍飛云，周躍海，童峰.基于似零范數(shù)和混合優(yōu)化的壓縮感知信號(hào)快速重構(gòu)算法.自動(dòng)化學(xué)報(bào)，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（徐澤芳，劉順蘭.一種自適應(yīng)正則化子空間追蹤算法.計(jì)算機(jī)工程與應(yīng)用，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（張成，沈川，程鴻，章權(quán)兵，陳嵐，韋穗.彩色全息壓縮重構(gòu).自動(dòng)化學(xué)報(bào)，2015，41（2）:419-428）

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

田金鵬博士，上海大學(xué)通信與信息工程學(xué)院講師.主要研究方向?yàn)樾盘?hào)處理，模式識(shí)別.本文通信作者.

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.）

劉小娟上海大學(xué)通信與信息工程學(xué)院碩士研究生.主要研究方向?yàn)閳D像處理，壓縮感知.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.）

鄭國莘上海大學(xué)通信與信息工程學(xué)院教授.主要研究方向?yàn)樾盘?hào)處理，限定空間無線電通信.

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

國家自然科學(xué)基金（61132003，61571282），上海大學(xué)創(chuàng)新基金（sdcx2 012041）資助

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

本文責(zé)任編委劉成林

Recommended by Associate Editor LIU Cheng-Lin

1.上海大學(xué)通信與信息工程學(xué)院上海2004442.上海大學(xué)特種光纖與光接入網(wǎng)重點(diǎn)實(shí)驗(yàn)室上海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