2cm2cm2.54cm2cm

# Error estimates of Kaczmarz and randomized Kaczmarz methods

Chuan-gang Kang Corresponding author.
E-mail address: ckangtj@tjpu.edu.cn(C.-g. Kang) School of Mathematical
Sciences, Tian Jin polytechnic University,Tian Jin 300387, China  Heng Zhou
School of Mathematical Sciences, Tian Jin polytechnic University,Tian Jin
300387, China

Abstract: The Kaczmarz method is an iterative projection scheme for solving
consistent system $Ax=b$. It is later extended to the inconsistent and ill-
posed linear problems. But the classical Kaczmarz method is sensitive to the
correlation of the adjacent equations. In order to reduce the impact of
correlation on the convergence rate, the randomized Kaczmarz method and
randomized block Kaczmarz method are proposed, respectively. In the current
literature, the error estimate results of these methods are established based
on the error $\|x_{k}-x_{*}\|_{2}$, where $x_{*}$ is the solution of linear
system $Ax=b$. In this paper, we extend the present error estimates of the
Kaczmarz and randomized Kaczmarz methods on the basis of the convergence
theorem of Kunio Tanabe, and obtain some general results about the error
$\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}$.

Key Words: Kaczmarz method, randomized Kaczmarz method, error estimates,
convergent rate.

2010 Mathematics Subject Classification: 65F10,65F08,65N22,65J20

##  1 Introduction

Kaczmarz method is a popular iterative method for solving linear systems. It
was originally discovered by Kaczmarz in 1937. In 1970, it was rediscovered by
Gordon, Bender and Herman[7] to deal with the computed tomography (CT). In the
early stage of CT development, the computed techniques are dominated by back
projection(BP)[14] and filtered back projection(FBP)[3, 20] techniques because
of the hardware constraints. With the development of hardware techniques,
Kaczmarz method was widely used in CT reconstruction[25, 16] for its
outstanding properties, such as anti-interference and image reconstruction
ability from the incomplete data[10, 11, 22, 2]

In 1971, Kunio Tanabe established the convergence theory[27] of Kaczmarz
method for solving consistent linear systems and employed this method to solve
the generalized inverse of singular matrices. Moreover, he verified that
Kaczmarz method works well for both singular and non-singular systems.

But the issue of the convergent rate is very challenging. The convergent rate
of the method depends strongly on the ordering of the equations. Subsequently,
using the rows of matrix $A$ in Kaczmarz method in a random order rather than
original order, which can often substantially improve the convergence, was
proposed as a computed techniques and was named randomized Kaczmarz method[26]
later. The random selection of the rows from coefficient matrix $A$ weaken the
influence of the original order of the equations and are in line with the
actual situation, so randomized Kaczmarz method is appealing for practical
applications.

In 2009, Strohmer and Vershynin established the exponential convergence[23] of
randomized Kaczmarz method (RKM), where the convergent rate depends on a
variant of the condition number, for consistent and inconsistent linear
systems.

In 2014 Needell and Tropp considered a block algorithm[19] that used a
randomized control scheme to choose the subspace at each step. They analyzed
the convergent rate of randomized block Kaczmarz method[19] for overdetermined
least-square problems in that paper and obtained some important and meaningful
results. In 2015, Needell[18] and his collaborators analyzed two block
versions of Kaczmarz method each with a randomised projection, designed to
converge in expecatation to the least squares solution.

For noisy linear systems, Elfing, Hansen and Nikazad proved the semi-
convergent behavior of Kaczmarz method[24] for solving singular linear systems
and ill-posed problems. They illustrated that the Kaczmarz method is semi-
convergent for ill-posed problem. The semi-convergent behavior actually
clarify that Kaczmarz method can be considered as a kind of regularization
method[8, 5, 4]for solving inverse problems or ill-posed problems.

These convergent rate results do not fully explain the excellent empirical
performance of randomized Kaczmarz method for solving linear inverse problems,
especially in the case of noisy data. In fact, these convergent rate more
reflect the change of the error with noise-free term rather than the
perturbance, i.e., the decrease of the iterative error has nothing to do with
the perturbed term.

Yuling Jiao, Bangti Jin and Xiliang Lu considered the relationship between the
iterative error and perturbed term by splitting the iterative error into high-
frequency error and low-frequency error[12]. They discovered the change
process of high- and low-frequency error.

Most of the present literature about convergent rate depend on the hypothesis
that $A$ has full column rank or $Ax=b$ is consistent. Few literature
considered the least square problems but they assume that $Ax=b$ has a unique
solution, so they could not consider fully the property of generalized
solution. Furthermore, the current literature ignore the influence of the
inial value $x_{0}$ or simply make $x_{0}=0$.

Although $x_{0}$ can be fixed as zero, the reasonable case is that $x_{0}$ is
arbitrarily chosen. In this paper, inspired by the opinion of some literatures
[27, 12, 15, 18], we consider the convergent rate of Kaczmarz method,
randomized Kaczmarz method and randomized block Kaczmarz method, and establish
the convergent rate results on the basis of
$\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}$.

The rest of the paper is organized as follows. In section 2, we analyze the
convergent rate of randomized Kaczmarz and classical Kaczmarz method, and
illustrate the convergent behavior of these methods. Then in section 3, on the
basis of block division $S=S_{1}\bigcup S_{2}\bigcup\cdots\bigcup S_{r}$ about
index set $S=\\{1,2,\cdots,m\\}$, we propose a randomized Kaczmarz method and
analyze its convergent rate. Last, In section 4, we illustrate the convergent
behavior through several classical numerical experiments.

##  2 Kaczmarz and randomized Kaczmarz methods

In this paper, the solution of the linear equations

$\displaystyle Ax=b$ (2.1)

are considered, where $A=(a_{ij})$ is an $m\times n$ complex matrix, $x$ and
$b$ are $n-$ and $m-$dimension complex column vectors, respectively. we shall
denote by $a_{i}=(a_{i1},\cdots,a_{in})^{T},i=1,2,\cdots,m$ and $b_{i}$ the
$i$-th row of $A$ and the $i$-th component of the vector $b$, respectively. We
shall suppose that $a_{i}\neq 0,i=1,2,\cdots,m$.

In perturbed case, the right-hand side of (2.1) is $b^{\delta}$, where
$\|b^{\delta}-b\|_{2}\leq\delta$. The solution of (2.1) may or may not exist,
furthermore, the least square solution may not be unique.

The classical Kaczmarz method[13] can be described as

$\displaystyle
x_{k}=x_{k-1}+\frac{b_{i}-(a_{i},x_{k-1})}{\|a_{i}\|_{2}^{2}}a_{i},k=1,2,\cdots,$
(2.2a) or $\displaystyle
x_{k}=(I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}})x_{k-1}+\frac{b_{i}}{\|a_{i}\|_{2}^{2}},k=1,2,\cdots,$
(2.2b)

where $i=(k\bmod m)+1$.

The randomized Kaczmard method[26, 16] can be described as

$\displaystyle
x_{k}=x_{k-1}+\frac{b_{i}-(a_{i},x_{k-1})}{\|a_{i}\|_{2}^{2}}a_{i},k=1,2,\cdots,$
(2.3)

where $i$ is chosen in the set $\\{1,2,\cdots,n\\}$ by the probability
$p_{r}=\frac{\|a_{i}\|_{2}^{2}}{\|A\|_{F}^{2}}$.

The convergence of Kaczmarz method was obtained by Tanabe[27] as the following
theorem.

######  Theorem 2.1.

For any $m\times n$ matrix $A$ with nonzero rows and any $m$-dimensional
column vector $b$, the algorithm (2.2a) generates a convergent sequence of
vectors such that

$\displaystyle\lim\limits_{x\rightarrow\infty}x_{k}=P_{N(A)}x_{0}+Gb.$ (2.4)

where $x_{0}\in\mathcal{R}^{n}$ is an arbitrary initial vector.

In (2.2b), if let

$\displaystyle
P_{i}=I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}},~{}~{}~{}~{}~{}~{}i=1,2,\cdots,m$

and

$\displaystyle Q_{i}=P_{1}P_{2}\cdots P_{i},~{}~{}~{}~{}~{}~{}i=1,2,\cdots,m,$

where $Q_{0}=I,Q=Q_{m}$, and denote

$\displaystyle
R=(\frac{Q_{0}a_{1}}{\|a_{1}\|_{2}^{2}},\frac{Q_{1}a_{2}}{\|a_{2}\|_{2}^{2}},\cdots,\frac{Q_{m-1}a_{m}}{\|a_{m}\|_{2}^{2}}).$

Thereby, the operator $G$ in (2.4) can be described as

$\displaystyle G=(I-\widetilde{Q})^{-1}R=\sum\limits_{j=0}^{\infty}Q^{j}R.$

In 2015, Kang and Zhou[6] analyzed the generalized inverse property of
operator $G$ and proved that $Gb$ is not only the least square solution but
also the minimal norm solution, i.e. $Gb$ is the Moore-Penrose generalized
solution of $Ax=b$.

The convergent rate analysis in the following of this paper is mostly on the
basis of this theorem.

The following theorem summarizes typical convergence results of randomized
Kaczmarz method for consistent and inconsistent linear systems[17, 23, 28,
12].

######  Theorem 2.2.

Let $x_{k}$ be the solution generated by RKM at iteration $k$. and
$\kappa_{A}=\|A\|_{F}^{2}\|A^{\dagger}\|_{2}$ be a (generalized) condition
number. Then the following statements hold.

(i) For exact data, there holds

$\displaystyle
E\left[\|x_{k}-x^{*}\|_{2}^{2}\right]\leq(1-\kappa_{A}^{-2})^{k}\|x_{0}-x^{*}\|_{2}^{2}.$
(2.5)

(ii) For noisy data, there holds

$\displaystyle
E\left[\|x_{k}-x^{*}\|_{2}^{2}\right]\leq(1-\kappa_{A}^{-2})^{k}\|x_{0}-x^{*}\|_{2}^{2}+\frac{\delta^{2}}{\sigma_{\min}^{2}(A)}.$
(2.6)

where $x^{*}$ is a solution of the consistent system $Ax=b$.

In [17, 23, 28], The error estimate about $\|x_{k+1}-x^{*}\|_{2}$ was
considered for consistent system or some inconsistent system. For any initial
vector $x_{0}$, Kunio Tanabe has proved that the limit of Kacmarz method is
$P_{N(A)}x_{0}+Gb$ for consistent linear system, where $Gb$ has been proved to
be a Moore-Penrose generalized solution [1, 6, 24]. Inspired by them, we will
consider the theory analysis based on the error term
$\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}$ rather than
$\|x_{k+1}-x^{*}\|_{2}$.

For any $x_{0}\in R^{n}$, define manifold $D_{r}=P_{N(A)}x_{0}+N(A)^{\bot}$
and restrict the operator $A$ on the manifold $D_{r}$, that is

$\displaystyle A|_{D_{r}}:P_{N(A)}x_{0}+N(A)^{\bot}\mapsto R(A).$ (2.7)

######  Lemma 2.3.

For any $x_{0}\in R^{n}$, assume $D_{r}=P_{N(A)}x_{0}+N(A)^{\bot}$, then for
the vector sequence $x_{k}$ generated from (2.3), there hold $x_{k}\in
D_{r},k=1,2,\cdots$.

Proof. we prove this lemma with mathematical induction.

First, for any initial vector $x_{0}\in R^{n}$, obviously there has $x_{0}\in
D_{r}$. Next, we will prove $x_{1}\in D_{r}$, from randomized Kaczmarz
iteration (2.3), there is

$\displaystyle
x_{1}=x_{0}+\frac{b_{i}-(a_{i},x_{0})}{\|a_{i}\|_{2}^{2}}x_{i}.$ (2.8)

For any $\tilde{x}\in N(A)$,

$\displaystyle(x_{1}-P_{N(A)}x_{0},\tilde{x})$
$\displaystyle=((I-P_{N(A)})x_{0}+\frac{b_{i}-(a_{i},x_{0})}{\|a_{i}\|_{2}^{2}}a_{i},\tilde{x})$
$\displaystyle=\big{(}(I-P_{N(A)}\big{)}x_{0},\tilde{x})+(\frac{b_{i}-(a_{i},x_{0})}{\|a_{i}\|_{2}^{2}}a_{i},\tilde{x})$
$\displaystyle=\frac{b_{i}-(a_{i},x_{0})}{\|a_{i}\|_{2}^{2}}a_{i}^{T}\tilde{x}=0,$

which shows that $x_{1}=P_{N(A)}x_{0}+N(A)^{T}\in D_{r}$.

Second, suppose $x_{k}\in D_{r}$, we prove $x_{k+1}\in D_{r}$ in the
following. From the hypothesis $\tilde{x}\in N(A)$, so

$\displaystyle(x_{k+1}-P_{N(A)}x_{0},\tilde{x})$
$\displaystyle=(x_{k}-P_{N(A)}x_{0}+\frac{b_{i}-(a_{i},x_{k})}{\|a_{i}\|_{2}^{2}}a_{i},\tilde{x})$
$\displaystyle=(x_{k}-P_{N(A)}x_{0},\tilde{x})+(\frac{b_{i}-(a_{i},x_{k})}{\|a_{i}\|_{2}^{2}}a_{i},\tilde{x}).$
(2.9)

Because of $x_{k}\in D_{r}$ and $\tilde{x}\in N(A)$, there holds
$\left(x_{k}-P_{N(A)}x_{0},\tilde{x}\right)=0$, therefore there has

$\displaystyle(x_{k+1}-P_{N(A)}x_{0},\tilde{x})=(\frac{b_{i}-(a_{i},x_{k})}{\|a_{i}\|_{2}^{2}}a_{i},\tilde{x})=0,$

which shows $x_{k+1}\in D_{r}$.

To sum up, for any $x_{0}\in R^{n}$, the vector sequence
$\\{x_{k}\\}_{k=1}^{\infty}$ generated from randomized Kaczmarz method belong
to the manifold $D_{r}$. $\square$

The Kaczmraz method is an orthogonal projection method, so there holds the
follow lemma.

######  Lemma 2.4.

Let $u,v\in R^{n}$ are arbitrary vectors, then the vector
$(I-\frac{uu^{T}}{\|u\|_{2}^{2}})v$ and $u$ are orthogonal.

Proof.

$\displaystyle\big{(}(I-\frac{uu^{T}}{\|u\|_{2}^{2}})v,u\big{)}=(v,u)-(\frac{uu^{T}}{\|u\|_{2}^{2}}v,u)=(v,u)-(v,\frac{uu^{T}}{\|u\|_{2}^{2}}u)=(v,u)-(v,u)=0.$

######  Theorem 2.5.

For the linear system $Ax=b$, where $A\in R^{m\times n},b\in R^{m}$, Assume
$A^{\dagger}$ is the Moore-Penrose inverse of $A$, $x^{\dagger}$ is the Moore-
Penrose generalized solution of $Ax=b$, $P_{N(A)}:R^{n}\rightarrow N(A)$ and
$Q:R^{m}\rightarrow R(A)$ are orthogonal projection operators,
$\\{x_{k}\\}_{k=1}^{\infty}$ is the vector sequence generalized from
randomized Kaczmarz method (2.3), $\kappa_{A}=\|A\|_{F}\|A^{\dagger}\|_{2}$ is
generalized condition number, then there holds

$\displaystyle
E\big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{]}\leq(1-\frac{1}{\kappa^{2}(A)})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)b\|_{2}^{2}.$
(2.10)

Proof. For any initial vector $x_{0}\in R^{n}$, from Lemma 3 there has
$x_{k}\in D_{r}(k\geq 0)$, thus $x_{k}-P_{N(A)}x_{0}\in N(A)^{\bot}$,
therefore

$\displaystyle x_{k+1}-P_{N(A)}x_{0}$
$\displaystyle=x_{k}-P_{N(A)}x_{0}+\frac{b_{i}-(a_{i},x_{k}-P_{N(A)}x_{0})}{\|a_{i}\|_{2}^{2}}a_{i}$
$\displaystyle=x_{k}-P_{N(A)}x_{0}+\frac{(Qb)_{i}-(a_{i},x_{k}-P_{N(A)}x_{0})}{\|a_{i}\|_{2}^{2}}a_{i}+\frac{b_{i}-(Qb)_{i}}{\|a_{i}\|_{2}^{2}}a_{i}.$
(2.11)

Assume $x^{\dagger}$ is the generalized solution of $Ax=b$, hence

$\displaystyle x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}$
$\displaystyle=x_{k}-P_{N(A)}x_{0}-x^{\dagger}+\frac{(a_{i},x^{\dagger})-(a_{i},x_{k}-P_{N(A)}x_{0})}{\|a_{i}\|_{2}^{2}}a_{i}+\frac{\big{(}(I-Q)b\big{)}_{i}}{\|a_{i}\|_{2}^{2}}a_{i}$
$\displaystyle=x_{k}-P_{N(A)}x_{0}-x^{\dagger}-\frac{(a_{i},x_{k}-P_{N(A)}x_{0}-x^{\dagger})}{\|a_{i}\|_{2}^{2}}a_{i}+\frac{\big{(}(I-Q)b\big{)}_{i}}{\|a_{i}\|_{2}^{2}}a_{i}$
$\displaystyle=(I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}})(x_{k}-P_{N(A)}x_{0}-x^{\dagger})+\frac{\big{(}(I-Q)b{)}_{i}}{\|a_{i}\|_{2}^{2}}a_{i}.$
(2.12)

From Lemma 2.4, there holds

$\displaystyle\big{(}(I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}})(x_{k}-P_{N(A)}x_{0}-x^{\dagger}),\frac{\big{(}(I-Q)b)_{i}}{\|a_{i}\|_{2}^{2}}a_{i}\big{)}=0,$
(2.13)

