###### 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