Backend
From smoothed analysis to backward error: The power of adaptive perturbations
arXiv cs.NA0 views
arXiv:2611.18545v1 Announce Type: cross Abstract: Smoothed analysis has become a central tool in theoretical 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 an 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 \times n$ matrix $A$ can be solved to backward error $\epsilon$ using $O(\log(n) / \epsilon)$ matrix-vector products with $A$, any algorithm that solves a random $\epsilon$-sized perturbation of $A$ requires $\Omega(n)$ matrix-vector products. This means that a useful perturbation for solving a linear system in backward error must be adaptive to the input. Interestingly, however, randomness is still essential: we show that any deterministic method that attains small backward error for all linear systems provably requires $\Omega(n)$ matrix-vector products, resulting in the first separation between randomized and deterministic algorithms in a natural computational model for solving linear systems. Finally, we show that matrix structure can significantly affect backward error complexity. For example, we show a deterministic $O(1/\epsilon)$ matrix-vector product algorithm for symmetric linear systems.
Source:https://arxiv.org/abs/2611.18545PreviousLearning observable propagation with sparse local momentsNextTime Relaxation with Iterative Modified Lavrentiev Regularization
Related posts
Helsing backer Plural raises $1.1B to fund Europe’s next moonshots
0TechCrunch
Building Mobile Connectivity in Afghanistan: A Look at Roshan
0dev.to
Your Tests Blocked System.exit With a SecurityManager and Java 25 Will Not Let You Install One
0dev.to
We autoscaled our Java pricing service on memory and it grew to twenty pods and stayed there
0dev.to
Nine small tools I stopped installing apps for
0dev.to
I built a small tool to capture website screenshots across devices
0dev.to Productivity