Randomised Kaczmarz Method
Date
2018
Authors
Ma, Yutong
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Solving systems of linear equations, iterative methods are widely used for computing e ciency, though direct methods are robust and accurate. Kaczmarz method was rst introduced in 1973 for square matrices in Euclidean space and was utilised in Computational Tomography, while it has been noticed after a few decades. Although Kaczmarz proved its convergence, the rate of convergence is hard to obtain. Until the recent decade, Strohmer and Vershynin obtained the convergence rate of the randomised version of the Kaczmarz method, which primarily increased the e ciency. In this thesis, we will construct the randomised Kaczmarz method based on original Kaczmarz method, and prove through the properties of convergence rate and pre-asymptotic convergence for both exact input and noised input. Then we introduced an accelerated version of randomised Kaczmarz methods and analysing its converging property. Additionally, we extend the randomised Kaczmarz method into solving systems of linear inequalities, with proving of convergence. After that, we will focus on solving a system of linear equations with sparse solutions. Randomised Kaczmarz method has its advantage of sparse solution problems due to its using less memory in computing. We thus construct a randomised sparse Kaczmarz method by applying soft-threshold function and based on this, we further build an exact-step randomised sparse Kaczmarz method based upon introducing concepts on Bregman distance and projection. Also, we carefully prove the convergence of these methods by adopting concepts and theorems in convex analysis. Moreover, by conducting numerical experiments to the methodologies we investigated on, we nd that randomised Kaczmarz method has surpassed even Conjugate Gradient and Least Square (CGLS) method -a widely known iterative method- when solving overdetermined systems. Also, we nd that the randomised sparse Kaczmarz method has much better performance than randomised Kaczmarz methods. In this way, we proposed a series of randomised versions of the Kaczmarz method, which may be implemented under many real-world problems.
Description
Keywords
Citation
Collections
Source
Type
Thesis (Honours)
Book Title
Entity type
Access Statement
License Rights
Restricted until
Downloads
File
Description