key: cord-0045729-5pf2u12i
authors: Huang, Xinyin; Liu, Gang; Niu, Qiang
title: Remarks on Kaczmarz Algorithm for Solving Consistent and Inconsistent System of Linear Equations
date: 2020-06-15
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50417-5_17
sha: 38d340bb6946a6fd1ea0359f87c1f2466abb0633
doc_id: 45729
cord_uid: 5pf2u12i

In this paper we consider the classical Kaczmarz algorithm for solving system of linear equations. Based on the geometric relationship between the error vector and rows of the coefficient matrix, we derive the optimal strategy of selecting rows at each step of the algorithm for solving consistent system of linear equations. For solving perturbed system of linear equations, a new upper bound in the convergence rate of the randomized Kaczmarz algorithm is obtained.

Kaczmarz algorithm [28] is an iterative method for solving system of linear equations of the form

where A ∈ R m×n has full column rank, m ≥ n and b ∈ R m . In the consistent case, the solution of (1) can be regarded as the coordinate of the common point of hyperplanes defined by each single equation in (1):

where a T i , i = 1, 2, · · · , m, denotes the ith row of A and b i is the ith element of vector b.

The idea of the Kaczmarz type algorithms is to exploit the geometric structure of the problem (1) , and the using a sequential of projections to seek the solution. The recursive process can be formulated as follows. Let x 0 be an initial guess to the solution of (1), then the classical Kaczmarz algorithm iteratively generates a sequence of approximate solutions x k by the recursive formula:

where i = mod(k, m) + 1. For a given x k , from (3) we can see that x k+1 satisfies the ith equation in (1), i.e., a T i x k+1 = b i . The updating formula (3) implicitly produces a solution to the following constraint optimization problem [21, 37] min

which is equivalent to finding the projection of x k from the hyperplane P i . Two geometric explanations of the above process can be illustrated by Fig. 1 : By comparing the projection processes displayed in Fig. 1 , it is natural to have the intuition that convergence of the classical Kaczmarz algorithm highly depends on the geometric positions of the associated hyperplanes. If the normal vectors of every two successive hyperplanes keep reasonably large angles, the convergence of the classical Kaczmarz algorithm will be fast, whereas two nearly parallel consecutive hyperplanes will make the convergence slow down. The Kaczmarz algorithm can be regarded as a special application of famous von Neumann's alternating projection [35] originally distributed in 1933. The fundamental idea can even trace the history back to Schwarz [38] in 1870s.

