張雪偉，段雪峰，江祝靈

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林　541004)

?

非單調(diào)譜投影梯度法求解Toeplitz矩陣的正則化逼近* 1

張雪偉，段雪峰，江祝靈

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林541004)

摘要：研究Toeplitz矩陣的正則化逼近問題，先利用跡函數(shù)的French導(dǎo)數(shù)給出目標(biāo)函數(shù)的梯度，再計(jì)算任意矩陣到可行集上的投影，最后利用譜投影梯度方法求解Toeplitz矩陣的正則化逼近問題，并用數(shù)值例子驗(yàn)證迭代方法的可行性.

關(guān)鍵詞：Toeplitz矩陣；正則化逼近；非單調(diào)譜投影梯度法

1引言

本文記Rn×n為n×n實(shí)矩陣集合,Tn為n×nToeplitz矩陣集合,其元素形如

PΩ(A)為矩陣A在閉凸集Ω上的投影,▽F(X)為函數(shù)矩陣F(X)的梯度,tr(X)為矩陣X的跡,‖A‖F(xiàn)為矩陣A的F范數(shù),則有性質(zhì)‖A‖F(xiàn)=tr(ATA).

本文研究Toeplitz矩陣的正則化逼近問題,即

Toeplitz矩陣是一類具有特殊結(jié)構(gòu)的矩陣,它由第一列和第一行的元素確定,且矩陣中與主對(duì)角線平行的對(duì)角線上的元素相等.Toeplitz矩陣已被廣泛的應(yīng)用于信號(hào)處理和圖像處理[1-2],工業(yè)控制理論[3].對(duì)于Toeplitz矩陣逼近問題,其主要工作在于找到一個(gè)Toeplitz結(jié)構(gòu)的矩陣來逼近給定的數(shù)據(jù)矩陣,文獻(xiàn)[4-6]提出的一種Toeplitz迭代逼近的方法能很好地解決這一問題,尤其是在計(jì)算精度上,但是當(dāng)矩陣規(guī)模較大時(shí),此方法的計(jì)算時(shí)間較長(zhǎng).J.Murakami[7]提出了一種更加有效的方法來解決大規(guī)模問題,相比迭代Toeplitz逼近方法,減少了計(jì)算時(shí)間,且規(guī)模越大計(jì)算效率越高.

非單調(diào)譜投影梯度法是由文獻(xiàn)[8]首先提出的,用來求解形如minf(x),x∈Ω的問題，其中Ω為閉凸集的優(yōu)化問題.它采用非線性搜索確定步長(zhǎng),并求解出目標(biāo)函數(shù)的梯度和任意矩陣在閉凸集上的投影,然后設(shè)計(jì)適宜的算法來求解極小化問題.近年來,該方法被大量的研究,詳見文獻(xiàn)[9-12].

2主要結(jié)論

我們先給出目標(biāo)函數(shù)的梯度▽F(X)和矩陣A在閉凸集Tn上的投影,最后利用非單調(diào)譜投影梯度方法求解問題I.

下面我們給出矩陣A在閉凸集Tn上的投影PTn(A).

下面給出求解問題I的非單調(diào)譜投影梯度算法.算法的初始參數(shù)為:初始矩陣X0∈Tn,整數(shù)M≥1;小參數(shù)αmin>0和大參數(shù)αmax>αmin,充分小的參數(shù)γ∈(0,1)和參數(shù)0<σ1<σ2<1.任意α0∈(αmax,αmin),給定Xk∈Tn和αk∈(αmax,αmin),算法如下:

算法1

步1.檢驗(yàn)當(dāng)前點(diǎn)是否為穩(wěn)定點(diǎn). 如果‖PTn(Xk-▽F(X))-Xk‖≤tol，停止，Xk為穩(wěn)定點(diǎn).

定理2.2由算法2.1產(chǎn)生的迭代序列{Xk}收斂到問題I的解.

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

所有實(shí)驗(yàn)均在MATLAB2009a環(huán)境下進(jìn)行,采用終止條件‖Proj(Xk-▽F(Xk))-Xk‖F(xiàn)<10-10,其中▽F(Xk)為目標(biāo)函數(shù)F(X)在迭代解為Xk時(shí)的梯度.由文獻(xiàn)[8]可知,當(dāng)‖Proj(Xk-▽F(Xk))-Xk‖F(xiàn)<10-10時(shí),Xk就是問題I的逼近解.

解的投影殘差為‖Proj(Xk-▽F(Xk))-Xk‖F(xiàn)=9.222 2e-16.

例1表明用算法1求解問題I是可行的.

4結(jié)束語

本文研究譜投影梯度法求解Toeplitz矩陣的正則化逼近問題.首先,我們考慮問題I，利用矩陣范數(shù)的性質(zhì)計(jì)算出其目標(biāo)函數(shù)的梯度,并且由引理1給出了矩陣X在Toeplitz矩陣閉凸集上的投影,然后采用非單調(diào)譜投影梯度算法1求解問題I的解.最后給出數(shù)值例子驗(yàn)證了此方法的可行性.

參考文獻(xiàn)：

[1]R. Chan, M.K. Ng. Conjugate gradient methods for Toeplitz systems[J].SIAM Rev,1996,38:427-482.

[2]M. Hanke, J. Nagy. Restoration of atmospherically blurred images by symmetric indefinite conjugate gradient techniques[J].Inverse Problems,1996,12:157-173.

[3]U. Grenander, G. Szego. Toeplitz Forms and Their Applications[M].New York:2nd Edition, Chelsea:1984.

[4]D. M. Wilkes, M. H. Hayes. Block Toeplitz approximation[J].Signal Processing,1988,15:303-313.

[5]D. M. Wilkes, M. H. Hayes. Iterated Toeplitz approximation of covariance matrices[J].Acoustics Speech, and Signal Processing, 1988. ICASSP-88, 1988 International Conference on. IEEE,1988,3:1663-1666.

[6]J. A. Cadzow, D. M. Wilkes. Enhanced Rational Signal Modeling[J].Signal Processing,1991,25:171-188.

[7]J. Murakami, Y. Tadokoro. A new Toeplitz approximation method for linear prediction matrices[J].Acoustics Speech, and Signal Processing, 1993. ICASSP-93, 1993 International Conference on. IEEE,1993,3:460-463.

[8]E. G. Birgin, J. M. Martinez, M. Raydan. Nonmonotone spectral projected gradient methods on convex sets[J].SIAM J. Optim,2000,10:1196-1211.

[9]E. G. Birgin, J. M. Martinez, M. Raydan. Inexact spectral projected gradient methods on convex sets[J].SIMA J. Numer. Anal,2003,23:539-559.

[10]C. Y. Wang, Q. Liu, X. M. Yang. Convergence properties of nonmonotone spectral projected gradient method[J].J. Comput. Appl. Math,2005,182:51-66.

[11]Z. S. Yu. Solving bound constrained optimization via a new nonmonotone spectral projected gradient method[J].Appl. Numer. Math,2008,58:1340-1348.

[12]S. Bonettini, R. Zanella, L. Zanni. A scaled gradient projected method for constrained image deblurring[J].Inverse Problems,2009,25:002-015.

* 收稿日期：2016-01-20

DOI：10.13698/j.cnki.cn36-1037/c.2016.03.003

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(11561015)

作者簡(jiǎn)介：張雪偉(1990- )，男，河南安陽人，桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院在讀碩士，研究方向：數(shù)值代數(shù).

中圖分類號(hào)：O241.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1004-8332(2016)03-0011-03

Nonmonotone Spectral Projected Gradient Method for Computing the Regularization Approximation of Toeplitz Matrices

ZHANG Xuewei, DUAN Xuefeng, JIANG Zhuling

(SchoolofMathematicsandComputationalScience,GuilinUniversityofElectronicTechnology,Guilin541004,China)

Abstract:In this paper, we study the problem of the regularization approximation of Toeplitz matrices. We use the French derivative of the trace function to solve the gradient norm of the objective function, then calculate the projection of arbitrary matrix on the feasible set, and design nonmonotone spectral projected gradient method to compute the regularization approximation of the Toeplitz matrix. The numerical examples are tested to illustrate the feasibility of the iterative method.

Key words:toeplitz matrix; regularized approximation; nonmonotone spectral projected gradient method

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/36.1037.C.20160510.1229.058.html