Speaker: 

Halyun Jeong

Institution: 

UCLA

Time: 

Monday, April 1, 2024 - 4:00pm to 5:00pm

Host: 

Location: 

RH 306

In this talk, I will discuss recent developments in hybrid methods that combine the Kaczmarz method (KZ) and the iterative thresholding (IHT) method to solve linear systems with sparse constraints. The Kaczmarz method (KZ) and its variants, which are types of stochastic gradient descent (SGD) methods, have been extensively studied due to their simplicity and efficiency in solving linear equation systems. The iterative thresholding (IHT) method has gained popularity in various research fields, including compressed sensing or sparse linear regression. Recently, a hybrid method called Kaczmarz-based IHT (KZIHT) has been proposed, combining the benefits of both approaches, but its theoretical guarantees are missing. In this paper, we provide the first theoretical convergence guarantees for KZIHT by showing that it converges linearly to the solution of a system with sparsity constraints up to optimal statistical bias when the reshuffling data sampling scheme is used. We also propose the Kaczmarz with periodic thresholding (KZPT) method, which generalizes KZIHT by applying the thresholding operation for every certain number of KZ iterations and by employing two different types of step sizes. I will discuss several numerical experiments to support our theory; This is joint work with Deanna Needell.