稀疏度自適應(yīng)回溯追蹤算法改進(jìn)

丁佳靜 武雪姣 李雪晴

摘 要：針對(duì)壓縮感知重構(gòu)算法中信號(hào)稀疏度未知和步長(zhǎng)大小固定的問(wèn)題，提出一種新的壓縮感知信號(hào)重構(gòu)算法，即基于弱選擇的稀疏度自適應(yīng)回溯追蹤（SPWAMP）算法。該算法將自適應(yīng)思想、變步長(zhǎng)迭代思想與回溯思想相結(jié)合，在未知信號(hào)稀疏度的情況下，利用閾值方法選取預(yù)選集，通過(guò)變步長(zhǎng)更新支撐集原子個(gè)數(shù)并結(jié)合回溯思想剔除不可靠原子，最終實(shí)現(xiàn)信號(hào)精確重構(gòu)。仿真結(jié)果表明，當(dāng)信號(hào)稀疏度K達(dá)到65時(shí)，該算法重構(gòu)精度相對(duì)稀疏度自適應(yīng)匹配追蹤（SAMP）算法提高了40%，而此時(shí)正交匹配追蹤（OMP）算法、子空間追蹤（SP）算法和分段弱選擇正交匹配追蹤（SWOMP）算法已無(wú)法實(shí)現(xiàn)重構(gòu)。因此，該算法相對(duì)其它同類(lèi)算法提高了信號(hào)重構(gòu)精度。

關(guān)鍵詞：壓縮感知;重構(gòu)算法;稀疏度自適應(yīng);信號(hào)處理

DOI：10. 11907/rjdk. 191437 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2019）008-0059-04

Improved Algorithm for Sparsity Adaptive Backtracking

DING Jia-jing， WU Xue-jiao， LI Xue-qing

（School of Information Engineering， Hebei GEO University， Shijiazhuang 050000， China）

Abstract：Aiming at the reconstruction of unknown sparsity signal and step size small fixed in compressed sensing， we put forward a new compression sensing signal reconstruction algorithm， namely sparsity adaptive backtracking algorithm based on weak selection（SPWAMP）. The algorithm combines the idea of adaptive， variable step iteration and backtracking. In the case of unknown signal sparsity，the preset is selected by threshold method， and the number of atoms in the support set is updated by variable step size and the idea of backtracking is used to eliminate the unreliable. Finally， the precise signal reconstruction is realized. Simulation results show that when the signal sparsity K reaches 65， the reconstruction accuracy of the algorithm is improved by 40% compared with SAMP， while OMP， SP and SWOMP cannot realize the reconstruction. Therefore， compared with other similar algorithms， this algorithm improves the signal reconstruction accuracy.

Key Words：compressed sensing; reconstruction algorithm; sparse degree adaptive; signal processing

作者簡(jiǎn)介：丁佳靜（1992-），女，河北地質(zhì)大學(xué)信息工程學(xué)院碩士研究生，研究方向?yàn)槿斯ぶ悄芘c機(jī)器學(xué)習(xí)。

0 引言

2004年，Donoho[1]提出壓縮感知（Conmpressed Sensing，CS）理論，指出如果信號(hào)在某個(gè)變換域是稀疏的，則可借用一個(gè)觀測(cè)矩陣將變換后的信號(hào)降維;若該觀測(cè)矩陣滿(mǎn)足約束等距性條件，可以求解最優(yōu)化問(wèn)題，并根據(jù)低維測(cè)量向量，高概率地精確恢復(fù)原始信號(hào)。該理論在信號(hào)處理領(lǐng)域有廣闊的應(yīng)用前景[2-5]。

壓縮感知理論主要由信號(hào)稀疏表示、測(cè)量矩陣構(gòu)造和重構(gòu)信號(hào)算法組成，其中，最核心的是重構(gòu)算法[6-9]，其代表性算法包括正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法[10]、子空間追蹤（Sub-space，SP）算法[11]、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）算法[12]、分段正交匹配追蹤（Stagewise Orthogonal Matching Pursuit，StOMP）算法[13]和稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）算法[14]。2010年楊成等[15]提出一種新的稀疏度自適應(yīng)子空間追蹤算法，該算法在每次迭代中采用弱匹配原則選取新原子，并引入SAMP自適應(yīng)思想，再通過(guò)回溯思想提高重構(gòu)準(zhǔn)確性;2013年Xue等[16]提出VSStAMP（Variable Step size Stagewise Adaptive Matching Pursuit）算法，該算法根據(jù)判斷候選集中包含原子的個(gè)數(shù)作為變步長(zhǎng)的標(biāo)準(zhǔn)，當(dāng)原子個(gè)數(shù)小于u*M時(shí)采用大步長(zhǎng)2*s，當(dāng)原子個(gè)數(shù)小于u*M時(shí)采用小步長(zhǎng)s。

