A Randomized Kaczmarz Algorithm with Exponential Convergence |
| |
Authors: | Thomas Strohmer Roman Vershynin |
| |
Institution: | (1) Department of Mathematics, University of California, Davis, CA 95616-8633, USA |
| |
Abstract: | 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 Feichtinger et al. in the context of
reconstructing bandlimited functions from nonuniform sampling.
T. Strohmer was supported by NSF DMS grant 0511461. R. Vershynin was supported by the Alfred P. Sloan Foundation and by NSF
DMS grant 0401032. |
| |
Keywords: | Kaczmarz algorithm Randomized algorithm Random matrix Convergence rate |
本文献已被 SpringerLink 等数据库收录! |
|