Convergence rates of the Kaczmarz-Tanabe method for linear systems

2025-05-06 0 0 896.27KB 18 页 10玖币

侵权投诉

arXiv:2210.02602v1 [math.NA] 5 Oct 2022

Chuan-gang Kanga,∗

aSchool of Mathematical Sciences, Tiangong University, Tianjin 300387, Peoples R China

Abstract

In this paper, we investigate the Kaczmarz-Tanabe method for exact and inexact linear systems. The

Kaczmarz-Tanabe method is derived from the Kaczmarz method, but is more stable than that. We

analyze the convergence and the convergence rate of the Kaczmarz-Tanabe method based on the singu-

lar value decomposition theory, and discover two important factors, i.e., the second maximum singular

value of Qand the minimum non-zero singular value of A, that inﬂuence the convergence speed and the

amplitude of ﬂuctuation of the Kaczmarz-Tanabe method (even for the Kaczmarz method). Numerical

tests verify the theoretical results of the Kaczmarz-Tanabe method.

Keywords: Kaczmarz-Tanabe method; Convergence rates; Singular value decompositon

Mathematics Subject Classiﬁcation(2010) 65F10 65F08 65N22 65J20

1. Introduction

The Kaczmarz method is one of the most popular iterative methods for image reconstruction in com-

puterized tomography. It was proposed by the Polish mathematician Stefan Kaczmarz in [1, 2]. For the

linear system with equations

Ax =b, (1)

where A= (aij )∈Rm×nand b∈Rm, and xis an unknown vector. We denote the true solution with x∗

when (1) is consistent. However, the linear problem (1) may have no solution or multiple solutions, hence

we are often asked to solve the minimum norm least-squares solution (i.e., Moore-Penrose generalized

solution [3]) x†.

Let A= (a1, a2,...,am)Tand b= (b1,...,bm)T, then the classical form of Kaczmarz’s algorithm

[1, 4] is described as

xk=xk−1+bi− hai, xk−1i

kaik2

ai, k = 1,2,..., (2)

and the matrix-vector form is as follows,

xk= (I−aiaT

kaik2

)xk−1+bi

kaik2

ai, k = 1,2,..., (3)

∗Chuan-gang Kang

Email address: ckangtj@tiangong.edu.cn (Chuan-gang Kang)

Preprint submitted to Journal of L

X Templates October 7, 2022

where i= (kmod m) + 1,hx, yi=xTyand kxk2=phx, xidenote the inner product and the square

norm in Rn, respectively. The iterative scheme of Kaczmarz’s algorithm (2) (or (3)) sweeps through the

equations of Ax =bin a cyclic manner. In the ﬁrst epoch, the processes of projecting the iterate xk−1

orthogonally onto the solution hyperplane hak, xi=bkand getting the new iterate xkare executed from

k= 1 until k=m. When k≥m, then take x0=xmand repeat the above process.

Kaczmarz’s algorithm was unknown for more than 10 years after it was proposed [5, 6, 7]. Until

1970, it was rediscovered as an algebraic reconstruction technique (ART) in computed tomography in [8].

Thereafter, K. Tanabe considered the Kaczmarz method in [9] and investigated the convergence theory.

He proved that the sequence of vectors generated by Kaczmarz’s algorithm converges to the superposition

of the Moore-Penrose solution and the orthogonal projection of the initial vector x0onto the null space

N(A).

T. Strohmer and R. Vershynin considered the randomized Kaczmarz method for the consistent and

inconsistent linear systems and established the results of the exponential convergence rate in [10]. In 2014,

D. Needell and J. A. Tropp considered block Kaczmarz’s algorithm [11] that used a random manner to

pick up the projective subspace {x|Aτx=bτ}at each step, where τ∈T={τ1,...,τr}is a partition of

the row indices of A.

Y. Jiao, B. Jin and X. Lu considered the preasymptotic convergence behavior of the randomized

Kaczmarz method in [12] and illustrated its fast empirical convergence by analyzing the properties of the

high- and low- frequency iterative errors.

K. Wei used the Kaczmarz method to solve systems of phaseless equation in [13], i.e., the generalized

phase retrieval problem. He extended the Kaczmarz method for solving systems of linear equations by

integrating a phase selection heuristic in each iteration. The preliminary convergence analysis has been

presented for the randomized Kaczmarz methods.

C. Kang and H. Zhou considered the convergence of the Kaczmarz method [14] and presented the

convergence rate of the method for solving the exact and inexact linear systems based on the convergence

theory in [9].

For further description, the following symbols will be used in this paper. The null and range spaces

of Awill be denoted by N(A)and R(A), respectively. The rank of Awill be denoted by rank(A).S⊥

will denote the orthogonal complement of a linear subspace S. The Moore-Penrose generalized inverse

[15] of Awill be denoted by A†. The symbol Iwill denote identity matrix of whatever size appropriate

to the context. The transposition of a matrix or vector Xwill be denoted by XT.kAk2denotes the

spectral norm of a matrix Aand is deﬁned by

kAk2= sup

x∈Rn\{0}

kAxk2

kxk2

Denote

AS= (Q1a1, Q2a2,...,Qmam)T, M =diag(1/ka1k2

2,1/ka2k2

2,...,1/kamk2

2),(4)

where,

Qj=PmPm−1...Pj+1 (j= 1,2,...,m−1), Qm=I, Pi=I−aiaT

kaik2

