The Dual Kaczmarz Algorithm

Abstract

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,{\varphi }_n⟩\}$. The Kaczmarz algorithms defines a sequence of approximations from the sequence $\{⟨x,{\varphi }_n⟩\}$; these approximations only converge to $x$ when $\{{\varphi }_n\}$ is $effective$. We dualize the Kaczmarz algorithm so that $x$ can be obtained from $\{⟨x,{\varphi }_n⟩\}$ by using a second sequence $\{{\psi }_n\}$ in the reconstruction. This allows for the recovery of $x$ even when the sequence $\{{\varphi }_n\}$ is not effective; in particular, our dualization yields a reconstruction when the sequence $\{{\varphi }_n\}$ is $almost$ $effective$. We also obtain some partial results characterizing when the sequence of approximations from $\{⟨x,{\varphi }_n⟩\}$ using $\{{\psi }_n\}$ converges to $x$, in which case $\{({\varphi }_n,{\psi }_n)\}$ is called an $effective$ $pair$.

15 pages