{'fraction_non_alphanumeric': 0.04019352437662821, 'fraction_numerical': 0.01497953107554894, 'mean_word_length': 4.2976835879743716, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Block sampling Kaczmarz-Motzkin methods for consistent linear systems

The sampling Kaczmarz-Motzkin (SKM) method is a generalization of the randomized Kaczmarz and Motzkin methods. It first samples some rows of coefficient matrix randomly to build a set and then makes use of the maximum violation criterion within this set to determine a constraint. Finally, it makes progress by enforcing this single constraint. In this paper, on the basis of the framework of the SKM method and considering the greedy strategies, we present two block sampling Kaczmarz-Motzkin methods for consistent linear systems. Specifically, we also first sample a subset of rows of coefficient matrix and then determine an index in this set using the maximum violation criterion. Unlike the SKM method, in the rest of the block methods, we devise different greedy strategies to build index sets. Then, the new methods make progress by enforcing the corresponding multiple constraints simultaneously. Theoretical analyses demonstrate that these block methods converge at least as quickly as the SKM method, and numerical experiments show that, for the same accuracy, our methods outperform the SKM method in terms of the number of iterations and computing time.


Introduction
We consider the following consistent linear systems where A ∈ R m×n with m ≫ n, b ∈ R m , and x is the n-dimensional unknown vector. As we know, the Kaczmarz method [1] is a popular so-called row-action method for solving the systems (1). In 2009, Strohmer and Vershynin [2] proved the linear convergence of the randomized Kaczmarz (RK) method. Subsequently, many randomized Kaczmarz type methods were proposed for different possible systems settings; see for example [3][4][5][6][7][8][9] and references therein. Unlike the RK method which selects the working rows of A according to some probability distribution, Motzkin method [10,11] employs a greedy strategy, i.e., the maximum violation criterion, to select the working row in each iteration. So, the method is also known as the Kaczmarz method with the "most violated constraint control" or "maximal-residual control" [12][13][14]. This greedy strategy makes the Motzkin method outperform the RK method in many cases. So, many analyses and applications of the Motzkin method were published recently; see for example [15][16][17] and references therein.
The sampling Kaczmarz-Motzkin (SKM) method proposed in [18] for solving linear feasibility problem is a combination of the RK and Motzkin methods. Its accelerated version was presented in [19], which introduces Nesterov's acceleration scheme. In addition, an improved analysis of the SKM method was given in [20]. The SKM method overcomes some drawbacks of the methods of RK and Motzkin. For example, the Motzkin method is expensive since it selects the index i k at the iteration k by comparing the residual errors of all the constraints, and the RK method may make progress slowly since it doesn't employ a greedy strategy. Instead, the SKM method can select an index by just comparing the residual errors of part of constraints, and employs the maximum violation criterion. However, the SKM method may be slow because it makes progress by enforcing only one constraint. Inspired by the block algorithms given in [21][22][23] which can accelerate the original ones, in this paper, we consider the block versions of the SKM method. Two greedy strategies are devised to determine the index sets for block iteration.
The rest of this paper is organized as follows. In Section 2, some notation and preliminaries are given. Our methods and their convergences are discussed in Section 3 and Section 4, respectively. Finally, we present the numerical results in Section 5.

Notation and preliminaries
Throughout the paper, for a matrix A, A (i) and R(A) denote its i-th row (or i-th entry in the case of a vector) and column space, respectively. We denote the number of elements of a set I by |I | and let the positive eigenvalues of A T A, where (·) T denotes the transpose of a vector or a matrix, be always arranged in algebraically nonincreasing order: To analyze the convergence of our new methods, the following fact will be used extensively later in the paper.

Lemma 1 ( [24]
) Let A ∈ R n×n be symmetric and A t ∈ R t×t be its principal submatrix. Then In addition, to compare the SKM method and our new methods clearly, we list the SKM method from [18] in Algorithm 1.

Remark 1 Note that if
then i k ∈ I k . So the index set I k in Algorithm 2 is always nonempty.
Remark 2 Compared with the SKM method, in each iteration, the BSKM1 method can eliminate several large violated constraints control simultaneously. So, the BSKM1 method converges faster; see the detailed discussions following Theorem 1. In addition, if β = m, the BSKM1 method reduces to the Motzkin method. This means that the BSKM1 method can be also regarded as the block version of the Motzkin method. Now, we provide the convergence of Algorithm 2.
Theorem 1 From an initial guess x 0 ∈ R(A T ), the sequence {x k } ∞ k=0 generated by the BSKM1 method converges linearly in expectation to the least-Euclidean-norm Proof From Algorithm 2, using the fact Ax ⋆ = b, we have Since A † I k A I k is an orthogonal projector, taking the square of the Euclidean norm on both sides and using the Pythagorean theorem, we get which together with the Courant-Fisher theorem: and the fact λ min (( On the other hand, from Algorithm 2, if i k ∈ I k , we have Then Now, taking expectation of both sides (with respect to the sampled τ k ), we have Further, considering (3), we get which is the desired result.
Remark 3 According to Lemma 1, it is easy to see that λ min (A T A) That is, the convergence factor of the BSKM1 method is indeed smaller than 1.

Remark 4 From Algorithm 2, we know that {x|A
Similar to the analysis in [20], we can obtain which together with the fact In the above expressions, x BSKM1 k and x SKM k denote the next approximations generated by the BSKM1 and SKM methods, respectively. Hence, the BSKM1 method converges at least as quickly as the SKM method.
In addition, setting l k = arg max from Algorithm 2, we can obtain So, we also immediately get that the BSKM1 method converges at least as quickly as the Motzkin method.

The second block sampling Kaczmarz-Motzkin method
Considering that |I k | in Algorithm 2 may be 1 for all k = 1, 2, . . . and the size of the index set I k cannot be controlled, we design the second block sampling Kaczmarz-Motzkin (BSKM2) method, which is presented in Algorithm 3. The biggest difference between the BSKM2 and BSKM1 methods is the way to build the index set. For Algorithm 3, we can control the size of the index set J k .

Algorithm 3 The BSKM2 method
Input: Matrix A ∈ R m×n , vector b ∈ R m , parameter η, initial estimate x 0 . Output: Approximate x solving Ax = b. 1. For j = 1 : η 2. Choose a sample of β j constraints, τ j , uniformly at random from among the rows of A without replacement.

Repeat.
Remark 5 Note that if then i k ∈ J k . So the index set J k in Algorithm 3 is always nonempty.

Remark 6
The iteration index t k used for updating of the SKM method belongs to the index set J k used in the BSKM2 method. So the latter makes progress faster than the former. In addition, If η = 1, the BSKM2 method reduces to the Motzkin method. Now, we bound the expected rate of convergence for Algorithm 3.
Theorem 2 From an initial guess x 0 ∈ R(A T ), the sequence {x k } ∞ k=0 generated by the BSKM2 method converges linearly in expectation to the least-Euclidean-norm solution Proof Following an analogous argument to Theorem 1, we can obtain Now, taking expectation of both sides, we have which is the desired result.
Remark 7 According to Lemma 1, we have λ min (A T A) , which together with the facts |τ h | < m and η < m yield That is, the convergence factor of the BSKM2 method is indeed smaller than 1.
where t k is the iteration index of the SKM method. Thus, similar to the analysis in Remark 4, we immediately obtain that the BSKM2 method converges at least as quickly as the SKM method. In addition, as we also get that the BSKM2 method converges at least as quickly as the Motzkin method.
Remark 9 From Algorithms 2 and 3, we can find that both the update rules of the two methods need to compute the Moore-Penrose pseudoinverse of the row submatrix A I k or A J k in each iteration, which may be expensive. To avoid computing the Moore-Penrose pseudoinverse, we can adopt the following pseudoinverse-free iteration format: where w i represents the weight corresponding to the ith row. See [25][26][27][28] for a detailed discussion on this topic.

Numerical experiments
In this section, we mainly compare our two block sampling Kaczmarz-Motzkin methods (BSKM1, BSKM2) and the SKM method in terms of the iteration numbers (denoted as "Iteration") and computing time in seconds (denoted as "CPU time(s)") using the matrix A ∈ R m×n from two sets. One is generated randomly by using the MATLAB function randn, and the other one contains the matrices in Table 1 from the University of Florida sparse matrix collection [29]. To compare these methods more clearly, we set η = β . In addition, for the sparse matrices, the density is defined as follows: density = number of nonzero of an m × n matrix mn . In all the following specific experiments, we generate the solution vector x ⋆ ∈ R n using the MATLAB function randn, and set the vector b ∈ R m to be b = Ax ⋆ . All experiments start from an initial vector x 0 = 0, and terminate once the relative solution error (RES), defined by , satisfies RES < 10 −6 , or the number of iteration steps exceeds 200,000. For the first class of matrices, that is, the matrices generated randomly, the numerical results of the three methods are presented in Figs. 1-6. Figs. 1-4 show that, with different values of β , the number of iterative steps and computing time of our two methods are less than those of the SKM method. From Figs. 5-6, we find that the BSKM1 and BSKM2 methods vastly outperform the SKM method in terms of the iterations and computing time when the problems are large-scale.
For the second class of matrices, that is, the sparse matrices from [29], we plot the numerical results on Iteration and CPU time(s) versus β in Figs. 7-12. From these figures, we find that the similar results shown in Figs. 1-4. That is, the BSKM1 and BSKM2 methods converge faster and need less runtime for the same accuracy.
Therefore, in all the cases, our block sampling Kaczmarz-Motzkin methods, i.e., BSKM1 and BSKM2 methods, outperform the SKM method. This is mainly because the latter only updates one index in each iteration while the former enforces multiple greedy indices simultaneously.