consequently,

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}=\|(I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}})(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\|\frac{\big{(}(I-Q)b\big{)}_{i}}{\|a_{i}\|_{2}^{2}}a_{i}\|_{2}^{2}.$
(2.14)

In addition,

$\displaystyle\|(I-\frac{a_{i}a_{i}^{T}}{\|a_{i}\|_{2}^{2}})(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\|\frac{a_{i}^{T}}{\|a_{i}\|_{2}}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}.$
(2.15)

From (2.14) and (2.15), there holds

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}=$
$\displaystyle\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\|\frac{a_{i}^{T}}{\|a_{i}\|_{2}}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}$
$\displaystyle+\frac{1}{\|a_{i}\|_{2}^{2}}\big{(}(I-Q)b\big{)}_{i}^{2}.$
(2.16)

Consequently, taking expectation on both sides about index $i$ yields

$\displaystyle
E\Big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{|}x_{k}\Big{]}$
$\displaystyle=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\sum\limits_{i=1}^{m}\frac{\|a_{i}\|_{2}^{2}}{\|A\|_{F}^{2}}\|\frac{a_{i}^{T}}{\|a_{i}\|_{2}}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\sum\limits_{i=1}^{m}\frac{\|a_{i}\|_{2}^{2}}{\|A\|_{F}^{2}}\|\frac{1}{\|a_{i}\|_{2}^{2}}\big{(}(I-Q)b\big{)}_{i}^{2}$
$\displaystyle=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\sum\limits_{i=1}^{m}\frac{\|a_{i}\|_{2}^{2}}{\|A\|_{F}^{2}}\frac{1}{\|a_{i}\|_{2}^{2}}\|a_{i}^{T}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\sum\limits_{i=1}^{m}\frac{1}{\|A\|_{F}^{2}}\big{(}(I-Q)b)_{i}^{2}$
$\displaystyle=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\frac{1}{\|A\|_{F}^{2}}\|A(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)b\|_{2}^{2}.$
(2.17)

Since $x_{k}-P_{N(A)}x_{0}-x^{\dagger}\in N(A)^{\bot}$, there has

$\displaystyle
A^{\dagger}A(x_{k}-P_{N(A)}x_{0}-x^{\dagger})=x_{k}-P_{N(A)}x_{0}-x^{\dagger},$
(2.18)

hence

$\displaystyle\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}=\|A^{\dagger}A(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}\leq\|A^{\dagger}\|_{2}^{2}\|A(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2},$
(2.19)

which yields

$\displaystyle\|A(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}\geq\frac{1}{\|A^{\dagger}\|_{2}^{2}}\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}.$
(2.20)

Substitute (2.20) into (2), there holds

$\displaystyle E\left[\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\right]$
$\displaystyle\leq(1-\frac{1}{\|A\|_{F}^{2}\|A^{\dagger}\|_{2}^{2}})E\left[\|(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}\right]+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)b\|_{2}^{2}$
$\displaystyle\leq(1-\frac{1}{\|A\|_{F}^{2}\|A^{\dagger}\|_{2}^{2}})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)b\|_{2}^{2}.$
(2.21)

Denotes $\kappa_{A}=\|A\|_{F}\|A\|_{2}$ as $\kappa(A)$, then (2) implies
(2.10). $\square$

In (2.10), if $b\in R(A)$, it means $\|(I-Q)b\|_{2}\equiv 0$, then there holds

$\displaystyle E\left[\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\right]$
$\displaystyle\leq(1-\frac{1}{\kappa^{2}(A)})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}.$

As $k\rightarrow\infty$, $1-\frac{1}{\kappa^{2}(A)}$ tends to zero, thus
$\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\rightarrow 0$, i.e.

$\displaystyle x_{k+1}\rightarrow P_{N(A)}x_{0}+x^{\dagger},$

which proves that the vector sequence $\\{x_{k}\\}_{k=1}^{\infty}$ generated
from the randomized Kaczmarz method is convergent when $Ax=b$ is consistent
and the limit is $P_{N(A)}x_{0}+x^{\dagger}$.

In addition, it is easy to see from theorem 2.5 that if $b\notin R(A)$, i.e.
the system $Ax=b$ is inconsistent. The vector sequence generated by randomized
Kaczmarz method is bounded rather than convergent(see [21]).

In fact, Popa pointed out that the (classical) Kaczmarz algorithm with
$x_{0}=0$ generates a sequence ${x_{k}}$ convergent to $x^{\dagger}$ if and
only if the system $Ax=b$ is consistent. The (classic) Kaczmrz and randomized
Kaczmarz method are essentially the same in convergence behavior regardless of
convergent rate. Theorem 2.5 confirms that the Kaczmarz and randomized
Kaczamrz methods for solving the insistent system do not converge to
$x^{\dagger}$ even if $x_{0}=0$.

Unless the above illustrations, error scheme (2.10) can be used to analyze the
perturbation problems when $\|(I-Q)b\|_{2}$ is replaced with
$\|b^{\delta}-b\|_{2}$, where $b^{\delta}$ is the noisy right-hand side of the
consistent system $Ax=b$. Kaczmarz like methods for solving ill-posed problems
have semi-convergent behavior (see [24]), however, Theorem 2.5 show us an
upper bound of $\|x_{k}-P_{N(x)x_{0}}-x^{\dagger}\|_{2}$.

During the performance of randomized Kaczmarz method (2.3), the probability to
choose the $i$th equation is $\frac{\|a_{i}\|_{2}^{2}}{\|A\|_{F}^{2}}$, but in
fact, if the normal vector of every equation is canonical, i.e.
$\|a_{i}\|_{2}=1,i=1,2,\cdots,m$, then the probability in randomized Kaczmarz
method is changed to $\frac{1}{m}$. For general linear system, we can acquire
it by normalizing the coefficient matrix $A$, so the original linear system
$Ax=b$ is equivalent to $DAx=Db$, where
$D=\text{diag}(1/\|a_{1}\|_{2},1/\|a_{2}\|_{2},\cdots,1/\|a_{m}\|_{2})$. From
Theorem 2.2, there holds the next corollary for the normalized linear system.

######  Corollary 2.6.

For linear system $Ax=b$,
$D=\text{diag}(1/\|a_{1}\|_{2},1/\|a_{2}\|_{2},\cdots,1/\|a_{m}\|_{2})$,
$P_{N(A)}:R^{n}\rightarrow N(A)$ and $Q:R^{m}\rightarrow R(A)$ are orthogonal
projection operators, $\\{x_{k}\\}_{k=1}^{\infty}$ is a vector sequence
generated by randomized Kaczmarz method, then there holds
(1) For inconsistent data,

$\displaystyle
E\big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{]}\leq$
$\displaystyle(1-\frac{1}{m\cdot\max\limits_{i=1,\cdots,m}\|a_{i}\|_{2}^{2}\|A^{\dagger}\|_{2}^{2}})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}$
$\displaystyle+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)Db\|_{2}^{2}.$ (2.22)

(2) For consistent data,

$\displaystyle
E\big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{]}\leq(1-\frac{1}{m\cdot\max\limits_{i=1,\cdots,m}\|a_{i}\|_{2}^{2}\|A^{\dagger}\|_{2}^{2}})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}.$
(2.23)

Proof. For linear system $DAx=Db$, from the theorem 2.5, hence

$\displaystyle
E\big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{]}\leq(1-\frac{1}{\|DA\|_{F}^{2}\|(DA)^{\dagger}\|_{2}^{2}})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)b\|_{2}^{2}.$

Note that $\|DA\|_{F}^{2}=m,\|D^{-1}\|_{2}^{2}=\max(\|a_{i}\|_{2}^{2})$,
therefore

$\displaystyle\|DA\|_{F}^{2}\|(DA)^{\dagger}\|_{2}^{2}\leq
m\max\limits_{i}\|a_{i}\|_{2}^{2}\|A^{\dagger}\|_{2}^{2}.$

Consequently,

$\displaystyle
E\big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{]}\leq(1-\frac{1}{m\max\limits_{i=1,\cdots,m}\|a_{i}\|_{2}^{2}\|A^{\dagger}\|_{2}^{2}})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}+\frac{1}{\|A\|_{F}^{2}}\|(I-Q)Db\|_{2}^{2}.$

Furthermore, from $\|A\|_{2}^{2}=\sum\limits_{i=1}^{m}\|a_{i}\|_{2}^{2}\leq
m\max\|a_{i}\|_{2}^{2}$, there holds

$\displaystyle(1-\frac{1}{\|A\|_{F}^{2}\|A^{\dagger}\|_{2}^{2}})\leq(1-\frac{1}{m\max\limits_{i=1,\cdots,m}\|a_{i}\|_{2}^{2}\|A^{\dagger}\|_{2}^{2}}).$
(2.24)

Therefore, the result of the Corollary 2.6 for normal system is slightly
weaker than the result of Theorem 2.5 for general linear system. In fact, the
result can be understood easily, in order to keep the consistency with $Ax=b$,
we hope to express the result with $A$ or some parts of it rather than $DA$,
so it is unavoidable to enlarge appropriately the item
$\|A\|_{F}\|A^{\dagger}\|_{2}$ in (2.10).

