Random Walks, Faber Polynomials and Accelerated Power Methods
It provides a new theoretical tool for polynomial approximation with potential applications in iterative linear algebra, but the practical impact is not demonstrated with concrete results.
The paper constructs polynomial families from random walks to approximate z^n with degree ~√n in radially convex domains, and applies them to develop arbitrary-order dynamic momentum power iteration methods for non-symmetric matrices.
In this paper, we construct families of polynomials defined by recurrence relations related to mean-zero random walks. We show these families of polynomials can be used to approximate $z^n$ by a polynomial of degree $\sim \sqrt{n}$ in associated radially convex domains in the complex plane. Moreover, we show that the constructed families of polynomials have a useful rapid growth property and a connection to Faber polynomials. Applications to iterative linear algebra are presented, including the development of arbitrary-order dynamic momentum power iteration methods suitable for classes of non-symmetric matrices.