The Dual Kaczmarz Algorithm
- PDF / 773,968 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 180 Views
The Dual Kaczmarz Algorithm Anna Aboud1 · Emelie Curl1 · Steven N. Harding1 · Mary Vaughan1 · Eric S. Weber1
Received: 7 November 2018 / Accepted: 8 February 2019 © Springer Nature B.V. 2019
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, φn }. The Kaczmarz algorithm defines a sequence of approximations from the sequence {x, φn }; these approximations only converge to x when {φn } is effective. We dualize the Kaczmarz algorithm so that x can be obtained from {x, φn } by using a second sequence {ψn } in the reconstruction. This allows for the recovery of x even when the sequence {φn } is not effective; in particular, our dualization yields a reconstruction when the sequence {φn } is almost effective. We also obtain some partial results characterizing when the sequence of approximations from {x, φn } using {ψn } converges to x, in which case {(φn , ψn )} is called an effective pair. Keywords Kaczmarz algorithm · Effective sequence · Frame · Gram matrix · Hilbert space Mathematics Subject Classification (2010) Primary 41A65 · 65D15 · Secondary 42C15 · 65F10
1 Introduction A question of consistent interest in recent years is the conditions under which one can reconstruct a vector in a Hilbert space H given its inner products with some sequence of vectors
B E.S. Weber
[email protected] A. Aboud [email protected] E. Curl [email protected] S.N. Harding [email protected] M. Vaughan [email protected]
1
Department of Mathematics, Iowa State University, 396 Carver Hall, Ames, IA 50011, USA
A. Aboud et al. ∞ {en }∞ n=0 . Sequences of vectors {en }n=0 which yield non-uniqueness of representations and robustness to perturbations have motivated advances in the area of frame theory [2, 3, 5]. There is now renewed interest in iterative reconstructions, e.g. phase retrieval [8, 15], optimization [12], learning theory [10], and computerized tomography [11], to name a few. All of these areas make use of the reconstruction method which we now introduce. In 1937, Stefan Kaczmarz introduced an iterative process of solving linear systems which we now call the Kaczmarz algorithm. Given a linearly dense sequence of unit vectors {en }∞ n=0 in H and x ∈ H, we define a sequence of approximations {xn }∞ n=0 by
x0 = x, e0 e0 , xn = xn−1 + x − xn−1 , en en ,
n ≥ 1.
(1.1)
We say that {en }∞ n=0 is effective if xn − x → 0 for every x ∈ H. Kaczmarz showed in [9] that any periodic, linearly dense sequence of unit vectors {en }∞ n=0 in a finite-dimensional Hilbert space is effective. In [10], Kwapie´n and Mycielski made progress in the infinite-dimensional Hilbert space setting by utilizing the auxiliary sequence {hn }∞ n=0 defined recursively as h0 = e0 , hn = en −
n−1 en , ek hk ,
(1.2)
n ≥ 1.
k=0 ∞ They showed that {en }∞ n=0 is effective if and only if {hn }n=0 is a Parseval frame, namely that, for every x ∈ H,
x2 =
∞ x, hn 2 . n=0
In
Data Loading...
