  


"A Note on the Behavior of the Randomized Kaczmarz Algorithm of Strohmer and Vershynin"
Yair Censor(yairmath.haifa.ac.il) Abstract: In a recent paper by Strohmer and Vershynin (J. Fourier Anal. Appl. 15:262–278, 2009) a “randomized Kaczmarz algorithm” is proposed for solving consistent systems of linear equations {ai, x = bi }m i=1. In that algorithm the next equation to be used in an iterative Kaczmarz process is selected with a probability proportional to ai2. The paper illustrates the superiority of this selection method for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values. In this note we point out that the reported success of the algorithm of Strohmer and Vershynin in their numerical simulation depends on the specific choices that are made in translating the underlying problem, whose geometrical nature is “find a common point of a set of hyperplanes”, into a system of algebraic equations. If this translation is carefully done, as in the numerical simulation provided by Strohmer and Vershynin for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values, then indeed good performance may result. However, there will always be legitimate algebraic representations of the underlying problem (so that the set of solutions of the system of algebraic equations is exactly the set of points in the intersection of the hyperplanes), for which the selection method of Strohmer and Vershynin will perform in an inferior manner. Keywords: Kaczmarz algorithm, Projection method, Rate of convergence Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Applications  Science and Engineering (Biomedical Applications ) Citation: Journal of Fourier Analysis and Applications, accepted for publication. Download: [PDF] Entry Submitted: 07/20/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  