The standard form and convergence theory of the relaxation Kaczmarz-Tanabe method for solving linear systems

In medical imaging tomography (see, i.e., [1, 2, 3]) such as computerized tomography (CT), magnetic resonance imaging (MRI) and electrical impedance tomography (EIT), people are often required to solve the following linear system of equations [4, 5, 6],

$\displaystyle Ax=b,$

(1.1)

where $A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^{m}$ are also called projection matrix and measurement vector, respectively. We suppose that (1.1) is over-determined and consistent, and $x^{*}$ is a true solution. When (1.1) has many solutions, $x^{\dagger}$ is used to denote the minimum least-squares solution.

The Kaczmarz method [7] is one of the most popular methods to solve (1.1) in computerized tomography. Let $A=(a_{1},a_{2},\ldots,a_{m})^{T}$, Kaczmarz’s iteration is written as

$\displaystyle x_{k}=x_{k-1}+\frac{b_{i}-\langle a_{i},x_{k-1}\rangle}{\|a_{i}\|_{2}^{2}}a_{i},\quad k=1,2,\ldots,$

(1.2)

where $i=\bmod(k-1,m)+1$, $\langle x,y\rangle=x^{T}y$ and $\|x\|_{2}=\sqrt{\langle x,x\rangle}$ denote the inner product of $x,y$ and the square norm of $x$ in $\mathbb{R}^{n}$, respectively.

The Kaczmarz method was originally discovered by Kaczmarz in 1937, and it was rediscovered by Gordon, Bender and Herman [8] to deal with X-ray photography as an algebraic reconstruction technique (ART) in 1970. The convergence of the Kaczmarz method was established by Tanabe in 1971. Recently, Kang and Zhou gave the convergence rate results of the Kaczmarz method [9]. In order to improve computing speed, Eggermont [10], Censor [11], et al. considered the problem of block calculation and adopted approximate and executable iterative forms of the block Kaczmarz method to solve this problem. The strictly block Kaczmarz method was given by Rebrova and Needell [12]. In addition, the simultaneous iterative reconstructive technique (SIRT) as another important branch is also developed rapidly, and there appeared many known methods) such as Cimmino method[13], Landweber method [14], CAV method [15], DROP method [16], and SART method[17], etc.

With the development of hardware technology and computing technology, the idea of stochastic theory is continuously integrated into the non-randomized methods. In this context, people introduced and investigated the randomized Kaczmarz method [18, 19, 20, 21, 22] and greedy randomized Kaczmarz methods [23, 24].

From the perspective of SIRT methods, Kang [25] considered the matrix-vector form of the Kaczmarz method, i.e., the Kaczmarz-Tanabe’s iteration which is named by Popa [26], and the iteration reads

$\displaystyle y_{k+1}=(I-A_{\mathcal{S}}^{T}MA)y_{k}+A_{\mathcal{S}}^{T}Mb,\qquad k=0,1,2,\ldots,$

(1.3)

where $I$ denotes identity matrix of whatever size appropriate to the context, and

	$\displaystyle P_{i}=I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}},\quad Q_{m}=I,Q_{j}=P_{m}P_{m-1}\ldots P_{j+1},\quad Q=P_{m}P_{m-1}\cdots P_{1},$
	$\displaystyle M=\text{diag}(1/\|a_{1}\|_{2}^{2},1/\|a_{2}\|_{2}^{2},\ldots,1/\|a_{m}\|_{2}^{2}),\quad A_{\mathcal{S}}=(Q_{1}a_{1},Q_{2}a_{2},\ldots,Q_{m}a_{m})^{T}.$

Compared with the classic form of the Kaczmarz-Tanabe iteration, the iteration (1.3) has been greatly improved. However, each column of $A_{\mathcal{S}}$ is the product of matrix $Q_{i}$ and column vector $a_{i}$ from $A$. Notice this defect of $A_{\mathcal{S}}$, Kang [27] considered the decomposition of $A_{\mathcal{S}}$ and gave the standard form of the Kaczmarz-Tanabe’s iteration, i.e.,

$\displaystyle y_{k+1}=y_{k}+A^{T}C^{T}M(b-Ay_{k}),\qquad k=0,1,2,\ldots,$

(1.4)

where $C$ is defined as [27, Corollary 2.7]. The iterative scheme (1.4) has no essential difference from the iterative formula of the SIRT methods.

