You are here

Random Walks on the Sphere and Linear Systems of Equations

Stefan Steinerberger, University of Washington
Tuesday, November 10, 2020 - 1:30pm

Solving a system of linear equations is really the same as finding the common intersections of hyperplanes. This leads to a nice iterative method, first proposed by Kaczmarz in 1937: start with some arbitrary initial vector and then iteratively project onto the hyperplanes in some order, then your vector converges to the true solution of the linear system (this follows from the Pythagorean theorem). This replaces the numerical problem by a fun question in geometric probability: if you bounce around randomly between these hyperplanes, what happens?  This wasn't understood until recently (nonetheless, people have been using the method since the 1980s).  I will describe some fairly precise results about these random walks  -- one really nice byproduct is as follows: if you figure out a way to quickly reconstruct the location of the center of a sphere in IR^n from knowing many (say 100n) points on the sphere, you have invented a new and faster iterative method for solving linear systems.  Maybe that's not so hard? There should be several methods that do this.   This material is all fairly new (< 4 months), so there are tons of open questions and lots of good problems just waiting to be solved.

People Involved: 
Event Type: 
Event Subcalendar: