Smoothed analysis has become a central tool in computer science, often allowing for significant improvements to worst-case running times if we settle for a solution to a small random perturbation of the problem instance. This is closely related to the classical concept of backward error in numerical analysis, which allows an algorithm to return a solution to a small arbitrary perturbation of the problem.
Despite the qualitative similarity of these concepts, we show that they can exhibit large quantitative differences. Notably, we prove that, while a linear system with any n × n matrix A can be solved to backward error ε using O(log n / ε) matrix-vector products with A, any algorithm that solves a random ε-sized perturbation of A requires Ω(n) matrix-vector products.
This means that a useful perturbation for solving a linear system in backward error must be adaptive to the input. We use this as a starting point to explore the role of adaptivity and randomness in designing perturbations for solving numerical linear algebra problems in backward error.
Based on joint works with Yuji Nakatsukasa, Elizaveta Rebrova, Raphael Meyer, Michael Mahoney, and Christopher Musco.