壓縮感知中基于FADMM的l1-l1范數信號重構

高雷阜 徐 部

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

0 引 言

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

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

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

1 壓縮感知基本理論

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

b=ΦΨx=Ax

(1)

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

min{‖x‖1:Ax=b}

(2)

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

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

(3)

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

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

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

(4)

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

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

2.1 交替方向乘子法(ADMM)

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

minf(x)+g(z)

s.t.Ax+Bz=b

(5)

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

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 帶有“重啟動”規則的FADMM

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

具體的求解過程為：采用變量分裂方法，將式(4)轉變為約束優化問題：

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算法不同，FADMM沿用Nesterov梯度下降法[18]中的加速思想，對zk和yk進行二次更新：

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

本數據采集系統中設計的總線長32 m,每隔1 m接入一個從站單元,測試時在A1從站的第3通道接入3 V的電壓,其余通道和從站懸空,發送查詢指令后上位機收到的數據如圖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，轉步驟1.

3 實驗結果及分析

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

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

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

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

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

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

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

表1 R對比結果

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

4 結 語

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