Advances in Bregman-Kaczmarz Methods: Accelerations and Inconsistency

Kaczmarz's methods, rooted in iterative algorithms for solving linear systems, have undergone transformative advances, solidifying their role as indispensable tools in diverse scientific and engineering applications. A new variant of the randomized version of the Kaczmarz method namely sparse Kaczmarz was recently proposed for recovery sparse solutions of linear systems. It is an instance of the Bregman-Kaczmarz method which is a stochastic iterative method for finding solutions of linear systems using Bregman projection instead of Euclidean projection as it is done in the Kaczmarz method, thus taking into account different geometries. This thesis delves into the forefront of iterative solvers, focusing on novel enhancements to the classical Bregman-Kaczmarz method. The research encompasses three key facets: acceleration techniques, tailored iterative methods for least squares and impulsive noise problems and the integration of adaptive stepsize strategies. We develop and analyse variants that leverage parallel computations, averaging techniques and extrapolation to offer faster convergence rates. By incorporating randomized and accelerating techniques, the dissertation systematically explores new approaches that transcend the traditional bounds of convergence rates. The findings not only demonstrate substantial efficiency improvements but also showcase the adaptability of accelerated Bregman-Kaczmarz methods to diverse linear systems, particularly in the context of large-scale computations and high-dimensional data. Furthermore, we address the challenges posed by finding sparse least squares solutions and handling impulsive noise. Tailored adaptations of Bregman-Kaczmarz methods are proposed, leveraging the inherent property of these problems. The dissertation meticulously details the design and analysis of algorithms that provide accurate and computationally efficient solutions, establishing Bregman-Kaczmarz methods as potent tools in fields such as signal processing, machine learning, and scientific computing. Additionally, we propose an approach to solve linear inverse problems with independent noise exactly by leveraging adaptive stepsize strategies. This paradigm shift in iterative solvers introduces dynamic stepsize adjustments based on noise magnitude during iterations, optimizing performance across a spectrum of linear inverse problems. Through extensive experimentation and theoretical analysis, the thesis demonstrates the robustness and versatility of adaptive stepsize strategies within the context of Bregman-Kaczmarz methods.