高雷阜 徐 部

(遼寧工程技術(shù)大學理學院 遼寧 阜新 123000)

0 引 言

壓縮感知[1-3]CS(Compressed Sensing)是E.Candès、T.Tao等提出的一種尋找欠定線性系統(tǒng)稀疏解的技術(shù)。其核心思想是：若原始信號經(jīng)某些正交變換(如小波變換，傅里葉變換)后滿足稀疏或近似稀疏性，則可以將信號投影到低維空間，再通過最優(yōu)化方法較為精確地實現(xiàn)信號重構(gòu)。CS理論為降低信號采樣成本、減少數(shù)據(jù)存儲傳輸代價帶來了新契機，已廣泛應用于遙感圖像[4]、醫(yī)學成像[5]和無線傳感器網(wǎng)絡[6]等眾多領(lǐng)域。

在CS理論中，信號重建的作用至關(guān)重要，其目標是尋求計算復雜度低且能夠?qū)崿F(xiàn)信號精確復原的算法。一種直觀的重構(gòu)方法是求解l0-正則化問題，即利用信號滿足稀疏性的先驗信息，在欠定線性系統(tǒng)中尋求具有最稀疏性的信號，但該求解方式難以計算。因此，當信號足夠稀疏且不含噪聲時，常采用與之等價的基追蹤BP[7]方法重建信號。然而，在許多實際問題中，信號會受到噪聲干擾。對于含高斯噪聲的信號，CS理論將BP算法轉(zhuǎn)化為極小化l1-l2范數(shù)BPDN(Basis Pursuit Denoising)問題求解。但是當噪聲具備稀疏結(jié)構(gòu)(如脈沖噪聲)時，該類方法很難實現(xiàn)信號的精確重建[8]。

為此，文獻[9]用l1-范數(shù)擬合項取代BPDN中的l2-范數(shù)擬合項，提出一種l1-l1模型，將其應用于人臉識別問題并取得較好效果，但該文獻通過線性規(guī)劃方法求解l1-l1模型，因而求解速度較慢；文獻[10]提出DADM(Dual-based Alternating Direction Method)，該方法將l1-l1模型轉(zhuǎn)化為等價的BP問題，并采用交替方向乘子法ADMM(Alternating Direction Method of Multipliers)[11-12]求解，結(jié)果表明若信號中含有大量脈沖噪聲，相比于BPDN方法，DADM能夠更好地實現(xiàn)信號重建。但該算法要求感知矩陣行正交以使其收斂。然而，對于l1-l1范數(shù)極小化問題，感知矩陣通常為隨機陣，很難滿足這一條件[13]。因此，本文提出采用一種帶有“重啟動”策略的快速交替方向乘子法FADMM[14]求解l1-l1問題以實現(xiàn)信號重構(gòu)。該算法在求解過程中無需將l1-l1模型轉(zhuǎn)化為BP問題且不要求感知矩陣滿足行正交性，同樣適用于受到大量脈沖噪聲及少量高斯白噪聲干擾的信號重構(gòu)問題。

1 壓縮感知基本理論

任給信號f∈RN×1，若其在一組標準正交基底Ψ={ψ1,ψ2,…,ψN}下能夠稀疏表示為f=Ψx，其中x∈RN×1為Ψ域的稀疏系數(shù)，則可通過與Ψ非相干的測量矩陣ΦM×N(M<

b=ΦΨx=Ax

(1)

稱A=ΦΨ為感知矩陣。對于無噪信號，Chen等[7]提出可采用BP算法求解式:

min{‖x‖1:Ax=b}

(2)

若b受到噪聲干擾，則很難由上式較為精確地實現(xiàn)信號重建。因此，將式(2)中的約束條件進行松弛處理，轉(zhuǎn)化為有約束形式的BPDN問題：

min{‖x‖1:‖Ax-b‖≤δ}

(3)

式中：δ>0是噪聲水平的上界。由于可將無約束的式(3)作為二次規(guī)劃問題求解[15]，所以通常采用其無約束形式重建信號：

μ的作用為平衡正則與擬合項。文獻[10]提出，若信號中含有脈沖噪聲，求解極小化l1-l1范數(shù)問題：

min‖Ax-b‖1+λ‖x‖1

(4)

能夠取得更好的重構(gòu)效果，其中λ>0為正則參數(shù)。該類問題也被應用于圖像修復[16]、人臉識別[17]等領(lǐng)域。

2 快速交替方向乘子法(FADMM)

2.1 交替方向乘子法(ADMM)

ADMM融合了對偶上升法與乘子法的優(yōu)點，適用于求解大規(guī)模凸優(yōu)化問題[11]。該算法所求問題的形式如下：

minf(x)+g(z)

s.t.Ax+Bz=b

(5)

式中：A∈RM×N，B∈RM×P，b∈RM×1，f和g為凸函數(shù)。式(5)的增廣Lagrangian函數(shù)可表示為：

Lρ(x,z,y)=f(x)+g(z)+yT(Ax+Bz-b)+

(ρ/2)‖Ax+Bz-b‖2

式中：y∈RM×1是對偶變量，ρ>0為罰參。與乘子法通過最小化Lρ(x,z,y)來同時求解兩個原始變量的方式不同，ADMM引入單步高斯-賽德爾策略，固定其余變量，交替更新x和z：

(6)

直至滿足迭代終止要求，得式(5)所求解。

2.2 帶有“重啟動”規(guī)則的FADMM

在實際環(huán)境下，信號中通常含有噪聲。當信號及干擾噪聲同時滿足稀疏性時，通過求解l1-l1模型能夠更好地實現(xiàn)信號重建。雖然該模型是一個凸問題，但由于l1范數(shù)僅滿足弱凸性且不可導，因而很難對l1-l1范數(shù)極小化問題進行求解。本文提出采用一種帶有“重啟動”規(guī)則的FADMM算法來解決l1-l1范數(shù)極小化難以求解的問題。

具體的求解過程為：采用變量分裂方法，將式(4)轉(zhuǎn)變?yōu)榧s束優(yōu)化問題：

