Aaron Sidford: Perron-Frobenius Theory in Nearly Linear Time

Abstract: The Perron-Frobenius theorem of O. Perron (1907) and G. Frobenius (1912) is a fundamental linear algebraic that has had far reaching implications over the past century. It lies at the heart of numerous computational task including computing the stationary distribution of a Markov chain, solving linear systems in M-matrices, computing personalized PageRank, computing Katz centrality, and evaluating the utility of policies in Markov decision process. However, despite the ubiquity of these problems and their extensive study, the fastest known running times for all of these problems either depended either polynomially on the desired accuracy or conditioning of the problem or appealed to generic linear system solving machinery, and therefore ran in super-quadratic time.

In this talk I will present recent results showing that these problems can be solved to high precision in nearly linear time. I will present new iterative methods for extracting structure from directed graphs and show how they can be tailored to computing Perron vector's and solving M-matrices in nearly linear time. Moreover, I will discuss connections between this work and recent developments in solving Laplacian systems, new nearly linear time linear algebraic primitives, and emerging trends in combining continuous and combinatorial techniques in the design of optimization algorithms.