一種改進(jìn)的變步長稀疏自適應(yīng)正則匹配追蹤算法

摘要：針對未知稀疏度信號重構(gòu)和欠估計(jì)或過估計(jì)問題，在SAMP算法基礎(chǔ)上提出了一種改進(jìn)的變步長稀疏自適應(yīng)正則化匹配追蹤算法。首先利用原子匹配測試法得到稀疏度的初始估計(jì)，隨后根據(jù)變步長分階段思想和改進(jìn)的拋物線型函數(shù)設(shè)計(jì)步長，利用大步長和小步長相結(jié)合的方式提高重構(gòu)精度，最后根據(jù)測量向量與信號能量比率來設(shè)定閾值，最終重建信號。實(shí)驗(yàn)表明，該算法在解決欠估計(jì)或過估計(jì)問題上起到了很大的作用，未知稀疏信號的重建精度較高且效率較高。

關(guān)鍵詞：貪婪算法；稀疏自適應(yīng)；變步長；正則回溯；SAMP算法

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-5039（2018）16-0251-02

A Modified Variable Step Size Sparsity Adaptive Regularized Matching Pursuit Algorithm

SUN Run-run

（College of Computer Science and Engineering， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： For solving the problem of unknown sparsity signal reconstruction and underestimation or over estimation， a modified variable step size adaptive regularized matching pursuit algorithm is proposed on the basis of sparse adaptive matching pursuit algorithm. Firstly， the algorithm uses the method of atomic matching test to get the initial estimation. Then an improved parabolic function is used to design the step length. Finally，the the ratio of measurement vectors energy and the reconstruction signals energy is used to set the threshold. The experiment shows that the algorithm solves the problem caused by unsuitable selection of fixed step length， and realizes the accurate reconstruction of the unknown sparsity signal.

Key words： greedy algorithm；sparse adaptive； variable step size；regularized backtracking；SAMP algorithm

1 引言

近幾年來，Donoho，Cande和Tao等人提出了一種嶄新的信號采樣處理理論，即壓縮感知理論。該理論研究表明，如果信號是稀疏的或在某一個(gè)稀疏域是稀疏的，那么可以通過低于甚至遠(yuǎn)低于奈奎斯特采樣標(biāo)準(zhǔn)對其實(shí)現(xiàn)采樣壓縮并用的模式，可精確地實(shí)現(xiàn)原始信號重建。既節(jié)約了硬件資源，又節(jié)約了運(yùn)算成本和存儲空間[1]。

重構(gòu)是壓縮感知理論研究的是重要的組成部分，使用低維數(shù)據(jù)以高精度的方法重構(gòu)出高維數(shù)據(jù)是研究人員研究的重點(diǎn)。對于稀疏性或某一稀疏域上稀疏的信號重構(gòu)算法的研究主要集中于組合算法、凸優(yōu)化算法和貪婪迭代算法[2]。組合算法是將非凸問題轉(zhuǎn)化成凸問題，運(yùn)行效率高但計(jì)算復(fù)雜度大，應(yīng)用不廣泛。貪婪追蹤算法在減少采樣頻率的同時(shí)增加運(yùn)行效率，因?yàn)槠溆?jì)算復(fù)雜度低，重構(gòu)效果好且計(jì)算結(jié)構(gòu)簡單，與其他兩種算法相比應(yīng)用廣泛。針對未知稀疏度信號的重構(gòu)，本文在研究上述算法基礎(chǔ)上，提出一種改進(jìn)的變步長稀疏自適應(yīng)正則化匹配追蹤算法。仿真實(shí)驗(yàn)表明，本文算法重構(gòu)精度較高，性能優(yōu)于SAMP算法且應(yīng)用范圍更廣。

2 改進(jìn)的變步長稀疏自適應(yīng)正則化匹配追蹤算法

2.1 算法描述

2.1.1 稀疏度估計(jì)

由于選擇合適的初始稀疏估計(jì)值能減少算法運(yùn)行時(shí)間，提高運(yùn)行精度，本文使用原子匹配測試方式計(jì)算出初始稀疏度估計(jì)值，該稀疏估計(jì)值即為初始固定步長，其中估計(jì)值小于且接近K值，然后得到一個(gè)假定支撐集，其原子個(gè)數(shù)略小于稀疏度K。

