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.
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 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. 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.