修正HS共軛梯度法在大規模信號重構問題中的應用

陳鳳華,李雙安

(鄭州工商學院公共基礎教學部,河南鄭州451400)

修正HS共軛梯度法在大規模信號重構問題中的應用

陳鳳華,李雙安

(鄭州工商學院公共基礎教學部,河南鄭州451400)

本文研究了壓縮感知在大規模信號恢復問題中應用的問題.利用修正HS共軛梯度法及光滑化方法,獲得了具有較好重構效果的算法.數值實驗表明用修正HS共軛梯度法解決大規模信號恢復問題是可行的.

壓縮感知;修正HS共軛梯度法;稀疏信號;Nesterov光滑技術

1　引言

在壓縮感知問題中,若先驗知道原信號在某個變換下是可壓縮的(或是稀疏的),則可以通過如下一個最小?0范數問題恢復信號

這里?0范數表示向量非零元素的個數.但是求解最小?0范數問題是一個NP難問題,即最小?0范數問題的求解需要列舉原信號中非零值的所有排列組合情況,計算量巨大,相關研究見文獻[1].

此后,人們轉而求解最小?1范數問題,而且證明了在一定的條件下,最小?1范數問題和最小?0范數問題的解是等價的,見文獻[2].因此問題(1.1)轉化為求解下面的最小?1范數問題

最小?1范數問題的求解是一個凸優化問題,這個問題能夠轉化為線性規劃問題,見文獻[3,4].然而在實際中求解線性規劃問題(1.2)是很難的.在壓縮感知問題中,當矩陣A是大且稠密的,線性規劃問題(1.2)常常是病態的.設矩陣A是行滿秩的,問題(1.2)可轉化為?1正則化最小二乘問題(見文獻[5])

這里λ是正則化參數.

2　算法

因為‖u‖1是關于u的非光滑凸函數,所以對于問題(1.3),次梯度基本方法的效果可能很差.本文通過求解問題(1.3)的一個適當的光滑形式,來求解?1最小化問題(1.2).

由文獻[6],利用Nesterov光滑技術,光滑化‖u‖1為如下光滑函數

其中

光滑函數fτ(u)是凸的,梯度?fτ(u)是Lipchitz連續的,且其分量為

其中

令F(u)=λfτ(u)+則問題(1.3)轉化為如下無約束光滑凸規劃問題

F(u)是可微的,其梯度?F(u)=λ?fτ(u)+AT(Au-b)是Lipchitz連續的.為方便,記gk=?F(uk),yk=?F(uk+1)-?F(uk)=gk+1-gk.

求解問題(2.1),共軛梯度法的迭代公式如下

其中αk為搜索步長,dk為搜索方向,βk為參數.

共軛梯度法的關鍵是參數βk的選取,常用的βk公式有如下幾種

一些文獻對βk的構造及算法的收斂性做了大量的研究,見文獻[7,8].文獻[8]指出, PRP,HS方法在數值計算中有很好的表現,但是即使使用精確線搜索PRP方法也不會有全局收斂性.FR,DY方法則具有較好的收斂性質.為尋求兼具良好收斂性和優秀數值結果的算法,許多研究者在經典共軛梯度法的基礎上推出新的βk公式.

本文我們提出用修正HS共軛梯度法解決大規模信號恢復問題(2.1),且在適當的假設條件下證明了本文提出的算法具有全局收斂性,最后數值實驗結果表明用修正HS共軛梯度法解決大規模信號恢復問題是可行的．

本文構造如下搜索方向

其中

引理2.1對任一線搜索,搜索方向由(2.4)式定義,則有

證由(2.4)式,有

算法2.1問題(2.1)的修正HS共軛梯度算法:

步驟0給定初始點u0∈Rn,終止誤差0≤∈?1,τ0=0.6,0＜ρ1＜ρ2＜1,令k:=0;

步驟1計算gk=?F(uk),若‖gk‖＜∈,且光滑參數τk≤∈,算法停止;否則,轉下一步;

步驟2計算搜索方向dk,搜索方向由(2.4)式定義;

步驟3計算步長αk:

步驟4更新:令uk+1=uk+αkdk,更新光滑參數

步驟5循環:置k:=k+1,轉步驟1.

3　全局收斂性

本文提出用修正HS共軛梯度法解決大規模信號恢復問題(2.1),且在適當的假設條件下證明了本文提出的算法具有全局收斂性.

為證明算法2.1具有全局收斂性,先作如下基本假設.

H1水平集Ω={x∈Rn|F(x)≤F(x0)}有界.

H2在Ω的某鄰域N內,F(x)連續可微,且其梯度?F(x)=g(x)是Lipschitz連續的,即存在一常數L＞0使得

由假設H1、H2知,存在一常數M＞0滿足

[8,9],有如下兩個引理.

引理3.1[9]若假設條件H1、H2成立,則算法是良定的.

注由(2.6)式知目標函數值序列{F(xk)}是一下降序列,有＜+∞,結合(3.2)式有

引理3.2[8]若假設條件H1、H2成立,對任一共軛梯度法的迭代形式(2.2),其中dk滿足＜0且αk滿足條件(2.6)和(2.7),則

式(3.4)結合式(2.5)有

定理3.3如果假設條件H1、H2成立,算法2.1產生的迭代序列為{uk},若存在常數r＞0滿足

證由(2.4)式定義的dk及式(3.1)、(3.2)、(3.6)有

由(3.3)式知存在一常數t∈(0,1),存在一正整數k,使得當k≥k0有

因此?k＞k0有

式(3.5)結合式(3.7)有

