Deterministic Versus Randomized Kaczmarz Iterative Projection
From MaRDI portal
Abstract: Kaczmarz's alternating projection method has been widely used for solving a consistent (mostly over-determined) linear system of equations Ax=b. Because of its simple iterative nature with light computation, this method was successfully applied in computerized tomography. Since tomography generates a matrix A with highly coherent rows, randomized Kaczmarz algorithm is expected to provide faster convergence as it picks a row for each iteration at random, based on a certain probability distribution. It was recently shown that picking a row at random, proportional with its norm, makes the iteration converge exponentially in expectation with a decay constant that depends on the scaled condition number of A and not the number of equations. Since Kaczmarz's method is a subspace projection method, the convergence rate for simple Kaczmarz algorithm was developed in terms of subspace angles. This paper provides analyses of simple and randomized Kaczmarz algorithms and explain the link between them. It also propose new versions of randomization that may speed up convergence.
This page was built for publication: Deterministic Versus Randomized Kaczmarz Iterative Projection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6253322)
