Almost Sure Convergence of the Kaczmarz Algorithm with Random Measurements

摘要

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) ~∞ ? ?~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/{double pipe}φ_n{double pipe} 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.