Скачать или смотреть Jason Altschuler - Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm

Recorded 22 May 2025. Jason Altschuler of the Massachusetts Institute of Technology presents "Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm" at IPAM's Statistical and Numerical Methods for Non-commutative Optimal Transport Workshop.
Abstract: Most modern software packages solve large-scale optimal transport using Sinkhorn’s algorithm for matrix scaling. In this talk, I will connect this topic to Osborne’s algorithm for matrix balancing -- highlighting similarities, differences, and recent advances.
Details: In 1960, Osborne proposed a simple iterative algorithm for matrix balancing with outstanding numerical performance. Today, it is the default preconditioning procedure before eigenvalue computation and other linear algebra subroutines in mainstream software packages such as Python, Julia, MATLAB, EISPACK, and LAPACK. Despite its widespread usage, Osborne's algorithm has long resisted theoretical guarantees for its runtime: the first polynomial-time guarantees were obtained only in the past decade, and recent near-linear runtimes remain confined to variants of Osborne's algorithm with important differences that make them simpler to analyze but empirically slower. In this talk, I will describe our recent work which addresses this longstanding gap between theory and practice by proving that Osborne's original algorithm -- the de facto preconditioner in practice -- in fact has near-linear runtime. This runtime guarantee (1) is optimal in the input size up to at most a single logarithm, (2) is the first runtime for Osborne's algorithm that does not dominate the runtime of downstream tasks like eigenvalue computation, and (3) improves upon the theoretical runtimes for all other variants of Osborne's algorithm. Based on joint work with Xufeng Cai and Jelena Diakonikolas.
Learn more online at: https://www.ipam.ucla.edu/programs/wo...