In this paper, we combine the relaxation Kaczmarz method and the Kaczmarz-Tanabe method, and introduce relaxation parameters into Kaczmarz-Tanabe method and propose the relaxation Kaczmarz-Tanabe method. Just as the convergence of the relaxation method is related to the relaxation parameters, the convergence of the relaxation Kaczmarz-Tanabe is also related to the relaxation parameters. Hence we further consider the convergence conditions (about the relaxation parameters) and convergence results of the relaxation Kaczmarz-Tanabe method.

The rest of this work is organized as follows. In Section 2, we consider the relaxation Kaczmarz method and derive the sufficient conditions for its convergence. In Section 3, we consider the standard form of the relaxation Kaczmarz-Tanabe method, and discuss their properties such as decomposition of $A_{\mathcal{S}}({\bf u})$, convergence condition, convergence, and so on. Section 4 is about the algorithm flow to compute $C({\bf u})$ appearing in (3.19) and (3.24). In Section LABEL:section.numerical.tests, we verify the effectiveness of the Kaczmarz-Tanabe method with given relaxation parameters by several classical numerical examples.

The relaxation Kaczmarz’s iteration is written as

$\displaystyle x_{k}=x_{k-1}+\mu_{i}\frac{b_{i}-\langle a_{i},x_{k-1}\rangle}{\|a_{i}\|_{2}^{2}}a_{i},\quad k=1,2,\ldots,$

(2.1)

where $i=\bmod(k-1,m)+1$ and $\mu_{i}$ are relaxation parameters. Let

$\displaystyle P_{i}(\mu_{i})=I-\mu_{i}\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}},\quad i=1,2,\ldots,m,$

(2.2)

then it follows from (2.1) that

$\displaystyle x_{k}=P_{i}(\mu_{i})x_{k-1}+\mu_{i}\frac{b_{i}}{\|a_{i}\|_{2}^{2}}a_{i},\quad k=1,2,\ldots.$

(2.3)

Denote

$\displaystyle P_{i}(\mu):=I-\mu a_{i}a_{i}^{T}/\|a_{i}\|_{2}^{2},$

(2.4)

then the following lemma gives a sufficient condition for the nonexpansion of linear operator $P_{i}(\mu)$.

Let $\{x_{k},k>0\}$ be generated by (2.1) and $e_{k}=x_{k}-P_{N(A)}x_{0}-x^{\dagger}$, thus

$\displaystyle e_{k}=(I-\mu_{i}\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}})e_{k-1}=P_{i}(\mu_{i})e_{k-1},$

(2.6)

where $i=\bmod(k-1,m)+1$, and we have the following set property.

Lemma 2.2 shows that, for any relaxation parameter $\mu_{i}$, the iterative error $\{e_{k},k\geq 0\}$ of the relaxation Kaczmarz method belong to $N(A)^{\bot}$. The following theorem gives the convergence result of the relaxation Kaczmarz method for solving a consistent linear system when $0<\mu_{i}<2$ (where $i=1,2,\ldots,m$).

We start with the first equation of (1.1) and perform the iteration (2.3) in turn until the $m$-th equation, and denote the $m$-th iteration with $x_{m}$, then get

	$\displaystyle x_{m}$	$\displaystyle=P_{m}(\mu_{m})\cdots P_{1}(\mu_{1})x_{0}$
		$\displaystyle\quad+\mu_{1}P_{m}(\mu_{m})\cdots P_{2}(\mu_{2})\frac{b_{1}}{\|a_{1}\|_{2}^{2}}a_{1}+\mu_{2}P_{m}(\mu_{m})\cdots P_{3}(\mu_{3})\frac{b_{2}}{\|a_{2}\|_{2}^{2}}a_{2}+\cdots+\mu_{m}\frac{b_{m}}{\|a_{m}\|_{2}^{2}}a_{m}.$		(3.1)

For $1\leq j\leq m-1$, let

	$\displaystyle{\bf u}:=(\mu_{1},\ldots,\mu_{m}),\quad{\bf u}_{j}:=(\mu_{j+1},\ldots,\mu_{m}),$		(3.2)
	$\displaystyle Q({\bf u}):=P_{m}(\mu_{m})\cdots P_{1}(\mu_{1}),\quad Q_{j}({\bf u}_{j}):=P_{m}(\mu_{m})\cdots P_{j+1}(\mu_{j+1}).$		(3.3)