在壓縮感知理論中,當{min‖u‖1:Au=b}有唯一解時,精確恢復才會實現.參考文獻[5],有下面的定理.

定理3.4設?1范數最小化問題min{‖u‖1:Au=b}有唯一最優解,算法2.1產生的迭代序列為{uk},當‖u‖1的光滑參數τk→0時,則=u?,這里u?=argmin{‖u‖1: Au=b}.

證記第k步的目標函數Fk(u)的最小值點為即

因為Fk(u)是凸函數,有Lipschitz連續梯度,由文獻[5]引理2.3有,Lipschitz常數滿足

所以

故當光滑參數τk→0時,(3.8)式表明序列{uk}有極限點.令u?表示這個序列的任意極限點,由文獻[5]結合定理3.3,可證u?是可行點,且是問題(1.2)的KKT點.又問題(1.2)是凸規劃問題,故u?是問題(1.2)的最優解.

4　數值實驗

實驗中,參數選取ρ1=0.2,ρ2=0.7,誤差精度∈=10-8.A為m×n維隨機矩陣,uexact表示n維k稀疏原信號,滿足Auexact=b,u表示本文算法恢復出來的信號,相對殘差相對誤差圖1和圖2中的圈和點分別表示原信號和經由我們的算法恢復出來的信號.

表1、圖1選取A的維數都是512×1024,表2對應的正則化參數λ=0.1,圖2選取A的維數分別是256×512,512×1024,1024×2048,2048×4096.

表4.1:λ按遞減規則產生的數值結果

表4.2:信號維數按遞增規則產生的數值結果

表4　.3:信號維數按遞增規則產生的數值結果

圖4.1:四幅圖分別表示λ不同取值下的信號恢復效果圖

5　結論

本文提出用基于Nesterov光滑技術和修正HS共軛梯度法的壓縮感知重構算法解決大規模信號恢復問題,最后做了兩類數值實驗,第一類反映了隨著正則化參數λ的變化,相對殘差、相對誤差、運行時間的變化,以及隨著原信號的維數的變化,相對殘差、相對誤差、運行時間的變化;第二類實驗用本文提出的修正HS共軛梯度法與HS共軛梯度法、PRP共軛梯度法解決大規模信號恢復問題作對比,實驗結果表明用修正HS共軛梯度法解決大規模信號恢復問題是可行的.該算法在圖像處理中有直接的應用價值.相關研究見文獻[10,11].

圖4.2:四幅圖分別表示信號維數不同取值下的信號恢復效果圖

圖4.3:修正HS共軛梯度法(圖中標為MHSCG)與HS共軛梯度法(圖中標為HSCG)、PRP共軛梯度法(圖中標為PRPCG)作比較,上圖分別反映了目標函數值、相對誤差、相對殘差隨迭代步、運行時間的變化.

[1]Zhu H,Xiao Y,Wu S Y.Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique[J].Comp.Math.Appl.,2013,66(1):24-32.

[2]Donoho D L.For most large underdetermined systems of linear equations the minimal 1-norm solution is also the sparsest solution[J].Commun.Pure Appl.Math.,2006,59(6):797-829.

[3]Candes E J,Tao T.Near Optimal Signal Recovery From Random Projections And Universal Encoding Strategies[J].IEEE Trans.Inform.The.,2007,52(12):5406-5425.

[4]Donoho L D.Compressed sensing[J].IEEE Trans.Inform.The.,2006,52(4):1289-1306.

[5]Aybat S N,Iyengar G.A first-order smoothed penalty method for compressed sensing[J].SIAM J. Optim.,2011,21(1):287-313.

[6]Nesterov Y.Smooth minimization of non-smooth functions[J].Math.Prog.,2005,103(1):127-152.

[7]Al Baali M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].IMA J.Numer.Anal.,1985,5(1):121-124.

[8]Ioannis E,Livieris,Panagiotis Pintelas.Globally convergent modified Perry’s conjugate gradient method[J].Appl.Math.Comp.,2012,218(18):9197-9207.

[9]Zhang L,Zhou W,Li D H.A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence[J].Ima.J.Numer.Anal.,2006,26(4):629-640.

[10]陳鳳華,李雙安.BFGS校正擬牛頓法解決大規模信號恢復問題[J].數學雜志,2015,35(3):727-734.

[11]房明磊,朱志斌.互補約束規劃問題的一個廣義梯度投影法[J].數學雜志,2011,31(4):685-694.

2010 MR Subject Classification:90C05;65K05

THE APPLICATION OF A MODIFIED HS CONJUGATE GRADIENT METHOD FOR LARGE-SCALE SIGNAL RECONSTRUCTION PROBLEM

CHEN Feng-hua,LI Shuang-an
(Teaching Department of the Public Infrastructure,Zhengzhou Technology and Business University, Zhengzhou 451400,China)

In this paper we study application about the compressed sensing in large-scale signal recovery problem.By the modified HS conjugate gradient method and smoothing technique, the algorithm which possesses better reconstruction effect is obtained.Preliminary numerical results show that our algorithm is suitable for solving large-scale sparse signal recovery problems.

compressed sensing;modified HS conjugate gradient method;sparse signal; Nesterov’s smoothing technique

MR(2010)主題分類號:90C05;65K05O221.1

A

0255-7797(2016)06-1291-08

?2015-12-16接收日期:2016-04-15

國家自然科學基金(11061011;11361018);河南省高等學校重點科研項目(17A110032);河南省教育廳科學技術研究重點項目(12B110011).

陳鳳華(1982-),女,湖北仙桃,講師,主要研究方向:優化理論與算法研究.