Скачать или смотреть Talk by Lek-Heng Lim (University of Chicago)

From randomized linear algebra to semidefinite programming

We give an account of the recent resolution of the Recht-Re conjecture: Zehua Lai's proof that it is false and De Sa's construction of explicit counterexamples. To answer a fundamental question (is it better to sample with or without replacement?) about randomized iterative methods in numerical linear algebra, we are led to a natural-looking matrix inequality that seems plausible, holds true in extensive numerical experiments, and can be proved for small cases. A more subtle analysis shows that the inequality can be translated into a property of multivariate matrix polynomials. The property may then be verified using semidefinite programming, essentially linear programming with matrix variables, and whose computation relies on repeated solutions of linear systems. So a question in numerical linear algebra is ultimately answered using numerical linear algebra, through a circuitous but scenic route. We will discuss some highlights of this route.