If $\mu_{i}\equiv 1$ for each $1\leq i\leq m$, then $Q({\bf u})=Q,Q({\bf u}_{j})=Q_{j}$. In addition, we agree that $Q_{m}({\bf u}_{m})=I$, where $I$ denote identity matrix of whatever size appropriate to the context.

Let

$\displaystyle A_{\mathcal{S}}({\bf u})\triangleq(Q_{1}({\bf u}_{1})a_{1},Q_{2}({\bf u}_{2})a_{2},\ldots,Q_{m}({\bf u}_{m})a_{m}\big{)}^{T},\quad\Lambda=\mathbf{diag}(\mu_{1},\ldots,\mu_{m}).$

(3.4)

Thus we get from (3), (3.2), (3.3) and (3.4) that

$\displaystyle x_{m}=Q({\bf u})x_{0}+[A_{\mathcal{S}}({\bf u})]^{T}\Lambda Mb.$

Consequently, it follows by repeating this iteration that

$\displaystyle x_{k\cdot m}=Q({\bf u})x_{(k-1)\cdot m}+[A_{\mathcal{S}}({\bf u})]^{T}\Lambda Mb,\quad k=1,2,\ldots.$

(3.5)

Taking $y_{k}=x_{k\cdot m}$, then we get the relaxation Kaczmarz-Tanabe’s iteration

$\displaystyle y_{k}=Q({\bf u})y_{k-1}+[A_{\mathcal{S}}({\bf u})]^{T}\Lambda Mb,\quad k=1,2,\ldots,$

(3.6)

where $y_{0}=x_{0}$.

By Lemma 3.1, we can get the alternative form of (3.6), i.e.,

$\displaystyle y_{k}=y_{k-1}+[A_{\mathcal{S}}({\bf u})]^{T}\Lambda M(b-Ay_{k-1}),\quad k=1,2,\ldots.$

For the further discussion to (3.6), we extend the conceptions of sequential projection matrix, sequential projection matrix set and sequential compatible to $Q_{j}({\bf u}_{j})$ (see [27, Definition 2.1 & Definition 2.2]).

Second, we suppose (3.10) holds for any given $(i,j)$ subjected to $s\leq i<m$ and $s\leq t<j<m$, i.e., there exists $(\zeta_{1}^{(i,j)}({\bf u}_{j}),\ldots,\zeta_{m}^{(i,j)}({\bf u}_{j}))$ such that

$\displaystyle a_{i}^{T}[Q_{j}({\bf u}_{j})]^{T}=\zeta_{1}^{(i,j)}({\bf u}_{j})a_{1}^{T}+\ldots\zeta_{m}^{(i,j)}({\bf u}_{j})a_{m}^{T}.$

Then, we prove (3.10) holds for $(i,j)=(s,t)$. Because of $Q_{t}({\bf u}_{t})=Q_{t+1}({\bf u}_{t+1})P_{t+1}(\mu_{t+1})$, then

$\displaystyle a_{s}^{T}[Q_{t}({\bf u}_{t})]^{T}=a_{s}^{T}[P_{t+1}(\mu_{t+1})]^{T}[Q_{t+1}({\bf u}_{t+1})]^{T}=a_{s}^{T}[Q_{t+1}({\bf u}_{t+1})]^{T}-\mu_{t+1}\frac{a_{s}^{T}a_{t+1}}{\|a_{t+1}\|_{2}^{2}}a_{t+1}^{T}[Q_{t+1}({\bf u}_{t+1})]^{T}.$

(3.11)

From the hypothesis, there exist $(\zeta_{1}^{(s,t+1)}({\bf u}_{t+1}),\ldots,\zeta_{m}^{(s,t+1)}({\bf u}_{t+1}))$ and $(\zeta_{1}^{(t+1,t+1)}({\bf u}_{t+1}),\ldots,\zeta_{m}^{(t+1,t+1)}({\bf u}_{t+1}))$ such that

	$\displaystyle a_{s}^{T}[Q_{t+1}({\bf u}_{t+1})]^{T}=\zeta_{1}^{(s,t+1)}({\bf u}_{t+1})a_{1}^{T}+\ldots+\zeta_{m}^{(s,t+1)}({\bf u}_{t+1})a_{m}^{T},$
	$\displaystyle a_{t+1}^{T}[Q_{t+1}({\bf u}_{t+1})]^{T}=\zeta_{1}^{(t+1,t+1)}({\bf u}_{t+1})a_{1}^{T}+\ldots+\zeta_{m}^{(t+1,t+1)}({\bf u}_{t+1})a_{m}^{T}.$

