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

陳鳳華,李雙安

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

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

陳鳳華,李雙安

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

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

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

1　引言

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

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

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

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

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

2　算法

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

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

其中

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

其中

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

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

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

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

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

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

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

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

其中

引理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‖＜∈,且光滑參數(shù)τk≤∈,算法停止;否則,轉(zhuǎn)下一步;

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

步驟3計算步長αk:

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

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

3　全局收斂性

本文提出用修正HS共軛梯度法解決大規(guī)模信號恢復(fù)問題(2.1),且在適當?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],有如下兩個引理.

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

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

引理3.2[8]若假設(shè)條件H1、H2成立,對任一共軛梯度法的迭代形式(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,使得當k≥k0有

因此?k＞k0有

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

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

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

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

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

所以

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

4　數(shù)值實驗

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

表1、圖1選取A的維數(shù)都是512×1024,表2對應(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:信號維數(shù)按遞增規(guī)則產(chǎn)生的數(shù)值結(jié)果

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

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

5　結(jié)論

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

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

圖4.3:修正HS共軛梯度法(圖中標為MHSCG)與HS共軛梯度法(圖中標為HSCG)、PRP共軛梯度法(圖中標為PRPCG)作比較,上圖分別反映了目標函數(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ī)模信號恢復(fù)問題[J].數(shù)學(xué)雜志,2015,35(3):727-734.

[11]房明磊,朱志斌.互補約束規(guī)劃問題的一個廣義梯度投影法[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)主題分類號:90C05;65K05O221.1

A

0255-7797(2016)06-1291-08

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

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

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