文獻(xiàn)[3]和[4]證明了命題“設(shè)如果測量矩陣滿足RIP有限等距性質(zhì)，如果[ΦTF0y2≤1-δk1+δky2]，則K0[≤]K”是真命題。利用該命題可以獲取合適的初始稀疏值K0。具體方法為：設(shè)置K0初始值，如果滿足上述公式，則K0自增直到不等式成立，此時(shí)K0為K的初始估計(jì)。

2.1.2 步長選擇

本文算法突破了傳統(tǒng)的匹配追蹤中需要稀疏度已知的局限，即實(shí)現(xiàn)稀疏度自適應(yīng)，通過在迭代過程中逐漸改變步長，逼近稀疏度K。變步長分階段思想使得在增加重構(gòu)精度的同時(shí)減小運(yùn)算時(shí)間。而當(dāng)支撐集原子個(gè)數(shù)不斷增加的過程中，原始信號的能量差在相鄰階段是先不斷減小在趨于平穩(wěn)，根據(jù)這一規(guī)律來進(jìn)行步長的函數(shù)選擇。步長的大小選擇也是至關(guān)重要的，步長過小可能會導(dǎo)致迭代次數(shù)過大且運(yùn)算時(shí)間增大，引起過估計(jì)問題；步長過大可能會導(dǎo)致重構(gòu)精度不高或欠估計(jì)問題，因此在變步長稀疏自適應(yīng)追蹤算法中固定步長的選擇至關(guān)重要。

對比文獻(xiàn)[5]的對數(shù)型和拋物線型稀疏度自適應(yīng)匹配追蹤算法，比較其中使用的步長設(shè)計(jì)公式，可以看出拋物線函數(shù)在初始階段的變化率大于對數(shù)函數(shù)。大的變化率可以進(jìn)一步加大初始階段的步長，可以更快速地接近稀疏度，所以拋物線步長有效解決了“大步長”階段步長變化小的問題，能夠獲得比對數(shù)型更優(yōu)越。在拋物線型平方根和立方根函數(shù)中，由于后者在步長上升階段變化率大，在步長減小的階段變化率更平緩。所以設(shè)計(jì)步長S如下：[S（x）=ax3+b]，Stage為總階段數(shù)，a和b為參數(shù)。再根據(jù)x為1時(shí)步長為初始步長S0，x為總階段數(shù)時(shí)步長為N。即可得出a、b。文獻(xiàn)[6]中定義相鄰階段重建信號能量差的斜率為R：階段能量差除以階段值。設(shè)置閾值R1、R2。迭代過程分為兩部分：當(dāng)R>R1時(shí)，[S（x）=N-S0Stage3-1N+xN-X3+S0Stage3-NStage3-1]將能量快速下降的過程定義為大步長階段，采用大步長快速逼近，可減少迭代次數(shù)和運(yùn)算時(shí)間。當(dāng)R2

2.1.3 能量比閾值的設(shè)定

定義 X為原始稀疏信號，Y為測量向量，如果觀測矩陣滿足有限等距性質(zhì)，得到測量向量與稀疏信號能量比率的范圍（0.63，1.307）。

證明：文獻(xiàn)[7]和[8]給出證明過程。如果保證測量矩陣和變換基不相干，則傳感矩陣滿足有限等距性質(zhì)。在信號重建過程中，根據(jù)該能量比率設(shè)定步長階段的閾值。

2.2 算法的步驟

輸入：觀測值y，觀測矩陣，初始步長S0。輸出：x的近似稀疏解。初始化殘差為y，支撐集為空， K0=1。

1）稀疏度估計(jì)：集合U為觀測矩陣和y的內(nèi)積絕對值，取U中前K0個(gè)子集。判斷是否滿足估計(jì)公式，如果結(jié)果為真，則K0增1，反之K0為所求的稀疏度

估計(jì)，即為初始步長。其中K0為接近且小于K的值。即為初始步長。

2）計(jì)算內(nèi)積，并將L個(gè)最大原子存入S；得到候選支撐集Ck；

3）正則化：選擇S對應(yīng)的向量Xs。找出所有S的子集，使得所有的列向量滿足[xm≤2xn]，選擇具有最大能量的集合Si。

