  The Kaczmarz method is an iterative algorithm for solving systems of linear
equalities and inequalities, that iteratively projects onto these constraints.
Recently, Strohmer and Vershynin [J. Fourier Anal. Appl., 15(2):262-278, 2009]
gave a non-asymptotic convergence rate analysis for this algorithm, spurring
numerous extensions and generalizations of the Kaczmarz method. Rather than the
randomized selection rule analyzed in that work, in this paper we instead
discuss greedy and approximate greedy selection rules. We show that in some
applications the computational costs of greedy and random selection are
comparable, and that in many cases greedy selection rules give faster
convergence rates than random selection rules. Further, we give the first
multi-step analysis of Kaczmarz methods for a particular greedy rule, and
propose a provably-faster randomized selection rule for matrices with many
pairwise-orthogonal rows.