Then, it follows from (3.11) that

	$\displaystyle a_{s}^{T}[Q_{t}({\bf u}_{t})]^{T}$
	$\displaystyle=\zeta_{1}^{(s,t+1)}({\bf u}_{t+1})a_{1}^{T}+\ldots+\zeta_{m}^{(s,t+1)}({\bf u}_{t+1})a_{m}^{T}-\frac{a_{s}^{T}a_{t+1}}{\|a_{t+1}\|_{2}^{2}}\big{(}\zeta_{1}^{(t+1,t+1)}({\bf u}_{t+1})a_{1}^{T}+\ldots+\zeta_{m}^{(t+1,t+1)}({\bf u}_{t+1})a_{m}^{T}\big{)}$
	$\displaystyle=\big{(}\zeta_{1}^{(s,t+1)}({\bf u}_{t+1})-\frac{a_{s}^{T}a_{t+1}}{\|a_{t+1}\|_{2}^{2}}\zeta_{1}^{(t+1,t+1)}({\bf u}_{t+1})\big{)}a_{1}^{T}+\ldots+\big{(}\zeta_{m}^{(s,t+1)}({\bf u}_{t+1})-\frac{a_{s}^{T}a_{t+1}}{\|a_{t+1}\|_{2}^{2}}\zeta_{m}^{(t+1,t+1)}({\bf u}_{t+1})\big{)}a_{m}^{T}.$

Denote

	$\displaystyle\big{(}\zeta_{1}^{(s,t)}({\bf u}_{t}),\ldots,\zeta_{m}^{(s,t)}({\bf u}_{t})\big{)}$
	$\displaystyle=\big{(}\zeta_{1}^{(s,t+1)}({\bf u}_{t+1})-\frac{a_{s}^{T}a_{t+1}}{\|a_{t+1}\|_{2}^{2}}\zeta_{1}^{(t+1,t+1)}({\bf u}_{t+1}),\ldots,\zeta_{m}^{(s,t+1)}({\bf u}_{t+1})-\frac{a_{s}^{T}a_{t+1}}{\|a_{t+1}\|_{2}^{2}}\zeta_{m}^{(t+1,t+1)}({\bf u}_{t+1})\big{)}.$

This proves (3.10) holds for $(i,j)=(s,t)$.

To sum up the above, the conclusion is proved for all $(i,j)$ with respect to $1\leq i\leq m,i\leq j\leq m$. Namely, $A$ and $S_{sp}(a_{1},a_{2},\ldots,a_{m};{\bf u})$ generated by relaxation Kaczmarz’s iteration are forward sequential compatible. ∎

In order to obtain the standard form (i.e., matrix-vector form) of the relaxation Kaczmarz-Tanabe’s iteration, we first import the following decomposition theorem about $A_{\mathcal{S}}({\bf u})$.

Theorem 3.5 is a general result, but it shows that there exists a structure-reserved decomposition in relaxation Kaczmarz-Tanabe’s iteration when a relaxation parameter is introduced into Kaczmarz’s iteration. However, the decomposition is not unique when $A$ is not row full rank.

By Theorem 3.5, then we get the standard form of the relaxation Kaczmarz-Tanabe’s iteration from (3.6) that

$\displaystyle y_{k}=y_{k-1}+A^{T}[C({\bf u})]^{T}\Lambda M(b-Ay_{k-1}),\quad k=1,2,\ldots.$

(3.12)

In order to get the special form of $C$ in Kaczmarz-Tanabe’s iteration, Kang introduced the concept of index set $I_{d}(n_{1},n_{2},v)$ in [27, Definition 2.9], i.e.,

By Definition 3.6, we can give the following expression of $a_{i}^{T}[Q_{i}({\bf u}_{i})]^{T}\tilde{x}$ for any $1\leq i\leq m$ and $\tilde{x}\in N(A)^{\bot}$.