Analysing approximate Gaussian elimination using matrix martingales

Rasmus Kyng (Harvard) 11:00 -- 12:00

The sum of a sequence of random variables is a martingale, if each variable has zero mean, conditioned on all the preceding variables. Concentration results for matrix-valued martingales have become an important tool in the analysis of algorithms in randomized numerical linear algebra. Simple and fast algorithms for many well-studied problems can be analyzed in using martingales. We will explore recent results on using matrix martingales for analyzing approximate Gaussian elimination on Laplacian matrices associated with undirected and directed graphs, and survey briefly other uses of matrix martingales in spectral graph theory.