Abstract
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.
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.
- Content Type Journal Article
- DOI 10.1007/s10543-010-0265-5
- Authors
- Deanna Needell, Stanford University Department of Statistics Stanford CA 94305-4065 USA
- Journal BIT Numerical Mathematics
- Online ISSN 1572-9125
- Print ISSN 0006-3835
No hay comentarios:
Publicar un comentario
Nota: solo los miembros de este blog pueden publicar comentarios.