4）合并集合F和S，更新殘差r。

5）如果R>R1，繼續(xù)步驟g，反之繼續(xù)步驟f。

6） 如果R2

7）如果R

8） 如果測量向量與稀疏信號能量比率大于1.38，進(jìn)入“大步長”階段，Stage自增1，根據(jù)公式計(jì)算新步長step，并更新步長L，t自增1，轉(zhuǎn)至步驟b；反之繼續(xù)步驟h。

9） 更新殘差，t自增，保存集合，轉(zhuǎn)至步驟b。

3 總結(jié)

壓縮感知理論一經(jīng)提出就引起廣泛關(guān)注，基于壓縮感知的應(yīng)用層出不窮，解決了數(shù)據(jù)采樣、傳輸和存儲等諸多問題，為很多領(lǐng)域都帶來了技術(shù)革新。不僅是在信號/圖像處理領(lǐng)域，也分布在醫(yī)療成像、射電天文、模式識別、光學(xué)/雷達(dá)成像、信道編碼等諸多領(lǐng)域。壓縮感知與傳統(tǒng)采樣有很大不用，包括非直接采樣、非均勻采樣、通過稀疏性決定采樣個(gè)數(shù)等。壓縮感知主要理論關(guān)鍵點(diǎn)在于稀疏基、采樣矩陣設(shè)計(jì)理論、范數(shù)最小化和低維觀測和信號重構(gòu)算法。當(dāng)前壓縮感知理論研究的重難點(diǎn)主要是信號重構(gòu)，改進(jìn)重構(gòu)算法也是本文的研究核心。

在稀疏自適應(yīng)匹配追蹤算法迭代過程中，由于使用固定步長且步長選擇不當(dāng)導(dǎo)致的過估計(jì)或欠估計(jì)問題。針對該問題，根據(jù)原始信號的能量差在相鄰階段是先不斷減小在趨于平穩(wěn)的規(guī)律，即初始階段變化率大，隨后趨于平穩(wěn)。本文在拋物線型步長選擇方式的基礎(chǔ)之上進(jìn)行改進(jìn)，選擇不同的拋物線函數(shù)，利用拋物線變化率先大后小的趨勢選擇步長，并設(shè)置雙閾值限定步長階段，后根據(jù)測量向量和原始信號的能量比率為迭代條件，提出了一種改進(jìn)的變步長稀疏自適應(yīng)正則化匹配追蹤算法。實(shí)驗(yàn)結(jié)果表明，該算法的重建效果較為突出，重建精度較高。

參考文獻(xiàn)：

[1] DonohoD L. Compressed sensing[J]. IEEETransactions on Information Theory， 2006， 52（4）：1289-1306.

[2] Varadarajan B， Khudanpur S， Tran T D. Stepwise optimal subspace pursuit for improving sparse recovery[J]. IEEE Signal Processing Letters， 2010， 18（1）：27-30.

[3] 楊成， 馮巍， 馮輝，等. 一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J]. 電子學(xué)報(bào)， 2010， 38（8）：1914-1917.

[4] 朱延萬， 趙擁軍， 孫兵. 一種改進(jìn)的稀疏度自適應(yīng)匹配追蹤算法[J]. 信號處理， 2012， 28（1）：80-86.

[5] 畢學(xué)霞， 尚振宏， 強(qiáng)振平，等. 一種基于變步長的稀疏度自適應(yīng)匹配追蹤算法[J]. 系統(tǒng)仿真學(xué)報(bào)， 2014， 26（9）：2116-2120.

[6] 杜秀麗， 胡興， 顧斌斌， 等. 基于變步長的正則回溯 SAMP 壓縮感知重構(gòu)算法[J/OL]. [2017-03-31]. http：//www.arocmag.com/article/02-2018-04-010.html.

[7] 李保珠， 邵建華， 聶夢雅，等. 基于能量的稀疏自適應(yīng)匹配追蹤算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2015， 32（11）：121-125.

[8] Cai T T， Wang L， Xu G. New Bounds for Restricted Isometry Constants[J]. IEEE Transactions on Information Theory It， 2009， 56（9）：4388-4394.