本文在現(xiàn)有壓縮感知重構(gòu)算法的基礎(chǔ)上，針對(duì)實(shí)際信號(hào)稀疏度大多未知及步長(zhǎng)大小固定的問(wèn)題，結(jié)合SP算法的回溯思想和SAMP算法的自適應(yīng)思想，并運(yùn)用弱匹配原則選取新原子和變步長(zhǎng)思想，提出一種改進(jìn)的基于弱選擇的稀疏度自適應(yīng)回溯追蹤（Sparsity subspace Weak Adaptive Matching Pursuit，SPWAMP）算法。

1 壓縮感知理論

壓縮感知理論中待采樣的信號(hào)能夠?qū)崿F(xiàn)壓縮感知技術(shù)的前提是該信號(hào)是稀疏的，即利用信號(hào)可壓縮性減少采樣樣本數(shù)目，且可以重建原始信號(hào)。壓縮感知與普通采樣率不同之處在于，測(cè)量對(duì)象不再是信號(hào)的某一采樣點(diǎn)數(shù)據(jù)，而是一組用于描述信號(hào)的線(xiàn)性方程[17-18]。

假設(shè)待采樣信號(hào)[x]的長(zhǎng)度為[N]，觀測(cè)信號(hào)[y]的長(zhǎng)度為[M]（[M<

[y=Φx]? ? ? ? ? ? ? ? （1）

[x]一般不是稀疏的，但在某個(gè)變換域[Ψ]是稀疏的，即[x=Ψθ]。此時(shí)[y=ΦΨθ]，令[A=ΦΨ]，則[y=Aθ]。其中[θ]表示[K]是稀疏的，即[θ]只有[K]個(gè)非零項(xiàng)，是信號(hào)[x]在某變換域的系數(shù)表示，[Φ]是大小為[M×N]的測(cè)量矩陣，[Ψ]是大小為[N×N]的稀疏矩陣，[A]是大小為[M×N]的傳感矩陣。

根據(jù)觀測(cè)值[y]，利用稀疏重構(gòu)關(guān)系和重構(gòu)算法重構(gòu)信號(hào)[x]，可求解[l1]范數(shù)優(yōu)化問(wèn)題：

[minαα1s.t.y=Ax]? ? ? ? （2）

從觀測(cè)值[y]中恢復(fù)稀疏系數(shù)[θ]，進(jìn)而求出信號(hào)[x]的精確估計(jì)[19-20]。

2 基于弱選擇的稀疏度自適應(yīng)回溯追蹤算法

壓縮感知中子空間追蹤（SP）算法在每次迭代中選擇多個(gè)原子，利用回溯思想，在每次迭代過(guò)程中重新估計(jì)所有候選者的可信賴(lài)性，但其自身也有不足，必須以稀疏度作為輸入?yún)?shù)。

2.1 SP算法

SP 算法核心步驟：

輸入：[M×N] 傳感矩陣[A]

[N]維觀測(cè)向量[y]

信號(hào)稀疏度[K]

（1）初始化[r0=y，Λ0=φ，A0=φ，t=1]。

（2）計(jì)算內(nèi)積[u=abs[ΑTrt-1]]（即計(jì)算[rt-1，aj]，[1][jN]），選擇[u]中[K]個(gè)最大值，將這些值對(duì)應(yīng)[Α]的列序號(hào)[j]構(gòu)成集合[J0]（列序號(hào)集合）。

（3）令[Λt=Λt-1？J0]，[Αt=Αt-1？aj][（j∈J0）]。

（4）從[θt]中選出絕對(duì)值最大的[K]項(xiàng)記為[θtK]，對(duì)應(yīng)[At]中[K]列記為[AtK]，對(duì)應(yīng)[A]的列序號(hào)記為[ΛtK]，更新集合[Λt]=[ΛtK]。

（5）求[y=Αtθt]的最小二乘解：[θt=argminθ||y-Αtθt||=][（ΑTtAt）-1ATty]。

（6）更新殘差，使得[rt=y-ΑtKθtK=y-ΑtK（ΑTtKΑtK）-1][ΑTtKy]。

（7）[t=t+1]，如果[t≤S]則返回第（2）步繼續(xù)迭代，如果[t>S]或殘差[rt=0]則停止迭代進(jìn)入。

（8）重構(gòu)得[θ]在[ΛtK]處有非零項(xiàng)，其值分別為最后一次迭代所得[θtK]。

輸出：信號(hào)稀疏表示系數(shù)估計(jì)[θ]

[N×1]維殘差[rS=y-ASθS]

2.2 SPWAMP算法

