修正HS共軛梯度法在大規(guī)模信號(hào)重構(gòu)問(wèn)題中的應(yīng)用

陳鳳華,李雙安

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

修正HS共軛梯度法在大規(guī)模信號(hào)重構(gòu)問(wèn)題中的應(yīng)用

陳鳳華,李雙安

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

本文研究了壓縮感知在大規(guī)模信號(hào)恢復(fù)問(wèn)題中應(yīng)用的問(wèn)題.利用修正HS共軛梯度法及光滑化方法,獲得了具有較好重構(gòu)效果的算法.數(shù)值實(shí)驗(yàn)表明用修正HS共軛梯度法解決大規(guī)模信號(hào)恢復(fù)問(wèn)題是可行的.

壓縮感知;修正HS共軛梯度法;稀疏信號(hào);Nesterov光滑技術(shù)

1　引言

在壓縮感知問(wèn)題中,若先驗(yàn)知道原信號(hào)在某個(gè)變換下是可壓縮的(或是稀疏的),則可以通過(guò)如下一個(gè)最小?0范數(shù)問(wèn)題恢復(fù)信號(hào)

這里?0范數(shù)表示向量非零元素的個(gè)數(shù).但是求解最小?0范數(shù)問(wèn)題是一個(gè)NP難問(wèn)題,即最小?0范數(shù)問(wèn)題的求解需要列舉原信號(hào)中非零值的所有排列組合情況,計(jì)算量巨大,相關(guān)研究見文獻(xiàn)[1].

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

最小?1范數(shù)問(wèn)題的求解是一個(gè)凸優(yōu)化問(wèn)題,這個(gè)問(wèn)題能夠轉(zhuǎn)化為線性規(guī)劃問(wèn)題,見文獻(xiàn)[3,4].然而在實(shí)際中求解線性規(guī)劃問(wèn)題(1.2)是很難的.在壓縮感知問(wèn)題中,當(dāng)矩陣A是大且稠密的,線性規(guī)劃問(wèn)題(1.2)常常是病態(tài)的.設(shè)矩陣A是行滿秩的,問(wèn)題(1.2)可轉(zhuǎn)化為?1正則化最小二乘問(wèn)題(見文獻(xiàn)[5])

這里λ是正則化參數(shù).

2　算法

因?yàn)椤瑄‖1是關(guān)于u的非光滑凸函數(shù),所以對(duì)于問(wèn)題(1.3),次梯度基本方法的效果可能很差.本文通過(guò)求解問(wèn)題(1.3)的一個(gè)適當(dāng)?shù)墓饣问?來(lái)求解?1最小化問(wèn)題(1.2).

由文獻(xiàn)[6],利用Nesterov光滑技術(shù),光滑化‖u‖1為如下光滑函數(shù)

其中

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

其中

令F(u)=λfτ(u)+則問(wèn)題(1.3)轉(zhuǎn)化為如下無(wú)約束光滑凸規(guī)劃問(wèn)題

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

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

其中αk為搜索步長(zhǎng),dk為搜索方向,βk為參數(shù).

共軛梯度法的關(guān)鍵是參數(shù)βk的選取,常用的βk公式有如下幾種

一些文獻(xiàn)對(duì)βk的構(gòu)造及算法的收斂性做了大量的研究,見文獻(xiàn)[7,8].文獻(xiàn)[8]指出, PRP,HS方法在數(shù)值計(jì)算中有很好的表現(xiàn),但是即使使用精確線搜索PRP方法也不會(huì)有全局收斂性.FR,DY方法則具有較好的收斂性質(zhì).為尋求兼具良好收斂性和優(yōu)秀數(shù)值結(jié)果的算法,許多研究者在經(jīng)典共軛梯度法的基礎(chǔ)上推出新的βk公式.

本文我們提出用修正HS共軛梯度法解決大規(guī)模信號(hào)恢復(fù)問(wèn)題(2.1),且在適當(dāng)?shù)募僭O(shè)條件下證明了本文提出的算法具有全局收斂性,最后數(shù)值實(shí)驗(yàn)結(jié)果表明用修正HS共軛梯度法解決大規(guī)模信號(hào)恢復(fù)問(wèn)題是可行的．

