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 ({langle x, phi _{n} rangle }). The Kaczmarz algorithm defines a sequence of approximations from the sequence ({langle x, phi _{n} rangle }); these approximations only converge to (x) when ({phi _{n}}) is effective. We dualize the Kaczmarz algorithm so that (x) can be obtained from ({langle x, phi _{n} rangle }) 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 ({langle x, phi _{n} rangle }) using ({psi _{n}}) converges to (x), in which case ({(phi _{n}, psi _{n})}) is called an effective pair.