|
|
Comparison of direct regularization methods based on least squares for problems corrupted by noise
Cepko, Tomáš ; Hnětynková, Iveta (advisor) ; Kučera, Václav (referee)
In this thesis we are going to deal with the inverse linear approximation problem Ax ≈ b, where our goal is to find the best approximation x of the unknown exact solution. We are going to especially focus on the so-called rank-deficient and ill-posed problems, which are very ill-conditioned and sensitive to possible random noise present in b. To solve these problems, we must use regularization methods, which suppress this sensitivity. The main goal of this thesis is to get a comprehensive overview of direct methods T-SVD, T- TLS and Tikhonov regularization, and analyse their close connection with classical least squares methods. One possible approach is to formulate these regularization methods as so-called filtering. In this way we implement them for numerical experiments. This thesis will also include a numerical comparision of these methods for selected problems from the Regularization Toolbox and in the application problem of image reconstruction. 1
|
|
|
Approximation by the TLS method: linear data fitting for problems with unprecise models
Pokorná, Kateřina ; Hnětynková, Iveta (advisor) ; Duintjer Tebbens, Erik Jurjen (referee)
In this thesis, we concern ourselves with the linear approximation problem, where errors in both the observation and the data are considered. We focus on the total least squares problem (TLS), which may be used in solving such tasks. We summarise ba- sic theory of the existence and uniqueness of the TLS solution, present the classic TLS algorithm and examine some possible complications, which may appear during its imple- mentation. Furthermore, we shall study the singular value decomposition (SVD), which is used in constructing the TLS solution. As the SVD is rather difficult to compute, we discuss one of the possible methods of approximating only its part necessary for the construction of the TLS solution, the so called singular triplets. This method is based on Golub-Kahan iterative bidiagonalization. Finally, we shall test how the quality of the approximation of the smallest singular triplets influences the computed TLS solution. 1
|
|
|
Noise propagation in algorithms constructing krylov regularization bases for the solution of inverse problems
Kašpar, Jakub ; Hnětynková, Iveta (advisor) ; Plešinger, Martin (referee)
In this thesis we consider a linear inverse problem Ax ≈ b with a smoothing operator A and a right-hand side vector b polluted by unknown noise. To find good approximation of x we can use large family of iterative regularization methods, which compute the approximate solution by projection onto a Krylov subspace of small dimension. Even though this projection has filtering property, the high frequency noise propagates to the Krylov basis, which causes semiconvergence of the methods. The knowledge of intensity of noise propagation is therefore necessary to find reasonably precise approximation of the solution. In the thesis we study noise propagation in the Golub-Kahan iterative bidiagonali- zation and in the Lanczos algorithm, which construct the required Krylov subspace for LSQR and MINRES methods. For both methods, we analyze a noise-amplifying coef- ficient, for which we derive explicit formulas in both cases. For the Golub-Kahan bidi- agonalization, this analysis summarizes the theory from multiple sources. Analysis for the Lanczos algorithm is original. For both methods, we derive explicit relations between noise-amplifying coefficients and residual norms. Several numerical experiments are pre- sented to demonstrate properties of both algorithms. Impact of noise propagation on true errors and influence...
|
|
|
Analysis of Krylov regularization methods for image deblurring problems
Machalová, Markéta ; Hnětynková, Iveta (advisor) ; Tichý, Petr (referee)
The diploma thesis deals with the construction and properties of image deblurring problems along with approaches to their solution. We focus on Krylov subspace methods LSQR, GMRES and RRGMRES, which are known for their regularization properties. We analyze the convergence behavior of the methods, the time efficiency and the quality of the approximate solution. Next, we present block Krylov subspace methods, which are not well explored in the field of image processing. These methods solve a system of linear equations with a multiple right-hand side and were created by the generalizing Krylov subspace methods, which are used for solving linear equations with a vector right-hand side. Finally, we perform numerical experiments investigating the influence of various factors on the results of image deblurring and the time complexity of individual methods, and we compare block and non-block methods. 1
|
|
|
Mixed Precision in Uncertainty Quantification Methods
Martínek, Josef ; Carson, Erin Claire (advisor) ; Hnětynková, Iveta (referee)
This work is concerned with analysing and exploiting mixed precision arithmetic in un- certainty quantification methods with emphasis on the multilevel Monte Carlo (MLMC) method. Although mixed precision can improve performance, it should be used carefully to avoid unwanted effects on the solution accuracy. We provide a rigorous analysis of uncertainty quantification methods in finite precision arithmetic. Based on this analysis, we exploit mixed precision arithmetic in uncertainty quantification methods to improve runtime while preserving the overall error. We begin by stating the model problem, an elliptic PDE with random coefficients and a random right-hand side. Such a problem arises, for example, in uncertainty quantification for groundwater flow. Our focus is on approximating a quantity of interest given as the expected value of a functional of the solution of the PDE problem. To this end, we use the conforming finite element method for approximation in the spatial variable and the MLMC method for approximation of the expected value. We provide a novel rigorous analysis of the MLMC method in finite precision arithmetic and based on this we formulate an adaptive algorithm which determines the optimal precision value on each level of discretisation. To our knowledge, this is a new approach. Our...
|
|
|
Iterative methods for Tichonov regularization with generalized regularization terms
Kučerová, Andrea ; Hnětynková, Iveta (advisor) ; Carson, Erin Claire (referee)
The aim of this thesis is to study hybrid methods for solving ill-posed linear inverse problems corrupted by white noise. These approaches are based on the combination of iterative Krylov subspace methods and the Tichonov regularization with a general regularization term. We explain the basic properties of ill-posed problems, the idea of regularization, the role of the regularization term to enforce desirable properties to the solution and the theoretical background of Standard and General Tichonov minimization. Then we explain shift invariance of Krylov subspaces. This allows us to describe a hybrid approach where the full size problem is first projected onto a Krylov subspace of a smaller dimension and then the Tichonov minimization is applied to the small projected problem. We focus on the regularization based on the finite difference approximation of derivatives of the solution. The well known regularization terms constructed from forward differences for the first and the second derivative are summarized, then we use the Taylor expansion to construct finite differences of higher orders of precision. We incorporate different variants of boundary conditions. Then the impact of the order of precision of the finite difference schemes on the quality of the solution is studied. In the experiments we use the...
|
|
|
Algebraic view on the PCA method in selected applications
Hammerbauer, Tomáš ; Hnětynková, Iveta (advisor) ; Tichý, Petr (referee)
This thesis deals with describing algebraic and statistic view on Principal component analysis and the way of exporting important variables. Basic properties of the singular value decomposition are introduced and the best rank k aproximation of a matrix is de- rived. Then, a conection between PCA and singular value decomposition is described. At the end, PCA is ilustrated on two numerical experiments on image databases. It is shown, how we can aproximate images simillar to the elements of the database. Theo- retical foundations for the experiments are presented and then they are implemented in the Matlab enviroment. 1
|
|
|
Approximate Polynomial Greatest Common Divisor
Eliaš, Ján ; Zítko, Jan (advisor) ; Hnětynková, Iveta (referee)
Title: Approximate Polynomial Greatest Common Divisor Author: Ján Eliaš Department: Department of Numerical Mathematics, MFF UK Supervisor: Doc. RNDr. Jan Zítko, CSc., Department of Numerical Mathematics, MFF UK Abstract: The computation of polynomial greatest common divisor (GCD) ranks among basic algebraic problems with many applications. The Euclidean algorithm is the oldest and usual technique for computing GCD. However, the GCD computation problem is ill-posed, particularly when some unknown noise is applied to the polyno- mial coefficients. Since the Euclidean algorithm is unstable, new methods have been extensively studied in recent years. Methods based on the numerical rank estimation represent one group of current meth- ods. Their disadvantage is that the numerical rank cannot be computed reliably due to the sensitivity of singular values on noise. The aim of the work is to overcome the ill-posed sensitivity of GCD computation in the presence of noise. Keywords: AGCD, Sylvester matrix, numerical rank, TLS
|
|
| |
|
|
Numerical Methods in Discrete Inverse Problems
Kubínová, Marie ; Hnětynková, Iveta (advisor) ; Gazzola, Silvia (referee) ; Meurant, Gerard (referee)
Title: Numerical Methods in Discrete Inverse Problems Author: Marie Kubínová Department: Department of Numerical Mathematics Supervisor: RNDr. Iveta Hnětynková, Ph.D., Department of Numerical Mathe- matics Abstract: Inverse problems represent a broad class of problems of reconstruct- ing unknown quantities from measured data. A common characteristic of these problems is high sensitivity of the solution to perturbations in the data. The aim of numerical methods is to approximate the solution in a computationally efficient way while suppressing the influence of inaccuracies in the data, referred to as noise, that are always present. Properties of noise and its behavior in reg- ularization methods play crucial role in the design and analysis of the methods. The thesis focuses on several aspects of solution of discrete inverse problems, in particular: on propagation of noise in iterative methods and its representation in the corresponding residuals, including the study of influence of finite-precision computation, on estimating the noise level, and on solving problems with data polluted with noise coming from various sources. Keywords: discrete inverse problems, iterative solvers, noise estimation, mixed noise, finite-precision arithmetic - iii -
|
guest ::