本文算法在SP算法的基礎(chǔ)上，采用弱匹配原則選取新原子，結(jié)合SAMP算法自適應(yīng)思想在迭代過(guò)程中自動(dòng)調(diào)整所選原子數(shù)目，并采用變步長(zhǎng)提高信號(hào)重構(gòu)精度[21]。當(dāng)算法在開(kāi)始執(zhí)行時(shí)采用大步長(zhǎng)快速接近（使用冪函數(shù)變步長(zhǎng)），當(dāng)接近目標(biāo)時(shí)，采用小步長(zhǎng)（步長(zhǎng)為原步長(zhǎng)的0.5倍），并且通過(guò)相鄰信號(hào)能量之間的關(guān)系作為改變步長(zhǎng)的標(biāo)準(zhǔn)。

總之，基于弱選擇的稀疏度自適應(yīng)回溯追蹤（SPWAMP）算法是一種結(jié)合SP算法的回溯思想和SAMP算法的自適應(yīng)思想，并通過(guò)弱匹配原則選取新原子和變步長(zhǎng)思想的新重構(gòu)算法，提高了算法重構(gòu)精度。

SPWAMP 算法核心步驟為：

輸入：[M×N]的傳感矩陣[A=ΦΨ]

[N×1]? 維觀測(cè)向量[y]

步長(zhǎng)[S]

（1）初始化[r0=y，Λ0=φ，L=S，t=1]。

（2）計(jì)算[u=abs[ΑTrt-1]]（即計(jì)算[rt-1，aj]，[1jN]），選擇[u]中[L]個(gè)最大值，將這些值對(duì)應(yīng)[Α]的列序號(hào)[j]構(gòu)成集合[Sk]（列序號(hào)集合）;選擇[u]中大于門(mén)限[Th]的值，將這些值對(duì)應(yīng)A的列序號(hào)[j]構(gòu)成集合[J0]（列序號(hào)集合）。

（3）令[Ck=Λt-1？Sk？J0][Αt={aj}][（for? all? j∈Ck）]。

（4）求[y=Αtθt]的最小二乘解：[θt=argminθ||y-Αtθt||=][（ΑTtAt）-1ATty]。

（5）從[θt]的中選出絕對(duì)值最大的[L]項(xiàng)記為[θtL]，對(duì)應(yīng)的[At]中的[L]列記為[AtL]，對(duì)應(yīng)的[A]的列序號(hào)記為[ΛtL]，更新集合[F]=[ΛtL]。

（6）更新殘差，使得[rnew=y-ΑtL（ΑTtLΑtL）-1ΑTtLy]。

（7）如果[rnew≤1e-6]，則停止迭代進(jìn)入，第（10）步。

（8）如果[rnew2≤rt-12]，則[Λt=F]，[rt=rnew]，[t=][t+][1]，否則進(jìn)入第（9）步。

[9] 劉浩強(qiáng)，趙洪博，馮文全. 基于CS的正則化稀疏度變步長(zhǎng)自適應(yīng)匹配追蹤算法[J]. 北京航空航天大學(xué)學(xué)報(bào)，2017，43（10）：2109-2117.

[10] 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.

[11] WEI D， MILENKOVIC O. Subspace pursuit for Compressive Sensing signal reconstruction[J].? IEEE Transactions on Information Theory， 2009， 55（5）：2230-2249.

[12] NEEDELL D，VERSHYNIN R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit [J]. IEEE Journal of? Selscted Toptics in Signal Processing，2010，4（2）：310-316.

[13] DONOHO D L，TSAI G Y，STARCK J L. Sparse solution of under-determined linear equations by stage-wise orthogonal matching pursuit [J]. IEEE Transactions on Information Theory，2012，58（2）：1094-1121.

[14] DO? T? T，GAN L， NGUYEN N，et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing [C]. Piscataway：IEEE Conference on Signals，2008.

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

[16] XUE B I， CHEN X D， ZHANG Y U. Variable step size stagewise adaptive matching pursuit algorithm for image compressed sensing[C]. 2013 IEEE International Conference on Signal Processing， Communication and Computing，2013：1-4.

[17] 王烈，羅文，秦偉萌. 分段弱選擇自適應(yīng)正交匹配追蹤算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2018，39（12）：3767-3773.

[18] 王福馳，趙志剛，劉馨月，等. 一種改進(jìn)的稀疏度自適應(yīng)匹配追蹤算法[J]. 計(jì)算機(jī)科學(xué)，2018，45（S1）：234-238.

[19] 王欣，張嚴(yán)心，黃志清. 基于變步長(zhǎng)的正則化回溯自適應(yīng)追蹤算法[J]. 電子學(xué)報(bào)，2018，46（8）：1829-1834.

[20] 楊韌，張興敢. 壓縮感知重構(gòu)SAMP的改進(jìn)算法[J]. 南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2018，54（3）：538-542.

[21] 彬彬有禮的專(zhuān)欄. 壓縮感知重構(gòu)算法之子空間追蹤（SP）[EB/OL].https：//blog.csdn.net/jbb0523.

（責(zé)任編輯：江 艷）