liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On Diagonally Relaxed Orthogonal Projection Methods
Department of Mathematics, University of Haifa, Mt. Carmel, Haifa, Israel.
Linköping University, Department of Mathematics, Scientific Computing. Linköping University, The Institute of Technology.
Department of Computer Science, The Graduate Center, City University of New York, New York, USA.
Linköping University, Department of Mathematics, Scientific Computing. Linköping University, The Institute of Technology.
2008 (English)In: SIAM Journal on Scientific Computing, ISSN 1064-8275, E-ISSN 1095-7197, Vol. 30, no 1, 473-504 p.Article in journal (Refereed) Published
Abstract [en]

We propose and studya block-iterative projection method for solving linear equations and/or inequalities.The method allows diagonal componentwise relaxation in conjunction with orthogonalprojections onto the individual hyperplanes of the system, and isthus called diagonally relaxed orthogonal projections (DROP). Diagonal relaxation hasproven useful in accelerating the initial convergence of simultaneous andblock-iterative projection algorithms, but until now it was available onlyin conjunction with generalized oblique projections in which there isa special relation between the weighting and the oblique projections.DROP has been used by practitioners, and in this papera contribution to its convergence theory is provided. The mathematicalanalysis is complemented by some experiments in image reconstruction fromprojections which illustrate the performance of DROP.

Place, publisher, year, edition, pages
Philadelphia, PA, United States: Society for Industrial and Applied Mathematics, 2008. Vol. 30, no 1, 473-504 p.
Keyword [en]
block iteration, convex feasibility, diagonal relaxation, projection methods, simultaneous algorithms
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-13235DOI: 10.1137/050639399ISI: 000208048600006OAI: oai:DiVA.org:liu-13235DiVA: diva2:18093
Available from: 2008-05-21 Created: 2008-05-21 Last updated: 2017-12-13Bibliographically approved
In thesis
1. Algebraic Reconstruction Methods
Open this publication in new window or tab >>Algebraic Reconstruction Methods
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1186
Keyword
iterative methods; image reconstruction; ART; Cimmino; Kaczmarz; Landweber; sequential iteration; simultaneous iteration; block iteration; semi-convergence; relaxation parameters; stopping rules; discrepancy principle
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-11670 (URN)978-91-7393-888-4 (ISBN)
Public defence
2008-06-10, Glashuset, Hus B, Ingång 23, Department of Mathematics, Linköping University, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2008-05-21 Created: 2008-05-21 Last updated: 2009-05-08
2. The Use of Landweber Algorithm in Image Reconstruction
Open this publication in new window or tab >>The Use of Landweber Algorithm in Image Reconstruction
2007 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

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 modelled using the Radon transform. After expanding the solution into a finite series of basis functions a large, sparse and ill-conditioned linear system arises. 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 typically 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 phenomena is called semi-convergence. It is therefore vital to find good stopping rules for the iteration.

We describe a class of stopping rules for Landweber type iterations for solving linear inverse problems. The class includes, e.g., the well known discrepancy principle, and also the monotone error rule. We also 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.

Abstract [sv]

Vi betraktar lösning av sådana linjära ekvationssystem som uppkommer vid diskretisering av inversa problem. Dessa problem karakteriseras av att den sökta informationen inte direkt kan mätas. Ett välkänt exempel utgör datortomografi. Där mäts hur mycket strålning som passerar genom ett föremål som belyses av en strålningskälla vilken intar olika vinklar i förhållande till objektet. Syftet är förstås att generera bilder av föremålets inre (i medicinska tillämpngar av det inre av kroppen). Vi studerar en klass av iterativa lösningsmetoder för lösning av ekvationssystemen. Metoderna tillämpas på testdata från bildrekonstruktion och jämförs med andra föreslagna iterationsmetoder. Vi gör även en konvergensanalys för olika val av metod-parametrar.

När man använder en iterativ metod startar man med en begynnelse approximation som sedan gradvis förbättras. Emellertid är inversa problem känsliga även för relativt små fel i uppmätta data. Detta visar sig i att iterationerna först förbättras för att senare försämras. Detta fenomen, s.k. ’semi-convergence’ är väl känt och förklarat. Emellertid innebär detta att det är viktigt att konstruera goda stoppregler. Om man avbryter iterationen för tidigt fås dålig upplösning och om den avbryts för sent fås en oskarp och brusig bild.

I avhandligen studeras en klass av stoppregler. Dessa analyseras teoretiskt och testas på mätdata. Speciellt föreslås en inlärningsförfarande där stoppregeln presenteras med data där det korrekra värdet på stopp-indexet är känt. Dessa data används för att bestämma en viktig parameter i regeln. Sedan används regeln för nya okända data. En sådan tränad stoppregel visar sig fungera väl på testdata från bildrekonstruktionsområdet.

Place, publisher, year, edition, pages
Matematiska institutionen, 2007. 13 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1311
Keyword
convex feasibility, projection methods, simultaneous algorithms, iterative methods, stopping rules, semi-convergence
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-10030 (URN)978-91-85831-89-0 (ISBN)
Presentation
2007-06-12, kompakta rummet, B23, Campus Valla, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2007-11-09 Created: 2007-11-09 Last updated: 2010-01-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textLink to Licentiate thesisLink to Ph.D. thesis

Authority records BETA

Elfving, TommyNikazad, Touraj

Search in DiVA

By author/editor
Elfving, TommyNikazad, Touraj
By organisation
Scientific ComputingThe Institute of Technology
In the same journal
SIAM Journal on Scientific Computing
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 700 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf