The Kaczmarz method is an iterative method for solving overcomplete linear systems of equations Ax=b. The randomized version of the Kaczmarz method put forth by Strohmer and Vershynin iteratively projects onto a randomly chosen solution space given by a single row of the matrix A and converges exponentially in expectation to the solution of a consistent system. In this paper we analyze two block versions of the method each with a randomized projection, that converge in expectation to the least squares solution of inconsistent systems. Our approach utilizes a paving of the matrix A to guarantee exponential convergence, and suggests that paving yields a significant improvement in performance in certain regimes. The proposed method is an extension of the block Kaczmarz method analyzed by Needell and Tropp and the Randomized Extended Kaczmarz method of Zouzias and Freris. The contribution is thus two-fold; unlike the standard Kaczmarz method, our methods converge to the least-squares solution of inconsistent systems, and by using appropriate blocks of the matrix this convergence can be significantly accelerated. Numerical experiments suggest that the proposed algorithm can indeed lead to advantages in practice.
@cite_43: In some previous papers the author extended two algorithms proposed by Z. Kovarik for approximate orthogonalization of a finite set of linearly independent vectors from a Hilbert space, to the case when the vectors are rows (not necessary linearly independent) of an arbitrary rectangular matrix. In this paper we describe combinations between these two methods and the classical Kaczmarz’s iteration. We prove that, in the case of a consistent least-squares problem, the new algorithms so obtained converge to any of its solutions (depending on the initial approximation). The numerical experiments described in the last section of the paper on a problem obtained after the discretization of a first kind integral equation ilustrate the fast convergence of the new algorithms.
@cite_29: The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem.
@cite_26: In this paper we describe an iterative algorithm for numerical solution of ill-conditioned inconsistent symmetric linear least-squares problems arising from collocation discretization of first kind integral equations. It is constructed by successive application of Kaczmarz Extended method and an appropriate version of Kovarik’s approximate orthogonalization algorithm. In this way we obtain a preconditioned version of Kaczmarz algorithm for which we prove convergence and make an analysis concerning the computational effort per iteration. Numerical experiments are also presented. AMS Subject Classification : 65F10 , 65F20. 1 Kaczmarz extended and Kovarik algorithms Beside many papers and books concerned with the qualitative analysis of classes of linear and nonlinear operators and operatorial equations, professor Dan Pascali also analysed the possibility to approximate solutions for some of them (see e.g. [5], [6]). This paper is written in the same direction, by considering iterative methods for numerical solution of first kind integral equations
@cite_20: In this paper we present an algorithm which, for a given (sparse) matrix, constructs a partition of its set of row-indices, such that each subset of this partition (except the last one obtained) contains indices which correspond to mutually orthogonal rows. We then use such decompositions in some classes of block-projections methods, previously extended by the author to general inconsistent linear least-squares problems. Numerical experiments on an inconsistent and rank-deficient least-squares model problem are described in the last section of the paper.
To use block methods effectively, one needs to obtain a suitable partition of the rows (and or columns). Popa constructs such partitions by creating orthogonal blocks @cite_20 @cite_43 @cite_26 , whereas Needell and Tropp promote the use of row pavings to construct the partition @cite_29 .