A Relaxed Greedy Block Kaczmarz Method for Solving Large Consistent Linear Systems ()
1. Introduction
We are concerned with the solution of the large consistent linear system
(1)
where
, and
. The Kaczmarz method in [2] is possible one of the most popular, simple while efficient algorithms for solving (1). It was revised to be applied to image reconstruction in [3], which is called algebraic reconstruction technique, and has a large range of fields of applications such as image reconstruction in computerized tomography [4] [5] [6] and parallel computing [7].
There are many extended Kaczmarz algorithms [8] - [16] developed to solve (1). Strohmer and Vershynin in [17] introduced a randomized Kaczmarz method (RK) for consistent overdetermined systems (1). The RK method has a convergence bound with the expected exponential convergence, which was called linear convergence. Zhang [18] proposed an improved greedy Kaczmarz (GK) method for solving (1). Bai and Wu in [19] presented a greedy randomized Kaczmarz algorithm (GRK) for (1) when the system is consistent. In each step of iteration, GRK is based on a probability criterion trying to grasp larger entries of the residual vector. Bai and Wu [20] further developed a relaxed GRK method for large sparse Equations (1). Due to its fast convergence, the block method [21] [22] [23] [24] has also been extensively developed in linear or nonlinear optimization problems. Recently, Liu and Zheng in [1] presented a greedy block Kaczmarz algorithm (GBK) with the iteration
(2)
where the index of the selected row
(3)
with the parameter
(4)
stands for the submatrix
of
,
represents the ith element of the vector b,
denotes the ithrow of
and
denotes the Moore-Penrose pseudoinverse of
.
In this paper, based on the GBK method in [1], we develop a new relaxed greedy block Kaczmarz algorithm (RGBK) for (1). RGBK extends the GBK algorithm by introducing a relaxed parameter. The convergence of the algorithm is provided and the optimal relaxed parameter is discussed. The rest of this paper is organized as follows. In Section 2, a new relaxed greedy block Kaczmarz algorithm is presented. The convergence is provided and the optimal relaxed parameter is determined. Several types of examples are shown in Section 3, including the overdetermined or underdetermined systems with dense and sparse coefficient matrices. Some conclusions are drawn in Section 4.
At the end of this section, we introduce some mathematical symbols that will be used. For a matrix
,
denotes the ith row vector of
.
stands for the submatrix
of
, where
is an index set composed of positive integers not exceeding m, and m is the number of rows of
. Let
and
be the maximum and minimum positive singular values of
, respectively.
and
are the spectral norm and Frobenius norm, respectively. For any vector
,
represents the ith component of p.
2. The Relaxed Greedy Block Kaczmarz Algorithm
Replacing the left side
in (2) with the combination of
and
in (2) by introducing a relaxed parameter
, we have
(5)
Thus
(6)
The method presented by (6) is called a relaxed greedy block Kaczmarz algorithm, which is abbreviated by RGBK. Algorithm 1 summarizes the RGBK algorithm.
We remark that the iteration formulation (6) reduces to (2) when
, thus the GBK method in [1] is a special case of Algorithm 1.
The results below give the convergence of Algorithm 1.
Theorem 1. Assume the linear system (1) is consistent. The iterative sequence
generated by Algorithm 1 converges to the minimum norm solution
of (1). Moreover, it holds that
(7)
where
,
denotes the Frobenius norm of
,
and
are the maximum and minimum positive singular values of
, respectively.
Proof. Let
, where
satisfies
, then we have from (6) that
(8)
According to the definition of
at Step 3 in Algorithm 1 and the fact that
, we have that
Algorithm 1. A relaxed greedy block Kaczmarz algorithm (RGBK).
(9)
For
, it holds that
thus the constant
at step 2 of Algorithm 1 becomes
(10)
Thus (8) together with (9) and (10) implies (7). This completes the proof. □
We derive easily the results below from Theorem 1.
Corollary 1. Let
. Under the conditions of Theorem 1, we obtain an upper bound of error
(11)
Proof. Using (7) iteratively for
, we have (11) with the definition of
. □
The upper bound of error below is independent of
.
Corollary 2. Under the conditions of Theorem 1, (7) becomes
(12)
Proof. We notice that
thus
(13)
Therefore, (12) results from (12) together with (7). □
Remark 1. The RGBK method reduces to the GBK method in [1] when
. Examples in Section 3 provide a way to determine the optimal relaxed parameter value of
that minimizes the CPU time or the number of iteration for both overdetermined and underdetermined systems.
Remark 2. Taking into account the limitation of computer memory space, we use Gaussian Kaczmarz method defined in [22] instead of (6), which could avoid the calculation of
,
where
, this method abbreviated as AGBK.
3. Numerical Examples
In this section, we give several examples to show the efficiency of our RGBK and AGBK methods and compare them with GBK in [1]. All experiments are carried out with the MATLAB 2020b on a computer with 3.00 GHz processing unit and 16 GB RAM.
We compute the solution of the consistent system (1) with
and
computed by
, where
denotes the exact solution generated by the MATLAB function randn. Denote the relative solution residuals
. We define different acceleration ratios as follows,
To avoid calculating the Moore-Penrose inverse
when implementing the update (6) in Algorithm 1, we use the CGLS algorithm in [21] to solve a corresponding least-squares problem. Considering the fairness of the three algorithms, all parameters involved in AGBK are the same as RGBK. We set the initial vector
and the termination criterion satisfying RSE < 10−6 for GBK, RGBK and AGBK in all examples.
Example 4.1. We use this example to illustrate how to determine an optimal parameter
in Algorithm 1 for both overdetermined and underdetermined systems (1). We use different parameter
ranged from 0.05 to 0.9 to compute the number of iteration (IT) and CPU time (CPU) by Algorithm 1 for the consistent systems (1) with
and
, which are randomly dense matrices generated by the MATLAB function randn, respectively, then determine an optimal parameter
that minimizes the IT or CPU.
Figure 1 shows the plot of CPU versus
. From Figure 1, we can choose the optimal parameter
, which minimizes CPU by using Algorithm 1 for the consistent systems (1) with
and
.
Example 4.2. In this case, we give the same way to determine the optimal relaxation parameters
of RGBK as shown in Figure 2, and strictly abide by the method of controlling variables. We default that GBK and RGBK have the same
.
Figure 2 shows the plot of IT and CPU versus relaxed parameter
. From Figure 2(a) and Figure 2(b), we can choose the optimal relaxed parameter
and
, which minimizes CPU by using Algorithm 1 for the consistent systems (1) with
and
.
Figure 1. An optimal parameter (
) determined by the minimum of CPU for overdetermined 2000 × 1000 (left) and underdetermined 1000 × 2000 (right) systems in RGBK.
Figure 2. An optimal relaxed parameter (
) determined by the minimum of IT (left) and CPU (right) for overdetermined and underdetermined systems. (a) IT (left) and CPU (right) versus
with 2000 × 1000; (b) IT (left) and CPU (right) versus
with 1000 × 2000.
Example 4.3. We compare the convergence of RGBK and AGBK with the optimal relaxed parameter
determined similarly in Example 4.2 with that of GBK algorithm for overdetermined and underdetermined systems (1) with
generated by the MATLAB function randn. Table 1 lists IT and CPU(s) of the RGBK and AGBK algorithms with the optimal relaxed parameter
compared with that of GBK algorithm for different overdetermined systems (1) with Gaussian coefficient matrices
. The corresponding optimal relaxed parameter computed similarly in Example 4.2 is
, respectively.
Table 2 shows similar results for different underdetermined Gaussian systems (1) with
. From Table 1 and Table 2, we can see the advantages of our proposed RGBK and AGBK methods over GBK algorithm.
Example 4.4. We use the RGBK and AGBK methods and compare them with GBK to solve systems (1) with sparse coefficient matrix
from the Florida sparse matrix collection in [25]. Table 3 summarizes the different sparse systems and its density and condition number
, where the density of
means the ratio of the number of the nonzero elements of
to the total number of the elements of
.
Table 4 lists IT and CPU(s) of the RGBK and AGBK algorithms with the optimal
Table 1. Performance of GBK, RGBK, AGBK for overdetermined systems.
Table 2. Performance of GBK, RGBK, AGBK for underdetermined systems.
Table 3. The properties of different sparse matrices.
Table 4. Performance of GBK, RGBK, AGBK for overdetermined systems.
relaxed parameter
compared with that of GBK algorithm for different sparse systems (1) with coefficient matrices
. The corresponding optimal relaxed parameter computed similarly in Example 4.3 is
and 0.8, respectively. Figure 3 shows the plot of RSE versus IT (left) or RSE versus CPU (right) of Algorithm 1 applied to solve (1) with different sparse coefficient matrix
in Table 4. From Table 4, we can see that the speedup ratio SU-R can reach 1.2246 and SU-A can reach 2.5934, which shows the fast convergence of our proposed algorithm. From Figure 3, RGBK and AGBK converge much faster than GBK does on RSE versus IT (left) and RSE versus CPU (right) for sparse consistent Equation (1) with coefficient matrices
named ash958 and stat96v5 in Table 4.
Example 4.5. This example uses RGBK and AGBK to restore a computer
Figure 3. RSE versus IT (left) and RSE versus CPU (right) of RGBK and AGBK compared with GBK to solve consistent Equation (1) with sparse coefficient matrix
named ash958 (a) stat96v5 (b) in Table 3. (a) IT (left) and CPU (right) vesue ash958; (b) IT (left) and CPU (right) vesue stat96v5.
tomography (CT) image. The MATLAB function
from Algebraic Iterative Reconstruction (ART) package in [26], which generates a large sparse matrix
and the exact solution
is used, where
,
and
, then the size of
is 17,850 × 4900. We compute b by
, RGBK and AGBK are used to recover
from b and compared with the GBK method.
Table 5 reports the IT and CPU(s), and RSE of RGBK and AGBK compared with GBK for overdetermined consistent sparse matrix, where
. Figure 4 shows the recovered images by GBK, RGBK and AGBK together with the original image.
It can be seen from Table 5 that RGBK(1.3) and AGBK obtain lower IT and CPU(s) than GBK(0.2) for restoring CT images, which show that RGBK and AGBK converge faster than GBK dose if the parameter
is selected appropriately.
Table 5. GBK, RGBK and AGBK for reconstruction of CT image.
Figure 4. The original “phantom” image (a), the recovered images by GBK (b), RGBK(1.3) (c) and AGBK (d).
4. Conclusion
We present a relaxed GBK algorithm abbreviated as RGBK for solving large consistent linear systems. The RGBK method extends the GBK method in [17]. The convergence is provided and a method is provided to determine an optimal relaxed parameter for the RGBK method. In addition, AGBK effectively accelerates the convergence of RGBK in running time. The examples for different cases show the advantage of the proposed RGBK and AGBK methods as long as the optimal relaxation parameter
is determined.
Acknowledgements
The authors thank the reviewers for providing some helpful comments. Research by Y.L. was partially supported by The Innovation Fund of Postgraduate, Sichuan University of Science & Engineering (grant y2021101), Research by F.Y. was partially supported by the Opening Project of Sichuan Province University Key Laboratory of Bridge Non-destruction Detecting and Engineering Computing (grant 2020QZJ03) and SUSE (grant 2019RC09, 2020RC25) and research by G.H. was supported in part by Application Fundamentals Foundation of STD of Sichuan (grant 2020YJ0366).