Optimization Online


"A Note on the Behavior of the Randomized Kaczmarz Algorithm of Strohmer and Vershynin"

Yair Censor(yair***at***math.haifa.ac.il)
Gabor Herman(gabortherman***at***yahoo.com)
Ming Jiang(ming-jiang***at***pku.edu.cn)

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
Entry Accepted: 07/20/2009
Entry Last Modified: 07/20/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society