本文構(gòu)造如下搜索方向

其中

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

證由(2.4)式,有

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

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

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

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

步驟3計(jì)算步長(zhǎng)αk:

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

步驟5循環(huán):置k:=k+1,轉(zhuǎn)步驟1.

3　全局收斂性

本文提出用修正HS共軛梯度法解決大規(guī)模信號(hào)恢復(fù)問(wèn)題(2.1),且在適當(dāng)?shù)募僭O(shè)條件下證明了本文提出的算法具有全局收斂性.

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

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

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

由假設(shè)H1、H2知,存在一常數(shù)M＞0滿足

[8,9],有如下兩個(gè)引理.

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

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

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

式(3.4)結(jié)合式(2.5)有

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

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

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

因此?k＞k0有

式(3.5)結(jié)合式(3.7)有

在壓縮感知理論中,當(dāng){min‖u‖1:Au=b}有唯一解時(shí),精確恢復(fù)才會(huì)實(shí)現(xiàn).參考文獻(xiàn)[5],有下面的定理.

定理3.4設(shè)?1范數(shù)最小化問(wèn)題min{‖u‖1:Au=b}有唯一最優(yōu)解,算法2.1產(chǎn)生的迭代序列為{uk},當(dāng)‖u‖1的光滑參數(shù)τk→0時(shí),則=u?,這里u?=argmin{‖u‖1: Au=b}.

證記第k步的目標(biāo)函數(shù)Fk(u)的最小值點(diǎn)為即

因?yàn)镕k(u)是凸函數(shù),有Lipschitz連續(xù)梯度,由文獻(xiàn)[5]引理2.3有,Lipschitz常數(shù)滿足

所以

故當(dāng)光滑參數(shù)τk→0時(shí),(3.8)式表明序列{uk}有極限點(diǎn).令u?表示這個(gè)序列的任意極限點(diǎn),由文獻(xiàn)[5]結(jié)合定理3.3,可證u?是可行點(diǎn),且是問(wèn)題(1.2)的KKT點(diǎn).又問(wèn)題(1.2)是凸規(guī)劃問(wèn)題,故u?是問(wèn)題(1.2)的最優(yōu)解.

4　數(shù)值實(shí)驗(yàn)

實(shí)驗(yàn)中,參數(shù)選取ρ1=0.2,ρ2=0.7,誤差精度∈=10-8.A為m×n維隨機(jī)矩陣,uexact表示n維k稀疏原信號(hào),滿足Auexact=b,u表示本文算法恢復(fù)出來(lái)的信號(hào),相對(duì)殘差相對(duì)誤差圖1和圖2中的圈和點(diǎn)分別表示原信號(hào)和經(jīng)由我們的算法恢復(fù)出來(lái)的信號(hào).

表1、圖1選取A的維數(shù)都是512×1024,表2對(duì)應(yīng)的正則化參數(shù)λ=0.1,圖2選取A的維數(shù)分別是256×512,512×1024,1024×2048,2048×4096.

表4.1:λ按遞減規(guī)則產(chǎn)生的數(shù)值結(jié)果

表4.2:信號(hào)維數(shù)按遞增規(guī)則產(chǎn)生的數(shù)值結(jié)果

表4　.3:信號(hào)維數(shù)按遞增規(guī)則產(chǎn)生的數(shù)值結(jié)果

圖4.1:四幅圖分別表示λ不同取值下的信號(hào)恢復(fù)效果圖

5　結(jié)論

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

圖4.2:四幅圖分別表示信號(hào)維數(shù)不同取值下的信號(hào)恢復(fù)效果圖

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

[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校正擬牛頓法解決大規(guī)模信號(hào)恢復(fù)問(wèn)題[J].數(shù)學(xué)雜志,2015,35(3):727-734.

[11]房明磊,朱志斌.互補(bǔ)約束規(guī)劃問(wèn)題的一個(gè)廣義梯度投影法[J].數(shù)學(xué)雜志,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)主題分類號(hào):90C05;65K05O221.1

A

0255-7797(2016)06-1291-08

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

國(guó)家自然科學(xué)基金(11061011;11361018);河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(17A110032);河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(12B110011).

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