The Dual Kaczmarz Algorithm

The Kaczmarz algorithm is an iterative method for solving a system of linear equations. It can be extended so as to reconstruct a vector x in a (separable) Hilbert space from the inner-products {< x,phi n & rang;}. The Kaczmarz algorithm defines a sequence of approximations from the sequence {< x,phi n & rang;}; these approximations only converge to x when {phi n} is effective. We dualize the Kaczmarz algorithm so that x can be obtained from {< x,phi n & rang;} by using a second sequence {psi n}in the reconstruction. This allows for the recovery of x even when the sequence {phi n} is not effective; in particular, our dualization yields a reconstruction when the sequence {phi n} is almost effective. We also obtain some partial results characterizing when the sequence of approximations from {< x,phi n & rang;} using {psi n} converges to x, in which case {(phi n,psi n)} is called an effective pair.