Logo

Mathematical Sciences Research Institute

Home » GFA Young Researchers Seminar: Iterative Methods for Solving Factorized Linear Systems

Seminar

GFA Young Researchers Seminar: Iterative Methods for Solving Factorized Linear Systems November 29, 2017 (11:15 AM PST - 12:30 PM PST)
Parent Program:
Location: MSRI: Baker Board Room
Speaker(s) Anna Ma (Claremont Graduate University)
Description No Description
Video
No Video Uploaded
Abstract/Media

Stochastic iterative algorithms such as the Kacmarz and Gauss-Seidel methods have gained recent attention because of their speed, simplicity, and the ability to approximately solve large-scale linear systems of equations without needing to access the entire matrix. In this work, we consider the setting where we wish to solve a linear system in a large matrix $X$ that is stored in a factorized form, $X = UV$; this setting either arises naturally in many applications or may be imposed when working with large low-rank datasets for reasons of space required for storage. We propose a variant of the randomized Kaczmarz method for such systems that takes advantage of the factored form, and avoids computing $X$. We prove an exponential convergence rate and supplement our theoretical guarantees with experimental evidence demonstrating that the factored variant yields significant acceleration in convergence. Joint work with Deanna Needell and Aaditya Ramdas.

No Notes/Supplements Uploaded No Video Files Uploaded