For the consistent system, i.e. $(I-Q)b=0$, the inequality (2.6) can be
simplified to (2.23). $\square$

Next, we consider the classical Kaczmarz method, there holds the following
error estimate.

######  Theorem 2.7.

If $Ax=b$ is consistent, denote $N_{k+1}=N(a_{k+1})$. $P_{N(A)}:R^{n}\mapsto
N(A)^{\bot}$ and $P_{k+1}:N(A)^{\bot}\mapsto N_{k+1}^{\bot}$ are orthogonal
projection operators. For any initial vector $x_{0}\in R^{n}$, the vector
consequence $\\{x_{k}\\}_{k=1}^{m}$ generated from Kaczmarz method (2.2a)
satisfies

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\leq(1-\frac{1}{\|a_{k+1}\|_{2}^{2}\|(a_{k+1}^{T}P_{k+1})^{\dagger}\|_{2}^{2}})\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}$
(2.25)

and $\|(a_{k+1}^{T}P_{k+1})^{\dagger}\|_{2}\geq\|A^{\dagger}\|_{2}$.

Proof. In (2), let $i=k+1$. Since $Ax=b$ is consistent, thus $Q=I$, and hence

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}$
$\displaystyle=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\|\frac{a_{k+1}^{T}}{\|a_{k+1}\|_{2}}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}$
$\displaystyle\leq\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\|\frac{a_{k+1}^{T}}{\|a_{k+1}\|_{2}}P_{k+1}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}.$
(2.26)

for $N(A)\subset N_{k+1}$, thus $N_{k+1}^{\bot}\subset N(A)^{\bot}$, from the
condition $P_{k+1}:N(A)^{\bot}\mapsto N_{k+1}^{\bot}$, let
$(a_{k+1}^{T}P_{k+1})^{\dagger}$ be the generalized inverse of
$a_{k+1}^{T}P_{k+1}$, there holds

$\displaystyle\|a_{k+1}^{T}P_{k+1}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}\geq\frac{1}{\|(a_{k+1}^{T}P_{k+1})^{\dagger}\|_{2}^{2}}\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2},$
(2.27)

substitute (2) into (2.27), then there holds

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\leq(1-\frac{1}{\|a_{k+1}\|_{2}^{2}\|(a_{k+1}^{T}P_{k+1})^{\dagger}\|_{2}^{2}})\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2},$
(2.28)

the inequality (2.25) is proved.

In addition,

$\displaystyle\|(a_{k+1}^{T}P_{k+1})^{\dagger}\|_{2}$
$\displaystyle=\sup\limits_{y\in
R(a_{k+1})}\|\frac{(a_{k+1}^{T}P_{k+1})^{\dagger}y\|_{2}}{\|y\|_{2}}=\sup\limits_{x\in
N_{A}^{\bot}}\frac{\|(a_{k+1}^{T}P_{k+1})^{\dagger}a_{k+1}^{T}P_{k+1}x\|_{2}}{\|a_{k+1}^{T}P_{k+1}x\|_{2}}$
$\displaystyle=\sup\limits_{x\in
N_{A}^{\bot}}\frac{\|x\|_{2}}{\|a_{k+1}^{T}P_{k+1}x\|_{2}}=\sup\limits_{x\in
N_{A}^{\bot}}\frac{\|x\|_{2}}{\|a_{k+1}^{T}x\|_{2}}\geq\sup\limits_{x\in
N_{A}^{\bot}}\frac{\|x\|_{2}}{\|Ax\|_{2}}=\|A^{\dagger}\|_{2},$

It is obvious that the above proof about the error estimate for the vector
sequence generated by classical Kaczmarz method is restricted in one recycle
period, i.e. $k=1,2,\cdots,m$, in other word, the index of error is in
accordance with the number of equation. For general case, there holds the
following result.

######  Corollary 2.8.

If $Ax=b$ is consistent, denote $N_{k+1}=\ker(a_{k+1})=N(a_{k+1})$,
$P_{N(A)}:R^{n}\mapsto N(A)^{\bot}$ and $P_{k+1}:N(A)^{\bot}\mapsto
N_{k+1}^{\bot}$ are orthogonal projection operators, for any initial vector
$x_{0}\in R^{n}$, the vector consequence $\\{x_{k}\\}_{k=1}^{\infty}$
generated from Kaczmarz method (2.2a) satisfies

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\leq(1-\frac{1}{\max\limits_{i=1,2,\cdots,m}\|a_{i}\|_{2}^{2}\|(a_{i}^{T}P_{i})^{\dagger}\|_{2}^{2}})^{k+1}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}.$
(2.29)

From Corollary 2.8, as $k\rightarrow\infty$, there holds
$\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}\rightarrow 0$ at once, i.e.,
$x_{k+1}\rightarrow P_{N(A)}x_{0}+x^{\dagger}$ which is in accordance with the
conclusion of Kunio Tanabe in [27].

##  3 Block randomized Kaczmarz method

In this part, we will consider the block randomized Kaczmrz method. Assume the
linear system $Ax=b$, where $A\in R^{m\times n},b\in R^{m}$,
$S=\\{1,2,\cdots,m\\}$ is the identifier set of the equations of the linear
system, divide the set $S=S_{1}\cup S_{2}\cup\cdots\cup S_{r}$, where
$S_{i}\cap S_{j}=\Phi(i,j=1,2,\cdots,r)$, actually, $\\{S_{i}\\}_{i=1}^{r}$ is
a classification set of $S$. the number of the elements in $S_{i}$ is denoted
by $\\#S_{i}$.

Based on the general framework, i.e. without fixing classification set, The
algorithm of the Block randomized Kaczmarz method can be provided in the
following.

Algorithm 1 Block randomized Kaczmarz method

1:Given $A,b,x_{0}$, $S_{1},S_{2},\cdots,S_{r}$, $N$.

2:$k=1$, let $S_{sel}=S_{1}$.

3:perform  $\displaystyle
x_{k}=x_{k-1}+\frac{b_{i}-(a_{i},x_{k-1})}{\|a_{i}\|_{2}^{2}}a_{i},$ (3.1)
where the identifier $i$ is selected by the probability
$P_{r}=\frac{1}{\\#S_{sel}}$ in subset $S_{sel}$.

4:$k=k+1$, if $k<N$, let $l=k\bmod r$, if $l\neq 0$, let $S_{sel}=S_{l}$ and
if $l=0$, let $S_{sel}=S_{r}$, then select one number $i$ in $S_{sel}$ by the
probability $\frac{1}{\\#S_{l}}$ and then go to step 3; otherwise, terminate
the iteration and let $x_{k}$ be the numerical solution.

For block randomized Kaczmarz method, there holds the next theorem.

######  Theorem 3.1.

Assume identifer $i$ is selected in $S_{c}$, where $c$ is a certain value in
set $\\{1,2,\cdots,r\\}$, $P_{i}:N(A)^{\bot}\mapsto N(a_{i})^{\perp}$, then
there holds for the vector sequence $\\{x_{k}\\}_{k=1}^{\infty}$ generated by
Algorithm 1:

(i) For consistent system

$\displaystyle
E\Big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{|}x_{k}\Big{]}\leq(1-\min\limits_{i\in
S_{c}}\frac{1}{\|a_{i}\|_{2}^{2}\|(a_{i}^{T}P_{i})^{\dagger}\|_{2}^{2}})\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}.$
(3.2)

(ii) For inconsistent system

$\displaystyle
E\big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{]}\leq(1-\frac{1}{m\max\limits_{i=1,\cdots,m}\|a_{i}\|_{2}^{2}\|A^{\dagger}\|_{2}^{2}})^{k}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}+\frac{m}{\\#S_{sel}}\frac{\delta^{2}}{\lambda_{\min}^{2}(A)}.$
(3.3)

Proof. From (2)

$\displaystyle\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\|\frac{a_{i}^{T}}{\|a_{i}\|_{2}}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\frac{1}{\|a_{i}\|_{2}^{2}}\big{(}(I-Q)b)_{i}^{2}.$

Taking expectation on both side about $i$ in $S_{c}$ yields

$\displaystyle
E\Big{[}\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}\big{|}x_{k}\Big{]}$
$\displaystyle=\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\frac{1}{\\#S_{c}}\sum\limits_{i=1}^{\\#S_{c}}\|\frac{a_{i}^{T}}{\|a_{i}\|_{2}}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\frac{1}{\\#S_{c}}\sum\limits_{i=1}^{\\#S_{c}}\frac{1}{\|a_{i}\|_{2}^{2}}\big{(}(I-Q)b)_{i}^{2}$
$\displaystyle\leq\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\min\limits_{i\in
S_{c}}\frac{1}{\|a_{i}\|_{2}^{2}}\|a_{i}^{T}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\frac{1}{\\#S_{c}}\frac{1}{\min\limits_{i\in
S_{c}}\|a_{i}\|_{2}^{2}}\|(I-Q)b\|_{2}^{2}$
$\displaystyle\leq\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}-\min\limits_{i\in
S_{c}}\frac{1}{\|a_{i}\|_{2}^{2}}\|a_{i}^{T}P_{i}(x_{k}-P_{N(A)}x_{0}-x^{\dagger})\|_{2}^{2}+\frac{1}{\\#S_{c}}\frac{1}{\min\limits_{i\in
S_{c}}\|a_{i}\|_{2}^{2}}\|(I-Q)b\|_{2}^{2}$
$\displaystyle\leq(1-\min\limits_{i\in
S_{c}}\frac{1}{\|a_{i}\|_{2}^{2}\|(a_{i}^{T}P_{i})^{\dagger}\|_{2}^{2}})\|x_{k}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}+\frac{1}{\\#S_{c}}\frac{1}{\min\limits_{i\in
S_{c}}\|a_{i}\|_{2}^{2}}\|(I-Q)b\|_{2}^{2}.$