(i= 1,2,...,m).(5)

Some of these mathematical symbols were introduced by Tanabe in [9], so we try to quote these symbols

in order to maintain their consistency, but there are still some diﬀerence, such as Qi(i= 1,2,...,m)

deﬁned in (5), and Qdeﬁned as follows

Q=PmPm−1...P1.(6)

K. Tanabe introduced the following results in [9] and they are also valid for matrix Qdeﬁned in (6).

Lemma 1.1. Qx =xiﬀ x∈N(A).

Lemma 1.2. kQk2≤1. If rank(A)< n then kQk2= 1.

Theorem 1.3. k˜

Qk2= sup

x∈R(AT),kxk2=1

kQxk2<1, where ˜

Q=QPR(AT)and PR(AT)denotes the orthog-

onal projection onto the range space R(AT).

Proposition 1.4. I−AT

SMA =Q.

Proof. According to the deﬁnition of symbols (4) and (5), we have

Q=Pm...P1=Q1−Q1

a1aT

ka1k2

=...=Qm−Qm

amaT

kamk2

−...−Q1

a1aT

ka1k2

=I−(Q1a1, Q2a2,...,Qmam)diag(1/ka1k2

2,1/ka2k2

2,...,1/kamk2

2)(a1, a2,...,am)T

=I−AT

SMA.

Proposition 1.4 was ﬁrst introduced by K. Tanabe in 1971, and we redescribe the result because the

deﬁnition of Qihere is somewhat diﬀerent. The following theorem is derived from Theorem 8.1 in [9].

Theorem 1.5. (I−˜

Q)−1AT

SM=A†, where ˜

Qis deﬁned in Theorem 1.3.

C. Kang and H. Zhou introduced the set-property (Lemma 1.6) and the convergence rate (Theorem

1.7) for the sequence of vectors {xk}generated by Kaczmarz’s iteration (2) in [14].

Lemma 1.6. For any x0∈Rn, let Dr=PN(A)x0+N(A)⊥, then for the sequence of vectors {xk}

generated by Kaczmarz’s iteration (2) (or (3)), there hold xk∈Dr, k = 1,2,....

Theorem 1.7. Assume that (1) is consistent and the sequence of vectors {xk}m

k=1 is generated by

Kaczmarz’s iteration (2). Then for any initial vector x0∈Rn, there holds

kxk+1 −PN(A)x0−x†k2

2≤(1 −1

kak+1k2

2k(aT

k+1Pk+1)†k2

)kxk−PN(A)x0−x†k2

where k(aT

k+1Pk+1)†k2≥ kA†k2.

Theorem 1.7 was obtained based on Kaczmarz’s iteration (2), and the coeﬃcient factors on the right-

hand side of the inequality are not easy to quantify. The iteration number of the Kaczmarz method is

usually a integer multiple of the number of equations in order to make each equation work in the iterative

algorithm. This feature allows us to extract a subsequence {yk}={xkm}from the sequence of vectors

{xk}and make it as a new iterative sequence.

Compared with the original sequence, the new iteration can be generated by the multiplication of

matrix and vector and was named the Kaczmarz-Tanabe iteration in [5]. The iterative scheme is described

as follows,

yk+1 = (I−AT

SMA)yk+AT

SMb, k = 0,1,2,.... (7)

In this paper, we consider the new iterative formula (7) of the Kaczmarz method to improve these

convergence rate results in [14]. The whole linear system are used in each iteration, therefore we can use

the characteristic information about Asuch as the condition number and the singular values, which can

eﬀectively avoid the diﬃculty to quantity the characteristic information of a standalone equation.

Our work is organized as follows. In Section 2, we present the explicit form of the Kaczmarz-Tanabe

method and consider its convergence and convergence rate for the exact linear system. In Section 3,

we consider the convergence rate of the Kaczmarz-Tanabe method for the linear system with perturbed

right-hand side. In Section 4, we present an sub-optimal algorithm, which can save much computational

cost in forming ASand Q. In Section 5, we present some numerical tests to verify these theoretical results

about convergence and convergence rate. Section 6 is the conclusion of this paper.

2. The convergence rate of the Kaczmarz-Tanabe method for an exact linear system

From Proposition 1.4, the iterative formula (7) can also be described as

yk+1 =Qyk+AT

SMb, k = 0,1,2,.... (8)

Obviously, there hold the following equalities,

(I−AT

SMA)PN(A)yδ

0=PN(A)yδ

0,(I−AT

SMA)x†=x†−AT

SMb. (9)

Let ek=yk−PN(A)y0−x†and rk+1 =b−Ayk+1, then for any k≥0there hold

ek+1 = (I−AT

SMA)ek(10)

and

rk+1 = (I−AAT

SM)rk.(11)

Lemma 2.1. if x∈N(A), then Qix=xand QT

ix=x,i= 1,2,...,m.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.02602v1[math.NA]5Oct2022ConvergenceratesoftheKaczmarz-TanabemethodforlinearsystemsChuan-gangKanga,∗aSchoolofMathematicalSciences,TiangongUniversity,Tianjin300387,PeoplesRChinaAbstractInthispaper,weinvestigatetheKaczmarz-Tanabemethodforexactandinexactlinearsystems.TheKaczmarz-Tanabemethodi...

展开>> 收起<<

Convergence rates of the Kaczmarz-Tanabe method for linear systems.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Convergence rates of the Kaczmarz-Tanabe method for linear systems

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: