An Equivalence result for sketched Anderson Acceleration and sketched GMRES
For researchers in numerical linear algebra and optimization, this equivalence clarifies the relationship between two acceleration techniques and may guide the design of new randomized methods.
The paper proves that randomized Anderson Acceleration is equivalent to randomized GMRES for linear problems when the least-squares problem is solved in a sketched space, extending a classical result. This provides a theoretical link between the two methods.
In this paper we present an equivalence result between a randomized version of Anderson Acceleration and of randomized GMRES for linear problems. Namely, we extend the classical result of Walker and Ni (2011) to the case in which the least-squares problem in Anderson Acceleration is solved in a sketched space defined by a random projection. This equivalence suggests potential avenues for further research in the design and analysis of randomized acceleration methods.