The inequality (3.2) is proved. Taking $Qb=b$ will obtain the inequality for
the consistent system.

From Theorem 3.1, the following corollary is obvious.

######  Corollary 3.2.

Assume $Q:R^{m}\rightarrow R(A)$ and $P_{i}:N(A)^{\bot}\mapsto
N(a_{i})^{\bot}$ are orthogonal projection operators, then there hold for the
vector sequence $\\{x_{k}\\}_{k=1}^{\infty}$ generated by Algorithm 1:

(i) For consistent system

$\displaystyle
E[\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}]\leq(1-\min\limits_{i\in
S}\frac{1}{\|a_{i}\|_{2}^{2}\|(a_{i}^{T}P_{i})^{\dagger}\|_{2}^{2}})^{k+1}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}.$
(3.4)

(ii) For inconsistent system

$\displaystyle E[\|x_{k+1}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}]\leq$
$\displaystyle(1-\min\limits_{i\in
S}\frac{1}{\|a_{i}\|_{2}^{2}\|(a_{i}^{T}P_{i})^{\dagger}\|_{2}^{2}})^{k+1}\|x_{0}-P_{N(A)}x_{0}-x^{\dagger}\|_{2}^{2}$
$\displaystyle+\frac{\max\limits_{i\in S}\|a_{i}\|_{2}^{2}}{\min\limits_{i\in
S}\|a_{i}\|_{2}^{2}}\frac{\max\limits_{i\in
S}\|(a_{i}^{T}P_{i})^{\dagger}\|_{2}^{2}}{\min\limits_{c\in\\{1,2,\cdots,r\\}}\\#S_{c}}\|(I-Q)b\|_{2}^{2}.$
(3.5)

when the projection is performed randomly in classification sets
$S_{1},S_{2},\cdots,S_{r}$ from $x_{k}$, the behavior of error for Kaczmarz
method are shown in Theorem 3.1 and the corollary 3.2.

##  4 Numerical experiments

In this section, we will illustrate these error estimate results appeared in
the above sections by several classical problems, i.e. phillips, gravity and
shaw. They are Fredholm integral equations of the first kind, phillips problem
is mildly ill-posed and the others are severely ill-posed. If discretized them
with dimension $m=n=1000$, the condition numbers of them are $2.6415e+10$,
$9.8894e+19$ and $7.1301e+20$, respectively. the codes of discretized problems
are taken from Matlab package Regutools[9]***Available from www.imm.dtu.dk/
pcha/Regutools/.

In the test programs, discretized dimension is fixed to $m=n=1000$. We mainly
compare the results of kaczmarz method and randomized Kaczmarz method. In
perturbed case, the right-hand $b^{\delta}$ is generated from accurate term
$b$, i.e.,

$\displaystyle b_{i}^{\delta}=b_{i}+\delta\max\limits_{i}(|b_{i}|),\qquad
i=1,2,\cdots,n.$

Figure 4.3$\sim$4.3 are the figures of phillips, gravity and shaw solved by
Kaczmarz as $K=10000,\delta=0$ and the initial vector $x_{0}=0$. From the
behavior of the error estimate about the iterative step, it is easy to find
that there are some ’ladders’ between two recycles, in other words, the
iterative improvement of Kaczmarz method is slight within one recycle until at
the beginning of the next recycle. In fact, the behavior due to the high
correlation between two adjacent equations.

Figure 4.1: Kaczmarz method, K=10000,$\delta=0$

Figure 4.2: Kaczmarz method, K=10000,$\delta=0$

Figure 4.3: Kaczmarz method, K=10000,$\delta=0$

In addition, we also illustrate the behavior from the following deduction. Let
$x_{k}$ be the current iterative solution, we projected $x_{k}$ to the
$(k+1)$th and the $(k+2)$th equations successively, i.e.

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

Let $x^{*}$ be an any solution of linear system $Ax=b$, and denote the error
$e_{k+1}=x_{k+1}-x^{*}$, therefore,

$\displaystyle e_{k+1}-e_{k+2}$
$\displaystyle=\frac{a_{k+2}a_{k+2}^{T}}{\|a_{k+2}\|_{2}^{2}}(I-\frac{a_{k+1}a_{k+1}^{T}}{\|a_{k+1}\|_{2}^{2}})e_{k}$
$\displaystyle=\frac{a_{k+2}}{\|a_{k+2}\|_{2}}(\frac{a_{k+2}^{T}}{\|a_{k+2}\|_{2}}-\frac{a_{k+1}^{T}\cos(\widehat{a_{k+1},a_{k+2}},)}{\|a_{k+1}\|_{2}})e_{k},$

so,

$\displaystyle\bigl{|}\|e_{k+1}\|-\|e_{k+2}\|\bigr{|}$
$\displaystyle\leq\|e_{k+1}-e_{k+2}\|\leq\bigl{\|}\frac{a_{k+2}^{T}}{\|a_{k+2}\|_{2}}-\frac{a_{k+1}^{T}\cos(\widehat{a_{k+1},a_{k+2}})}{\|a_{k+1}\|_{2}}\bigr{\|}\|e_{k}\|$
$\displaystyle\leq\bigl{(\|}\frac{a_{k+2}^{T}}{\|a_{k+2}\|_{2}}\|_{2}^{2}+\|\frac{a_{k+1}^{T}}{\|a_{k+1}\|_{2}}\|_{2}^{2}-2\cos(\widehat{a_{k+1},a_{k+2}})\langle\frac{a_{k+2}^{T}}{\|a_{k+2}\|_{2}},\frac{a_{k+1}^{T}}{\|a_{k+1}\|_{2}}\rangle\bigr{)}^{\frac{1}{2}}\|e_{k}\|$
$\displaystyle=\bigl{(}2-2\cos^{2}(\widehat{a_{k+1},a_{k+2}})\bigr{)}^{\frac{1}{2}}\|e_{k}\|.$
(4.1)

From (4), if the intersection angle between two adjacent projection equations
is small, the improvement of the current iteration $x_{k+1}$ is slight than
the last iteration $x_{k}$, Because the intersection angle between the normal
vectors of the adjacent equations are very small for these test problems, the
behavior of their errors are as we can see in Figure 4.3$\sim$4.3. Meanwhile,
these errors don’t converge to zero, i.e. the numerical solutions don’t
converge to the original solutions(which can also be seen from Figure
4.6$\sim$4.6). In fact, from Theorem 2.1 and Theorem 2.7, the numerical
solutions of Kaczmarz method converges to their corresponding Moore-Penrose
generalized solutions.

Figure 4.4: Kaczmarz method, K=100000,$\delta=0$

Figure 4.5: Kaczmarz method, K=100000,$\delta=0$

Figure 4.6: Kaczmarz method, K=100000,$\delta=0$

Let $K=100000$ and $\delta=0$, we can observe the subsequent behavior of these
test problems solved by Kaczmarz method from Figure 4.6$\sim$4.6, the error
changes of these problems tend to be stable.

Figure 4.7: phillips(10000),
$\delta=0.1$

Figure 4.8: gravity(10000),
$\delta=0.1$

Figure 4.9: shaw(10000),
$\delta=0.1$

Figure 4.10: phillips(100000),
$\delta=0.1$

Figure 4.11: gravity(100000),
$\delta=0.1$

Figure 4.12: shaw(100000),
$\delta=0.1$

Figure 4.9$\sim$4.9 and Figure 4.12$\sim$4.12 show the behavior of the error
results for phillips, gravity and shaw solved by Kaczmarz method as
$K=10000,\delta=0.1$, respectively. Kaczmarz method takes on ’semi-
convergence’ in solving phillips, gravity and shaw problems.

Figure 4.13: phillips(10000)

Figure 4.14: gravity(10000)

Figure 4.15: shaw(10000)

The behavior of convergence of randomized Kaczmarz mehtod can be seen in
Figure 4.15$\sim$ 4.18, where Figure 4.15$\sim$ 4.15 are the results of
randomized Kaczmarz method as $K=10000,\delta=0$, these curve decline
monotonously but don’t tend to zero, which is to some extent in accordance
with Theorem 2.5. When there are noise in linear systems, i.e. the right hand
of linear system are $b^{\delta}$, the behavior of convergence of randomized
Kaczmarz method are shown in Figure 4.18$\sim$ 4.18. Actually, Theorem 2.5 in
this paper couldn’t exhibit the tendency of the error on iterative step $k$ as
$\delta=0.1$, nevertheless, Theorem 2.5 shows the error bound between
numerical solution $x_{k}$ and Moore-Penrose generalized solution
$x^{\dagger}$, and the result of Theorem 2.2 is also about the bound rather
than the errors about $k$. Not only Theorem 2.2 but also Theorem 2.5 couldn’t
reflect the ’semi’-convergent behavior.

Figure 4.16: phillips(10000)

Figure 4.17: gravity(10000)

Figure 4.18: shaw(10000)

##  5 Conclusion

In this paper, we consider Kaczmarz like methods for solving linear systems.
For consistent systems $Ax=b$, Theorem 2.5, 2.7, 3.1 and Corollary 2.6, 2.8,
3.2 show that the vector sequence $\\{x_{k}\\}$ generated from Kaczmarz like
methods converge to $P_{N(A)}x_{0}+x^{\dagger}$ exponentially. Meanwhile, for
inconsistent linear systems, Theorem 2.5, 3.1 and Corollary 2.6, 3.2 show
Kaczmarz like methods is not convergent. From ill-posed problem theory, the
generalized solution $x^{\dagger}$ is crucial for linear system $Ax=b$.
Therefore, Theorem 2.5, 3.1 and Corollary 2.6,3.2 exhibit the convergent
tendency to $P_{N(A)}x_{0}+x^{\dagger}$ of Kaczmarz method for solving
inconsistent linear systems. In addition, most overdetermined linear system
$Ax=b^{\delta}$ is either inconsistent (i.e. $b^{\delta}=b\notin R(A)$) or
ill-posed($b^{\delta}\neq b$, $b\in R(A)$ and $b^{\delta}$ is in or not in the
range $R(A)$). Hence, Kaczmarz like methods can be regarded as a regularized
method, where iterative step $k$ is regularized parameter.

## References

  * [1] Ben-Israel A and Greville TNE, _Generalized inverses: Theory and applications_ , Wiley-Interscience, New York, 2003.
  * [2] Emmanuel Candes, Justin Romberg, and Terence Tao, _Stable signal recovery from incomplete and inaccurate measurements_ , Communications on Pure & Applied Mathematics 59 (2006), no. 8, 1207–1223.
  * [3] A. J. Devaney, _A filtered backpropagation algorithm for diffraction tomography_ , Ultrasonic Imaging 4 (1982), no. 4, 336–350.
  * [4] H W Engl, M Hanke, and A Neubauer, _Regularization of Inverse Problems_ , Kluwer Academic, 1996.
  * [5] Heinz W Engl, Karl Kunisch, and Andreas Neubauer, _Convergence rates for Tikhonov regularisation of non-linear ill-posed problems_ , Inverse Problems 5 (1989), 523–5411.
  * [6] Chuan gang Kang and Heng Zhou, _The property of analysis of the convergent solution to kaczmarz method_ , CT Theory and Applications 24 (2015), no. 5, 701–709.
  * [7] Richard Gordon, Robert Bender, and Gabor Herman, _Algebraic reconstrction techniques (art) for three dimensional electron microscopy and x-ray photography_ , J. Theor. Biol. 29 (1970), 471–481.
  * [8] Martin Hanke, _Regularizing properties of a truncated Newton-CG algorithm for nonlinear inverse problems_ , Numer.Funct.Anal.Optim. 18 (1997), 971–993.
  * [9] Per Christian Hansen, _Regularization tools: A matlab package for analysis and solution of discrete ill-posed problems_ , Numerical Algorithms 6 (1994), no. 1, 1–35.
  * [10] Patrick B. Heffernan and Richard A. Robb, _Image reconstruction from incomplete projection data: iterative reconstruction-projection techniques_ , IEEE Transactions on Biomedical Engineering 30 (1983), 838–841.
  * [11] Tamon Inouye, _Image reconstruction with limited angel projection data_ , IEEE Transactions on Nuclear Science 26 (1979), 2666–2669.
  * [12] Yuling Jiao, Bangti Jin, and Xiliang Lu, _Preasymptotic convergence of randomized kaczmarz method_ , Inverse Problems 33 (2017).
  * [13] Stefan Kaczmarz, _Angenäherte auflösung von systemen linearer gleichungen_ , Bulletin de Academie Polonaise des Sciences et Lettres 35 (1937), 355–357.
  * [14] Y. Long, J. A. Fessler, and J. M. Balter, _3d forward and back-projection for x-ray ct using separable footprints_ , IEEE Transactions on Medical Imaging 29 (2010), no. 11, 1839–1850.
  * [15] Anna Ma, Deanna Needell, and Aaditya Ramdas, _Convergence properties of the randomized extended gauss-seidel and kaczmarz methods_ , Siam Journal on Matrix Analysis & Applications 36 (2015), no. 4, 1590–1604.
  * [16] F Natterer, _The mathematics of computerized tomography_ , Wiley-Interscience, 1986.
  * [17] Deanna Needell, _Randomized kaczmarz solver for noisy linear systems_ , Behav. Inf. Technol. 50 (2010), no. 2, 395–403.
  * [18] Deanna Needell, Ran Zhao, and Anastasios Zouzias, _Randomized block kaczmarz method with projection for solving least squares_ , Linear Algebra & Its Applications 484 (2015), 322–343.
  * [19] Denna Needell and Joel A. Tropp, _Paved with good intentions:analysis of a randomized block kaczmarz method_ , Linear Algebra & Its Applications 441 (2014), 199–221.
  * [20] Xiaochuan Pan, Xia Dan, Y Zou, and Lifeng Yu, _A unified analysis of fbp-based algorithms in helical cone-beam and circular cone- and fan-beam scans_ , Physics in Medicine & Biology 49 (2004), no. 18, 4349–4369.
  * [21] Constantin Popa, _Least-squares solution of overdetermined inconsistent linear systems using kaczmarz’s relaxation_ , International Journal of Computer Mathematics 55 (1995), no. 1-2, 79–89.
  * [22] J. A. Reeds and L. A. Shepp, _Limited angle reconstruction in tomography via squashing_ , IEEE Transactions on Medical Imaging 6 (1987), no. 2, 89–97.
  * [23] Thomas Strohmer and R Vershynin, _A randomized kaczmarz algorithm with exponential convergence_ , J. Fourier Anal. Appl 15 (2009), 262–278.
  * [24] Elfing T, Hanson PC, and Nikazad T, _Semi-convergence properties of kaczmarz’s method_ , Inverse Problems 30 (2014), no. 5, 055007.
  * [25] Herman G T and Meyer L B, _relaxation method for image reconstruction commun_ , ACM 21 (1978), 152–158.
  * [26] Herman G T and Lent A and Lutz P H, _Algebraic reconstruction techniques cna be made computationally efficient_ , IEEE Trans. Med Imaging 12 (1993), 600–609.
  * [27] Kunio Tanabe, _Projection method for solving a singular system of linear equations and its applications_ , Numer. Math 17 (1971), 203–214.
  * [28] A Zouzias and N M Freris, _Randomized extended kaczmarz solver for solving least squares_ , SIAM J. Matrix Anal. Appl. 34 (2013), 773–793.


Autumn 2020

# Turing Number: How Far Are You to A. M. Turing Award?

Feng Xia1,2 Jiaying Liu1 Jing Ren1 Wei Wang3 Xiangjie Kong4
1 Dalian University of Technology  China
2 Federation University Australia  Australia
3 University of Macau  China
4 Zhejiang University of Technology  China

###### Abstract

The ACM A.M. Turing Award is commonly acknowledged as the highest distinction
in the realm of computer science. Since 1960s, it has been awarded to computer
scientists who made outstanding contributions. The significance of this award
is far-reaching to the laureates as well as their research teams. However,
unlike the Nobel Prize that has been extensively investigated, little research
has been done to explore this most important award. To this end, we propose
the Turing Number ($TN$) index to measure how far a specific scholar is to
this award. Inspired by previous works on Erdos Number and Bacon Number, this
index is defined as the shortest path between a given scholar to any Turing
Award Laureate. Experimental results suggest that $TN$ can reflect the
closeness of collaboration between scholars and Turing Award Laureates. With
the correlation analysis between $TN$ and metrics from the bibliometric-level
and network-level, we demonstrate that $TN$ has the potential of reflecting a
scholar’s academic influence and reputation.

##  1 Itroduction

As the ”Nobel Prize of Computing”, the ACM A.M. Turing Award is named for the
great British mathematician, Alan M. Turing. More than fifty years have passed
since the ACM awarded its first Turing Award to Alan Perlis. As of 2019, over
70 scholars from around the world have received the Turing Award [Fisher
(2017), Kong et al. (2019)]. However, the research of Turing Award seems like
a virgin territory compared with the Nobel Prize. For example, considerable
effort has been done in terms of understanding the characteristics of Nobel
Prize Laureates as well as predicting future winners [Ren et al. (2019), Kong
et al. (2020), Bai et al. (2020)]. However, when you try to search any study
on the Turing Award from Google Scholar, you may get disappointed because
little related research or papers has been done or published. We believe that
analyzing the highest award of computing is beneficial to highlight the
significant contribution of the Turing Award Laureates, look ahead to the
future of computing, and help motivate other computer scientists to dream and
create [Hanson (2017), Zhang et al. (2020)].

One of the promising research directions on exploring Turing Award is the
behavior dynamics of its laureates. Similar research has been done in terms of
Nobel Award Laureates [Schlagberger et al. (2016)], which examines the
possibility of predicting the Nobel Award Laureates. At the same time,
network-based approaches have been extensively utilized to explore the
collaboration behaviors of scientists [Liu et al. (2019), Liu et al. (2020)].
Inspired by previous work on Erdos Number and Bacon Number, this study tries
to answer an interesting question in terms of Turing Award: How far a computer
scientist is to the great scientist Turing? In other words, how to measure the
shortest path between a given scholar and Turing. In the era of Turing,
scientists are not as collaborative as nowadays and Turing had no collaborator
when publishing papers. Therefore, an alternative question is proposed: How
far a computer scientist is to the Turing Award Laureates? Specifically, we
propose ”Turing Number” index ($TN$) which measures the shortest path between
a given scholar to any Turing Award Laureate.

As $TN$ measures the closeness of collaboration between scholars and Turing
Award Laureates, we assume that it can be used to measure the influence of
scholars in the Turing collaboration network. To verify this hypothesis, we
design experiments from the bibliometric-level and network-level,
respectively. From the perspective of bibliometric, we calculate the
productivity (e.g., number of papers) and impact (e.g., citations and h-index)
for both scholars and countries, and examine the relationships between these
metrics and $TN$. From the perspective of network structure, we use different
indices such as degree centrality, closeness centrality, and betweenness
centrality to measure the importance of different $TN$ scholars in Turing
collaboration networks. Experimental results suggest that $TN$ can not only
reflect the closeness of collaboration between scholars and Turing Award
Laureates, but also measure the influence of scholars. Our contributions of
this article are summarized as follows:

  * •

We propose a new way to construct the scientific collboration network
centering around the Turing Award Laureates.

  * •

We define a new metric $TN$ to quantify the distance between scholars and
Turing Award Laureates.

  * •

We provide detailed correlation analysis of various metrics from the
bibliometric-level and network-level, with the aim of exploring the
relationship between $TN$ and scholar’s academic influence and reputation.

##  2 Social Network Analysis

Dataset To construct the scientific collaboration network, the
DBLP111https://dblp.org/ dataset is used in this work and we select the
computer scientists by 2020. All related information consist of scholar’s
name, paper title, and their publication years. The geographical location
information and citation information of each scholar is acquired by matching
the author information with Aminer dataset [Tang et al. (2008)] to get the
institution information and citation relationships. Then, we use the Google
Map API222https://cloud.google.com/maps-platform/ to get the latitude and
longitude of the institutions, as well as the region information. Authors’
name disambiguation process is conducted based on previous corresponding work
[Sinatra et al. (2016)]. The Turing Award Laureates are identified by name
manually. For institutions’ name disambiguation, we use the regular expression
to search and match the institution information. Meanwhile, institutions with
missing records are excluded. For scholars with more than one institution, we
use the institution information by the investigating year. The final
collaboration network includes 53,531 scholars including 65 Turing Award
Laureates and their collaborators from 119 countries and regions. In this
collaboration network, nodes represent scholars and edges represent
collaboration relationships between scholars. Based on the constructed
network, we calculate $TN$ for each scholar as follows.

Turing Number (_TN_) Turing number refers to the network distance of an author
to the Turing Award Laureates. A Turing number is defined as the minimum of
the shortest path of each author to all Turing Award Laureates. To be assigned
a Turing number, someone must be a coauthor of a research paper with another
person who has a finite Turing number. A Turing Award laureate has a Turing
number of zero. Anybody else’s Turing number is $k+1$ where $k$ is the lowest
Turing number of any coauthor. Based on its definition, a smaller $TN$ denotes
that the scholar is closer to the Turing Award.

Following previous conceptualizations, we explore $TN$ from two aspects:
bibliometric-level and network-level. The bibliometric indicators we used
include the number of publications, citations, and h-index. Table 1 lists a
detailed description of network-level indices used in this work.

Furthermore, for better understanding the special position of the Turing Award
Laureates in the network and eliminating geographical bias, we construct a
null model for comparison. The null model which is constructed by randomly
selecting equal number of scholars, i.e., 65 as the Turing Award Laureates.

Table 1: Description of network-level indices.

Index |  Description |  Calculation formula
---|---|---
Degree Centrality |  the number of links incident upon a node |  $C_{D}(v)=deg(v)$
Closeness Centrality |  the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph |  $C_{C}(v)=\frac{|V|-1}{\sum_{i\neq v}d_{vi}}$
Betweenness centrality |  the number of times a node occurs on the shortest path between other nodes |  $B_{C}(v)=\sum_{s\neq v\neq t\in V}\frac{\sigma_{st}(v)}{\sigma_{st}}$
Eigenvector Centrality |  an algorithm for measuring the transmission impact and connectivity between nodes |  the calculation process can be found in [Bonacich (1987)]
Load Centrality |  the fraction of all shortest paths that pass through that node |  the calculation process can be found in [Newman (2001a), Goh et al. (2001)]

##  3 Results and Discussions

###  3.1 Bibliometric-level analysis

To study how far a computer scientist is to the Turing Award, we first explore
the distribution of $TN$ over all investigated scholars and countries (see
Fig. 1). Fig. 1(a) shows most scholars have a $TN$ of 3. Meanwhile, more than
90% scholars’ $TN$ is between 2 and 5. It indicates that it takes 3 to 5 jumps
for a scholar to get connected with a Turing Award Laureate. This observation
confirms previous finding on six-degree separation [Watts and Strogatz
(1998)], which means scholars can reach each other by a relatively small
number of connections. However, since the $TN$ is measured by the distance
from a scholar to the Turing Award laureate community, it is much smaller.
Note that there are few people whose $TN$ is more than 5, which means that the
Turing Award laureate collaboration network is well connected. Meanwhile, as
shown in Fig. 1(a), the $TN$ number in the null model is much higher than that
of real Turing Award Laureates network. Fig. 1(b) shows the geographical
distribution of $TN$. We can see that the U.S. achieves a lower $TN$. The Asia
and Africa scholars have higher value of $TN$ than scholars from Europe and
America.

(a) Scholar distribution of $TN$

(b) Geographic distribution of $TN$

Figure 1: Distribution of $TN$.

Figure 2 shows the statistics of scholars with different $TN$ in terms of
number of publications, citations, and h-index. It shows that with the
increase of $TN$, the number of publications declines accordingly. The average
number of publications of scholars with $TN=1$ is 61.64 while that of scholars
with $TN=5$ is 2.17. Scholars’ average impact in terms of citations and
h-index also declines significantly with the increase of $TN$. For instance,
the average h-index of scholars with $TN=1$ is 17.14 while that of scholars
with $TN=5$ is only 1.21. All experimental results verify our hypothesis that
$TN$ can reflect the academic influence of scholars.

Figure 2: Scholars with different $TN$ in terms of the number of publications,
citations, and h-index.

Table 2 shows the statistics of $TN$ in the top 11 countries in terms of the
number of scholars. It is acknowledged that The United States is advanced in
the field of computer science. Not surprisingly, it has the best performance
in terms of number of scholars, citations, and $TN$. Influential countries in
computer science area such as Germany, France and Canada are also high on the
list. All of them have high impact in terms of average h-index and low $TN$.
Besides that, emerging countries such as China and India are also on the list.
The study by Nature Index has shown that China’s international papers have
increased to 24% in 2016, which merely lags behind Germany, the United States
and the United Kingdom [Phillips (2017)]. So we can believe that $TN$ is a
good measure to reflect the national scientific research level.

Table 2: Statistics of $TN$ in top countries.

Country | Scholars | Papers | Citations | h-index | TN
---|---|---|---|---|---
United States | 16,791 | 15.40 | 657.56 | 5.58 | 3.24
China | 3,438 | 9.84 | 161.63 | 2.92 | 3.89
Germany | 2,477 | 14.48 | 299.55 | 4.63 | 3.48
France | 2,279 | 13.58 | 248.30 | 4.42 | 3.58
Canada | 1,960 | 14.93 | 537.91 | 4.78 | 3.44
United Kingdom | 1,906 | 14.67 | 416.52 | 5.08 | 3.53
Japan | 1,378 | 10.68 | 106.41 | 2.75 | 3.98
Brazil | 1,374 | 9.14 | 84.86 | 2.58 | 3.81
South Korea | 1,272 | 7.83 | 109.57 | 2.80 | 4.07
Italy | 1,095 | 24.57 | 436.10 | 6.45 | 3.58
India | 1,078 | 15.62 | 227.45 | 4.52 | 3.86

To further understand the association between $TN$ and conventional
bibliometric indicators, we perform correlation analysis between the two sets
of variables. The results are shown in Table 3. We can observe from this table
that the correlation coefficients between $TN$ and bibliometric indicators are
negative. Besides that, the correlation between each index and $TN$ is always
significant. H-index has the highest correlation with $TN$ in comparison with
citations and number of publications. Overall, $TN$ is related to bibliometric
indicators. Scholars with lower $TN$ have better academic performance, which
demonstrates the feasibility of utilizing $TN$ to measure scholars’ impact.

Table 3: Results of correlation analysis.

Correlation analysis method | No. of Publications | No. of Citations | H-index
---|---|---|---
Pearson | -0.330*** | -0.258*** | -0.440***
Spearman | -0.463 *** | -0.450*** | -0.490***
Kendall | -0.381*** | -0.393*** | -0.408***
$*p<0.1;**p<0.05;***p<0.01$ |  |  |

###  3.2 Network-level analysis

The analysis of network level indicators is helpful to understand the
evolution and development of Turing collaboration network and find the key
nodes in the network. From the network structure perspective, we explore the
distribution of $TN$ conditional to network centrality measures mentioned in
Table 1. The result is shown in Fig. 3. Specifically, we take the $\ln$ of
each index. We can see that with the increase of $TN$, the value of each
indicator gradually becomes smaller. For example, for betweenness centrality,
it ranges from $0.01$ to $1.78e^{-12}$ while $TN$ changes from 0 to 7.
Overall, the result shows that scholars with lower $TN$ are more important in
the network in terms of degree centrality, between centrality, closeness
centrality, eigenvector centrality, and load centrality. $TN$ is not only
related to bibliometric indicators but also network centrality indicators.
Scholars with lower $TN$ have more important positions in the collaboration
network, which demonstrates the feasibility of utilizing $TN$ to measure
scholars’ importance from the network structure level.

Figure 3: Distribution of $TN$ conditional to network centrality measures.

##  4 Conclusion

Turing Award is the highest honor in the field of computer science. In this
article, we investigated the potential rules of Turing Award collaboration
network and explored the relationship and distance between an ordinary scholar
and Turing Award Laureates. Our results showed that most scholars are close to
the Turing Award Laureates within three steps in the network. The correlation
analysis between this indicator and traditional bibliometric indicators
suggested that $TN$ is meaningful for scholars’ impact evaluation. Besides,
our comparison of $TN$ among different countries showed the feasibility of
utilizing this indicator to evaluate the influence of a given country.
Furthermore, $TN$ can be regarded as a measure of the collaboration with top
computer scientists around the world. It can somehow reflect the reputation of
a given scholar. By examining the relationships between $TN$ and network
centrality indicators, we concluded that scholars with lower value of $TN$
generally have more important positions in the collaboration network.

## ACKNOWLEDGMENTS

This work is partially supported by National Natural Science Foundation of
China under Grant No. 61872054 and the Fundamental Research Funds for the
Central Universities (DUT19LAB23).

## References

  * Bai et al. (2020) Bai, X., Pan, H., Hou, J., Guo, T., Lee, I., and Xia, F. 2020\.  Quantifying success in science: An overview.  IEEE Access 8, 123200–123214.
  * Barabási and Albert (1999) Barabási, A.-L. and Albert, R. 1999\.  Emergence of scaling in random networks.  Science 286, 5439, 509–512.
  * Bonacich (1987) Bonacich, P. 1987\.  Power and centrality: A family of measures.  American Journal of Sociology 92, 5, 1170–1182.
  * Fisher (2017) Fisher, L. M. 2017\.  Turing laureates celebrate award’s 50 th anniversary.  Communications of the ACM 60, 9, 20–23.
  * Goh et al. (2001) Goh, K.-I., Kahng, B., and Kim, D. 2001\.  Universal behavior of load distribution in scale-free networks.  Physical Review Letters 87, 27, 278701.
  * Hanson (2017) Hanson, V. L. 2017\.  Celebrating 50 years of the turing award.  Communications of the ACM 60, 2, 5–5.
  * Kong et al. (2019) Kong, X., Shi, Y., Wang, W., Ma, K., Wan, L., and Xia, F. 2019\.  The evolution of turing award collaboration network: Bibliometric-level and network-level metrics.  IEEE Transactions on Computational Social Systems 6, 6, 1318–1328.
  * Kong et al. (2020) Kong, X., Zhang, J., Zhang, D., Bu, Y., Ding, Y., and Xia, F. 2020\.  The gene of scientific success.  ACM Transactions on Knowledge Discovery from Data (TKDD) 14, 4, 1–19.
  * Liu et al. (2020) Liu, J., Ren, J., Zheng, W., Chi, L., Lee, I., and Xia, F. 2020\.  Web of scholars: A scholar knowledge graph.  In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 2153–2156.
  * Liu et al. (2019) Liu, J., Xia, F., Wang, L., Xu, B., Kong, X., Tong, H., and King, I. 2019\.  Shifu2: A network representation learning based model for advisor-advisee relationship mining.  IEEE Transactions on Knowledge and Data Engineering.
  * Newman (2001a) Newman, M. E. 2001a.  Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality.  Physical Review E 64, 1, 016132.
  * Newman (2001b) Newman, M. E. 2001b.  The structure of scientific collaboration networks.  Proceedings of the National Academy of Sciences 98, 2, 404–409.
  * Phillips (2017) Phillips, N. 2017\.  A close look at china’s rise.  Nature 545 7655, S39.
  * Ren et al. (2019) Ren, J., Wang, L., Wang, K., Yu, S., Hou, M., Lee, I., Kong, X., and Xia, F. 2019\.  Api: An index for quantifying a scholar’s academic potential.  IEEE Access 7, 178675–178684.
  * Rodríguez-Navarro (2011) Rodríguez-Navarro, A. 2011\.  Measuring research excellence: Number of nobel prize achievements versus conventional bibliometric indicators.  Journal of Documentation 67, 582–600.
  * Schlagberger et al. (2016) Schlagberger, E. M., Bornmann, L., and Bauer, J. 2016\.  At what institutions did nobel laureates do their prize-winning work? an analysis of biographical information on nobel laureates from 1994 to 2014.  Scientometrics 109, 2, 723–767.
  * Sinatra et al. (2016) Sinatra, R., Wang, D., Deville, P., Song, C., and Barabási, A.-L. 2016\.  Quantifying the evolution of individual scientific impact.  Science 354, 6312, aaf5239.
  * Tang et al. (2008) Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., and Su, Z. 2008\.  Arnetminer: extraction and mining of academic social networks.  In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 990–998.
  * Watts and Strogatz (1998) Watts, D. J. and Strogatz, S. H. 1998\.  Collective dynamics of ‘small-world’ networks.  Nature 393, 6684, 440–442.
  * Zhang et al. (2020) Zhang, J., Wang, W., Xia, F., Lin, Y.-R., and Tong, H. 2020\.  Data-driven computational social science: A survey.  Big Data Research, 100145.

Feng Xia received the BSc and Ph.D. degrees from Zhejiang University,
Hangzhou, China. He is currently an Associate Professor and Discipline Leader
in School of Engineering, IT and Physical Sciences, Federation University
Australia, and on leave from School of Software, Dalian University of
Technology, China, where he is a Full Professor. Dr. Xia has published 2 books
and over 300 scientific papers in international journals and conferences. His
research interests include data science, social computing, and systems
engineering. He is a Senior Member of IEEE and ACM. (Corresponding author;
email<EMAIL_ADDRESS>
Jiaying Liu received the BSc degree in Software Engineering from Dalian
University of Technology, China, in 2016. She is currently working toward the
PhD degree in School of Software, Dalian University of Technology, China. Her
research interests include data science, big scholarly data, and social
network analysis.

Jing Ren received the Bachelor’s degree from Huaqiao University, China, in
2018, and the Master degree from Dalian University of Technology, China, in
2020. She is currently a Research Fellow in the School of Software, Dalian
University of Technology, China. Her research interests include data science,
social computing, and graph learning.

Wei Wang is a Research Fellow at University of Macau, Macau SAR. He received
PhD degree in Software Engineering from Dalian University of Technology in
2018. His research interests include computational social science, data
mining, internet of things, and artificial intelligence. He has authored/co-
authored over 50 scientific papers in international journals and conferences.
He is a member of IEEE, ACM, and CCF.

Xiangjie Kong received the B.Sc. and Ph.D. degrees from Zhejiang University,
Hangzhou, China. He is currently a Professor with College of Computer Science
and Technology, Zhejiang University of Technology, China. He has published
over 100 scientific papers in international journals and conferences. His
research interests include network science, data science, and computational
social science. He is a Senior Member of the IEEE and CCF and is a member of
ACM.