##### Department of Mathematics,

University of California San Diego

****************************

### Math 278B - Mathematics of Information, Data, and Signals Seminar

## Anna Ma

#### UC Irvine

## The Kaczmarz Algorithm: Greed, Randomness, and Tensors

##### Abstract:

The Kaczmarz algorithm is an iterative method for solving linear systems of equations of the form Ax=y. Owing to its low memory footprint, the Kaczmarz algorithm has gained popularity for its practicality in applications to large-scale data, acting only on single rows of A at a time. In this talk, we discuss selecting rows of A randomly (Randomized Kaczmarz), selecting rows in a greedy fashion (Motzkin's Method), and selecting rows in a partially greedy fashion (Sampling Kaczmarz-Motzkin algorithm). Despite their variable computational costs, these algorithms have been proven to have the same theoretical upper bound on the convergence rate. Here we present an improvement upon previous known convergence bounds of the Sampling Kaczmarz-Motzkin algorithm, capturing the benefit of partially greedy selection schemes. Time permitting, we also will discuss an extension of the Kaczmarz algorithm to the setting where data takes on the form of a tensor and make connections between the new Tensor Kaczmarz algorithm and previously established algorithms. \\ \\ This presentation contains joint work with Jamie Haddock and Denali Molitor.

Host: Rayan Saab

### September 9, 2021

### 11:30 AM

Zoom link: https://msu.zoom.us/j/96421373881 (passcode: first prime number $>$ 100)

****************************