minλ‖x‖1+‖z‖1s.t.Ax+z=b

令f=λ‖x‖1，g=‖z‖1，B=I，并用式(6)對其求解。固定z、y，更新x：

(7)

由于感知矩陣A的存在，使式(7)不存在解析解，因而在xk-1點處線性化二次項并加入迫近項可得:

xk= arg minxλ‖x‖1+

Τλtk/ρ(xk-1-tkgk)

更新對偶變量：

yk=yk-1+ρ(Axk+zk-b)

與ADMM算法不同，F(xiàn)ADMM沿用Nesterov梯度下降法[18]中的加速思想，對zk和yk進行二次更新：

若迭代過程中滿足ck<ηck-1(η為遞減因子)，則執(zhí)行zk和yk的二次更新；否則，拋棄當前代，將k-1代信息作為新的起始點，重新開始算法，以使其聯(lián)合誤差不增加，因而保證了FADMM的全局收斂性。但由于式(7)在求解過程中采用了線性逼近方法，由文獻[12],本文中聯(lián)合誤差定義為：

本數(shù)據(jù)采集系統(tǒng)中設(shè)計的總線長32 m,每隔1 m接入一個從站單元,測試時在A1從站的第3通道接入3 V的電壓,其余通道和從站懸空,發(fā)送查詢指令后上位機收到的數(shù)據(jù)如圖9所示。

算法的流程如下所示。

算法1FADMM求解l1-l1模型步驟

1:xk=arg minxLρ(Xk-1,zk,yk)

2:zk=arg minzLρ(Xk,z,yk)

5: ifck<ηck-1then

9: else

11:ck←η-1ck-1

12: end if

13: 判斷是否滿足終止條件 ，若滿足則停止；否則，令k=k+1，轉(zhuǎn)步驟1.

3 實驗結(jié)果及分析

式中：x是原始信號，x*為重建信號。

當信號中含有脈沖噪聲時，隨著正則參數(shù)的變化，三種算法計算所得相對誤差如圖1所示。

圖1 脈沖噪聲下信號重建誤差

由圖1可見，當信號中含有少量脈沖噪聲時，由于FADMM和DADM都是對l1-l1模型進行求解，所以兩種方法的信號重構(gòu)結(jié)果在整體上好于BPDN算法。但隨著正則參數(shù)λ值的增大，DADM所得相對誤差出現(xiàn)了明顯的增加，當λ>1.1時BPDN算法重構(gòu)結(jié)果比DADM更好一些，而FADMM受正則參數(shù)變化的影響較小，當λ>1.3時相對誤差才略有增加。隨著脈沖噪聲的增大，BPDN所得相對誤差在正則參數(shù)的變化過程中相對較大，而FADMM在正則參數(shù)較大時能夠得到更好的重構(gòu)結(jié)果。

為更好地驗證FADMM的重構(gòu)效果，取λ=0.7，采用該算法對含有5%脈沖噪聲的信號進行重構(gòu)，重構(gòu)效果見圖2。

由圖2可見，當信號中含有大量脈沖噪聲時，F(xiàn)ADMM獲得了較好的重構(gòu)效果，即能夠?qū)崿F(xiàn)原始信號與重構(gòu)信號間的高度重合。由圖3(a)可見，對于白噪聲為30 dB的信號，BPDN所得相對誤差呈線性遞增趨勢；當λ>0.7時DADM已出現(xiàn)相對誤差增加，而當λ>1.1時FADMM開始出現(xiàn)相對誤差增加。隨著白噪聲的增大，BPDN逐漸顯露其優(yōu)勢。

圖3 白噪聲下信號重建誤差

表1 R對比結(jié)果

由表1可見，隨著正則參數(shù)增加，兩種算法計算所得R均呈現(xiàn)先增后減的變化趨勢。由于DADM將l1-l1模型轉(zhuǎn)化為BP問題，其在具體求解過程中正則參數(shù)會直接影響原始及對偶變量的結(jié)果，因而該算法所得R更易因正則參數(shù)的變化而改變。在λ=0.5處DADM開始出現(xiàn)重構(gòu)信噪比減少，且遞減幅度較大，而FADMM在正則參數(shù)從0.3增加至1.1的過程中R變化幅度較小，因而整體上FADMM的重構(gòu)結(jié)果好于DADM算法。隨著采樣率的減小，DADM更易得到低R。相比于DADM算法，F(xiàn)ADMM能夠適應不同λ下的信號重構(gòu)。

4 結(jié) 語

針對極小化l1-l1范數(shù)難以求解的問題，本文采用FADMM對該模型求解。利用變量分裂技術(shù)，將l1-l1模型轉(zhuǎn)變?yōu)榧s束優(yōu)化問題，采用單步高斯-賽德爾思想，交替更新原始及對偶變量，并對變量執(zhí)行二次更新，引入重啟動規(guī)則以保證FADMM全局收斂，直至滿足終止要求，所得結(jié)果即為重構(gòu)的最優(yōu)解。實驗結(jié)果表明，對于含大量脈沖噪聲及少量白噪聲的信號，本文方法均能較好地實現(xiàn)重構(gòu)。下一步的計劃是將極小化l1-l1模型應用于含噪圖像重建等問題。