Options
Solving regularized total least squares problems based on eigenproblems
Citation Link: https://doi.org/10.15480/882.870
Other Titles
Lösen von Regularisierten totalen Ausgleichsproblemen mit Hilfe von Eigenwertproblemen
Publikationstyp
Doctoral Thesis
Publikationsdatum
2010
Sprache
English
Author
Advisor
Voß, Heinrich
Title Granting Institution
Technische Universität Hamburg
Place of Title Granting Institution
Hamburg
Examination Date
2010-05-13
Institut
Citation
Solving Regularized Total Least Squares Problems Based on Eigenproblems, Berlin, dissertation.de – Verlag im Internet GmbH, 2010, S. 177
In the first part of the thesis we review basic knowledge of regularized least squares problems and present a significant acceleration of an existing method for the solution of trust-region problems.
In the second part we present the basic theory of total least squares (TLS) problems and give an overview of possible extensions. Regularization of TLS problems by truncation and bidiagonalization approaches are briefly covered. Several approaches for solving the Tikhonov TLS problem based on Newton’s method are mentioned, which lead to a converging sequence of linear systems.
The emphasis of the thesis is on quadratically constrained TLS (RTLS) problems. Two different iterative concepts for the solution of the first-order condition are analyzed. The first iteration results in a sequence of quadratic problems while the second concept leads to a sequence of linear eigenvalue problems. For a fixed point iteration based on quadratic eigenvalue problems, i.e. the RTLSQEP method, the global convergence to the RTLS solution is proven. With the characterization of the rightmost eigenvalue of the QEPs the RTLS solution can be described via a generalized trust-region problem. The second concept has been studied in detail as well, i.e. the RTLSEVP method. To ensure convergence it was necessary to generalize the function g. The properties of this function have been heavily analyzed, which lead to a deeper understanding of the RTLS solution: It can also be characterized via the solution of a TLS problem.
The RTLSQEP and RTLSEVP algorithm for solving the RTLS problem are shown to be very efficient when combined with iterative projection methods in the inner loop. Since a sequence of convergent problems has to be solved it turns out that the Nonlinear Arnoldi method is the method of choice, because it is able to recycle most of the information during the iterative process. The computational complexity of the proposed approaches is kept at the order of matrix-vector multiplications. We give a detailed description of an efficient implementation of the different parts of the algorithms.
Two efficient algorithms for evaluating the L-curve at discrete points are presented. Since setting up the L-curve requires solving a sequence of RTLS problems the advantage of the Nonlinear Arnoldi method is even more apparent:
Recycling the search space, not only within one RTLS problem but throughout the whole sequence.
In the second part we present the basic theory of total least squares (TLS) problems and give an overview of possible extensions. Regularization of TLS problems by truncation and bidiagonalization approaches are briefly covered. Several approaches for solving the Tikhonov TLS problem based on Newton’s method are mentioned, which lead to a converging sequence of linear systems.
The emphasis of the thesis is on quadratically constrained TLS (RTLS) problems. Two different iterative concepts for the solution of the first-order condition are analyzed. The first iteration results in a sequence of quadratic problems while the second concept leads to a sequence of linear eigenvalue problems. For a fixed point iteration based on quadratic eigenvalue problems, i.e. the RTLSQEP method, the global convergence to the RTLS solution is proven. With the characterization of the rightmost eigenvalue of the QEPs the RTLS solution can be described via a generalized trust-region problem. The second concept has been studied in detail as well, i.e. the RTLSEVP method. To ensure convergence it was necessary to generalize the function g. The properties of this function have been heavily analyzed, which lead to a deeper understanding of the RTLS solution: It can also be characterized via the solution of a TLS problem.
The RTLSQEP and RTLSEVP algorithm for solving the RTLS problem are shown to be very efficient when combined with iterative projection methods in the inner loop. Since a sequence of convergent problems has to be solved it turns out that the Nonlinear Arnoldi method is the method of choice, because it is able to recycle most of the information during the iterative process. The computational complexity of the proposed approaches is kept at the order of matrix-vector multiplications. We give a detailed description of an efficient implementation of the different parts of the algorithms.
Two efficient algorithms for evaluating the L-curve at discrete points are presented. Since setting up the L-curve requires solving a sequence of RTLS problems the advantage of the Nonlinear Arnoldi method is even more apparent:
Recycling the search space, not only within one RTLS problem but throughout the whole sequence.
Schlagworte
eigenvalueproblem
total least squares
regularization
efficient algorithms
Loading...
Name
Lampe_Joerg.pdf
Size
1.66 MB
Format
Adobe PDF