CIRCULANT PRECONDITIONED TOEPLITZ LEAST-SQUARES ITERATIONS

被引:40
作者
CHAN, RH
NAGY, JG
PLEMMONS, RJ
机构
[1] UNIV MINNESOTA,INST MATH & APPLICAT,MINNEAPOLIS,MN 55455
[2] WAKE FOREST UNIV,DEPT MATH & COMP SCI,WINSTON SALEM,NC 27109
关键词
LEAST SQUARES; TOEPLITZ MATRIX; CIRCULANT MATRIX; PRECONDITIONED CONJUGATE GRADIENTS; REGULARIZATION;
D O I
10.1137/S0895479891223021
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The authors consider the solution of least squares problems min parallel to b - Tx parallel to(2) by the preconditioned conjugate gradient method, for m-by-n complex Toeplitz matrices T of rank n. A circulant preconditioner C is derived using the T. Chan optimal preconditioner on n-by-n Toeplitz row blocks of T. For Toeplitz T that are generated by a 2 pi-periodic continuous complex-valued functions without any zeros, the authors prove that the singular values of the preconditioned matrix TC-1 are clustered around 1, for sufficiently large n. The paper shows that if the condition number of T is of O(n(alpha)), alpha > 0, then the least squares conjugate gradient method converges in at most O(cd alpha log n+1) steps. Since each iteration requires only O(m log n) operations using the Fast Fourier Transform, it follows that the total complexity of the algorithm is then only O(alpha m log(2) n+m log n). Conditions for superlinear convergence are given and regularization techniques leading to superlinear convergence for least squares computations with ill-conditioned Toeplitz matrices arising from inverse problems are derived. Numerical examples ace provided illustrating the effectiveness of the authors' methods.
引用
收藏
页码:80 / 97
页数:18
相关论文
共 32 条
[1]  
ABBISS J, 1987, MATH SIGNAL PROCESSI
[2]   SUPERFAST SOLUTION OF REAL POSITIVE DEFINITE TOEPLITZ-SYSTEMS [J].
AMMAR, GS ;
GRAGG, WB .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1988, 9 (01) :61-76
[3]  
Andrews H, 1977, DIGITAL IMAGE RESTOR
[4]   ON THE RATE OF CONVERGENCE OF THE PRECONDITIONED CONJUGATE-GRADIENT METHOD [J].
AXELSSON, O ;
LINDSKOG, G .
NUMERISCHE MATHEMATIK, 1986, 48 (05) :499-523
[5]  
Axelsson O., 1984, FINITE ELEMENT SOLUT
[6]  
BIEDMOND J, 1990, P IEEE, V78, P856
[7]  
BJORCK A, 1989, HDB NUMERICAL METHOD, V1
[8]   STABILITY OF METHODS FOR SOLVING TOEPLITZ-SYSTEMS OF EQUATIONS [J].
BUNCH, JR .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1985, 6 (02) :349-364
[9]  
CHAN R, 1992, SPIE P, V1770, P60
[10]  
CHAN R, 1992, 916 U HONG KONG DEP