In the past few years, the Karzmarz algorithm has been interpreted as successive projection methods [4, 7, 8, [11] [12] [13] , which are also known as projection onto convex sets (POCS) [9, 17, 18, [42] [43] [44] in the optimization community. Notice that each iteration of the Kaczmarz algorithm just need O(n) flops and the cost is independent with the number of equations, this type of algorithms are wellsuited to problems with m n. Due to its simplicity and generality, Kaczmarz algorithms find viable applications in the area of image processing and signal process [19, 20, [24] [25] [26] 30, 36] under the name of algebraic reconstruction techniques (ART). Since 1980s, relaxation variants [11, 25, 41] x

and the block versions [3, 33, 34] x

of the Kaczmarz algorithm have been widely investigated, and some fruitful theoretical results have been obtained. In particular, for consistent linear systems, it is shown [5, 21, 31, 39] that the Kaczmarz iterations converges to the least square norm solution x = A † b with any starting vector x 0 in the column space of A T . For inconsistent linear systems, the cyclic subsequences generated by the Kaczmarz algorithm converges to a weighted least squares solution when the relaxation parameter λ k goes to zero [12] .

As indicated in Fig. 1 , convergence of the classical Kaczmarz algorithm depends on the sequence of successive projections, which relies upon the ordering of the rows in the matrix A. In some real applications, it is observed [25, 30] that instead of selecting rows of the matrix A sequentially at each step of the Kaczmarz algorithm, randomly selection can often improve its convergence. Recently, in the remarkable paper [39] , Strohmer and Vershynin proved the rate of convergence for the following randomized Kaczmarz algorithm

. In particular, the following bound on the expected rate of convergence for the randomized Kaczmarz method is proved

where [14] . Due to this pioneering work that characterized the convergence rate for the randomized Kaczmarz algorithms, the idea stimulated considerable interest in this area and various investigations [1, 2, 6, 10, 15] have been performed recently. In particular, some acceleration strategies have been proposed [6, 16, 22] and convergence analysis was performed in [21, 23, 27, 29, 31, 32] . See also [21, 23] for some comments on equivalent interpretations of the randomized Kaczmarz algorithms.

In this section, we consider the case that system of linear equations (1) is consistent and x is a solution. If the ith row is selected at the (k + 1)th iteration of the Kaczmarz algorithm, i.e.,

then x k+1 can be reformulated as

It follows that

and thus

From (7) and (8), we can see that

i.e.,

To this end, let us make the following orthogonal direct sum decomposition

whereâ i = ai ||ai||2 andâ ⊥ i is a normalized vector orthogonal to a i . Then coefficients α and β can be written as

is the angle between the vectors (x − x k ) and a i .

Substituting the above decomposition (11) into (7) gives

It follows that

From (13) we can see that the error norms generated by the Kaczmarz algorithm are monotonically nonincreasing. Moreover, the convergence can be optimized if | sin θ ki | is minimized at every iteration, which is equivalent to selecting the row a i that solves the optimization problem

As x is the unknown solution, the above minimization problems seems unsolvable. However, noting that consistent linear system (1) implies

and x k is fixed at the (k + 1)th iteration. The minimization problem can be tackled by maximizing | cos ∠(x − x k , a j )|, i.e.,

where

It is clear from (14) that the optimal updating strategy for the Kaczmarz algorithm is to select the rowî that satisfies

i.e., the index where r k has the largest entry in absolute value. We refer to the above row selection method as the optimal selecting strategy, and call the Kaczmarz algorithm with the optimal selecting strategy as the optimal Kaczmarz algorithm.

Next, we analyze the convergence of the optimal Kaczmarz algorithm for solving consistent system of linear equations. To simplify the analysis, we introduce two notations θî k = min

where 1 ≤î ≤ m and 1 ≤ p ≤ k. Based on (13), the (k + 1)th error can be bounded as follows

we can theoretically divide the convergence history of the Kaczmarz algorithm into two periods:

-when sin θî p < 1, the algorithm converge exponentially, -when sin θî p = 1, we have max j a T j (x p − x) = 0 and thus, a T j (x p − x) = 0, j = 1, 2, · · · , m. This implies that Ax p = b, i.e., x p solves the system of linear equation (1).

In summary, for solving consistent system of linear equations (1), there exists a theoretical optimal selecting strategy or optimal randomization strategy for Kaczmarz algorithm. With the strategy, the algorithm converges exponentially and will achieve convergence when

Suppose (1) is a consistent system of linear equations and its right hand side is perturbed with a noise vector r as follows:

where (16) can be either consistent or inconsistent. In this section, we give some remarks on the convergence of randomized Kaczmarz algorithm for solving (16) , which was investigated by D. Needell [32] . Firstly, we recall the Lemma 2.2 in [32] .

H i = {x | a i , x = b i }. LetH i be

Remarks: If the Lemma 1 is used to interpret the Kaczmarz algorithm for solving the perturbed and unperturbed equations, we need to introduce a vector a ⊥ i in the as the orthogonal complement of the vector a i , and writex i ∈H i as

where x i is a solution generated by Kaczmarz algorithm for solving the unperturbed equations, and v i is a vector in the orthogonal complement of a i .

Consider the 2 × 2 system of linear equations

and the perturbed equations

i.e., A = 1 1 1 −1 , b = 1 1 and r = 0.5 0.5 .

If we use x 0 = 1 0 as the same initial guess for the perturbed and unperturbed linear system, then

Note that a 1 = 1 1 , ||a 1 || 2 2 = 2 and r 1 = 1 2 . We have

i.e.,x

In order to derive the convergence rate of randomized Kaczmarz algorithm for solving the perturbed linear equations (16) , we need to make use of the established convergence results [39] for the unperturbed linear system (1), together with the relationship between the approximate solutions generated by the Kaczmarz algorithm [39] for perturbed and unperturbed linear equations. In [32] , D. Needell analyzed the convergence rate and error bound of the randomized Kaczmarz algorithm for solving the perturbed linear equations, in which the author take the approximate solution to the perturbed linear equations as the guess for the unperturbed system, which make the derivation process simplified. However, the approximate solutions generated by applying the randomized Kaczmarz algorithm to the perturbed linear system may not converge to the solution of the unperturbed linear system.

In what follows, we will consider the convergence rate of the randomized Kaczmarz algorithm for solving (16) from a different perspective. We try to bound the difference between the solution for the unperturbed linear system (1) and approximate solutions generated by applying the randomized Kaczmarz algorithm to the perturbed linear system.

In the following discussion, we use x k andx k to denote the approximate solutions generated by applying the randomized Kaczmarz algorithm to (1) and (16) , respectively. The recursive formulas can be written as

where the subscript i k ∈ {1, 2, · · · , m} is used to denote that the i k th row is selected with probability

at the kth iteration. Suppose the same initial guess x 0 =x 0 is used as the starting vector. Theñ

and potentially

It follows thatx

In the next iteration, we havẽ

||ai 0 ||2 . Continue the above process, we havẽ

where

. Subtracting x on both sides of (20) gives

Based on Jensen's inequality and (6), we have

where κ(A) = ||A|| F ||A −1 || 2 , with ||A −1 || 2 = inf{M : M ||Ax|| 2 ≥ ||x|| 2 }. Taking norm on both sides of (21) and using triangle inequality, we have

where γ = max 1≤i≤m |ri| ||ai||2 . In conclusion, we have derived the following theorem. Theorem 1. Let A be a matrix full column rank and assume the system Ax = b is consistent. Letx k be the kth iterate of the noisy randomized Kaczmarz method run with Ax b + r, and let a 1 , · · · , a m denote the rows of A. Then we have

where κ(A) = ||A|| F ||A −1 || 2 and γ = max 1≤i≤m |ri| ||ai||2 .

In this paper, we provide a new look at the Kaczmarz algorithm for solving system of linear equations. The optimal row selecting strategy of the Kaczmarz algorithm for solving consistent system of linear equations is derived. The convergence of the randomized Kaczmarz algorithm for solving perturbed system of linear equations is analyzed and a new bound of the convergence rate is obtained from a new perspective.

Randomized Kaczmarz algorithms: exact MSE analysis and optimal sampling probabilities

Kaczmarz algorithm for Tikhonov regularization problem

The block Kaczmarz algorithm based on solving linear systems with arrowhead matrices

On the Meany inequality with applications to convergence ananlysis of several row-action methods

On greedy randomized Kaczmarz method for solving large sparse linear systems

On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems

A direct projection method for sparse linear systems

Projection Methods for Systems of Equations

The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming

A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval

Row-action methods for huge and sparse systems and their applications

Strong underrelaxation in Kaczmarz's method for inconsistent systems

A note on the behaviour of the randomized Kaczmarz algorithm of Strohmer and Vershynin

The probability that a numerical analysis problem is difficult

A sampling Kaczmarz-Motzkin algorithm for linear feasibility

Acceleration of randomized Kaczmarzmethod via the Johnson-Lindenstrauss lemma

New variants of the POCS method using affine subspaces of finite codimension with applications to irregular sampling

On the rate of convergence of the alternating projection method in finite dimensional spaces

Algebraic Reconstruction Techniques (ART) for threedimensional electron microscopy and x-ray photography

Image reconstruction from projections

Randomized iterative methods for linear systems

On the acceleration of Kaczmarz's method for inconsistent linear systems

Rows vs. columns: randomized Kaczmarz or gauss-seidel for ridge regression

Image Reconstruction from Projection, the Fundamentals of the Computerized Tomography

Relaxation methods for image reconstruction

Algebraic reconstruction techniques can be made computationally efficient

Preasymptotic convergence of randomized Kaczmarz method. Inverse Prob

Angenäherte auflösung von systemen linearer gleichungen

Randomized methods for linear constraints: convergence rates and conditioning

Themathematics of Computerized Tomography. SIAM

Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods

Randomized Kaczmarz solver for noisy linear systems

Randomized block Kaczmarz method with projection for solving least squares

Paved with good intentions: analysis of a randomized block Kaczmarz method

This is a mimeographed lecture notes

Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph, UAI

Notes on randomized Kaczmarz, Lecture notes

Ueber einen Grenzübergang durch alternirendes Verfahren. Vierteljahrsschrift der

A randomized Kaczmarz algorithm with exponential convergence

Comments on the randomized Kaczmarz method

Projection method for solving a singular system of linear equations and its applications

Signal deconvolution by projection onto convex sets

Image restoration by the method of convex projections: part 1 theory

Image restoration by the method of convex projections: part 2 applications and numerical results

Randomized extended Kaczmarz for solving least squares