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_35: The iterative method for solving system of linear equations, due to Kaczmarz [2], is investigated. It is shown that the method works well for both singular and non-singular systems and it determines the affine space formed by the solutions if they exist. The method also provides an iterative procedure for computing a generalized inverse of a matrix.
@cite_37: The Kaczmarz algorithm is an iterative method for reconstructing a signal x∈ℝ d from an overcomplete collection of linear measurements y n =〈x,φ n 〉, n≥1. We prove quantitative bounds on the rate of almost sure exponential convergence in the Kaczmarz algorithm for suitable classes of random measurement vectors ( n _ n=1 ^ R ^ d ). Refined convergence results are given for the special case when each φ n has i.i.d. Gaussian entries and, more generally, when each φ n ∥φ n ∥ is uniformly distributed on ( S ^ d-1 ). This work on almost sure convergence complements the mean squared error analysis of Strohmer and Vershynin for randomized versions of the Kaczmarz algorithm.
@cite_33: 
@cite_1: The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Ax≈b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.
@cite_19: The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of in the context of reconstructing bandlimited functions from nonuniform sampling.
@cite_2: We investigate the behavior of Kaczmarz's method with relaxation for inconsistent systems. We show that when the relaxation parameter goes to zero, the limits of the cyclic subsequences generated by the method approach a weighted least squares solution of the system. This point minimizes the sum of the squares of the Euclidean distances to the hyperplanes of the system. If the starting point is chosen properly, then the limits approach the minimum norm weighted least squares solution. The proof is given for a block-Kaczmarz method.
@cite_16: We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum @math -norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.
@cite_25: Abstract Let the linear system Ax = b be rectangular but solvable. If A is a large sparse matrix, then one possibility to solve the system is to use the iterative method of Kaczmarz. Even in the case when the system is unsolvable, this method is applicable if the relaxation parameters are kept fixed in a certain interval. To get a meaningful result, however, one has to apply strong underrelaxation. We give an interpretation of the limit in terms of a generalized inverse of A and derive bounds with respect to the least-squares solution. Using a result of Buoni and Varga, we estimate the speed of convergence. It is further shown that the eigenvalues of the iteration matrix are nearly real numbers, and we propose to use Chebyshev acceleration. This results in a significant speedup.
@cite_12: There exist many classes of block-projections algorithms for approximating solutions of linear least-squares problems. Generally, these methods generate sequences convergent to the minimal norm least-squares solution only for consistent problems. In the inconsistent case, which usually appears in practice because of some approximations or measurements, these sequences do no longer converge to a least-squares solution or they converge to the minimal norm solution of a “perturbed” problem. In the present paper, we overcome this difficulty by constructing extensions for almost all the above classes of block-projections methods. We prove that the sequences generated with these extensions always converge to a least-squares solution and, with a suitable initial approximation, to the minimal norm solution of the problem. Numerical experiments, described in the last section of the paper, confirm the theoretical results obtained.
Recently, Strohmer and Vershynin @cite_19 derived the first provable convergence rate of the Kaczmarz method, showing that when each row is selected with probability proportional to its norm the method exhibits the expected linear convergence of . This work was extended to the inconsistent case in @cite_1 , which shows linear convergence to within some fixed radius of the least squares solution. The almost-sure guarantees were recently derived by Chen and Powell @cite_37 . To break the convergence barrier, relaxation parameters can be introduced, so that each iterate is over or under projected onto each solution space. Whitney and Meany prove that if the relaxation parameters tend to zero that the iterates converge to the least squares solution @cite_33 . Further results using relaxation have also been obtained, see for example @cite_2 @cite_35 @cite_25 @cite_16 . An alternative to relaxation parameters was recently proposed by Zouzias and Freris @cite_16 as the REK method described by . Rather than alter the projection step, motivated by ideas of Popa @cite_12 they introduce a secondary step which aims to reduce the residual.