Algebraic Reconstruction Methods
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Ill-posed sets of linear equations typically arise when discretizing certain types of integral transforms. A well known example is image reconstruction, which can be modeled using the Radon transform. After expanding the solution into a finite series of basis functions a large, sparse and ill-conditioned linear system occurs. We consider the solution of such systems. In particular we study a new class of iteration methods named DROP (for Diagonal Relaxed Orthogonal Projections) constructed for solving both linear equations and linear inequalities. This class can also be viewed, when applied to linear equations, as a generalized Landweber iteration. The method is compared with other iteration methods using test data from a medical application and from electron microscopy. Our theoretical analysis include convergence proofs of the fully-simultaneous DROP algorithm for linear equations without consistency assumptions, and of block-iterative algorithms both for linear equations and linear inequalities, for the consistent case.
When applying an iterative solver to an ill-posed set of linear equations the error usually initially decreases but after some iterations, depending on the amount of noise in the data, and the degree of ill-posedness, it starts to increase. This phenomenon is called semi-convergence. We study the semi-convergence performance of Landweber-type iteration, and propose new ways to specify the relaxation parameters. These are computed so as to control the propagated error.
We also describe a class of stopping rules for Landweber-type iteration for solving linear inverse problems. The class includes the well known discrepancy principle, and the monotone error rule. We unify the error analysis of these two methods. The stopping rules depend critically on a certain parameter whose value needs to be specified. A training procedure is therefore introduced for securing robustness. The advantages of using trained rules are demonstrated on examples taken from image reconstruction from projections.
Kaczmarz's method, also called ART (Algebraic Reconstruction Technique) is often used for solving the linear system which appears in image reconstruction. This is a fully sequential method. We examine and compare ART and its symmetric version. It is shown that the cycles of symmetric ART, unlike ART, converge to a weighted least squares solution if and only if the relaxation parameter lies between zero and two. Further we show that ART has faster asymptotic rate of convergence than symmetric ART. Also a stopping criterion is proposed and evaluated for symmetric ART.
We further investigate a class of block-iterative methods used in image reconstruction. The cycles of the iterative sequences are characterized in terms of the original linear system. We define symmetric block-iteration and compare the behavior of symmetric and non-symmetric block-iteration. The results are illustrated using some well-known methods. A stopping criterion is offered and assessed for symmetric block-iteration.
Place, publisher, year, edition, pages
Matematiska institutionen , 2008. , 16 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1186
iterative methods; image reconstruction; ART; Cimmino; Kaczmarz; Landweber; sequential iteration; simultaneous iteration; block iteration; semi-convergence; relaxation parameters; stopping rules; discrepancy principle
National CategoryComputational Mathematics
IdentifiersURN: urn:nbn:se:liu:diva-11670ISBN: 978-91-7393-888-4OAI: oai:DiVA.org:liu-11670DiVA: diva2:18098
2008-06-10, Glashuset, Hus B, Ingång 23, Department of Mathematics, Linköping University, Linköping, 10:15 (English)
Popa, Constantin, Professor
List of papers