Fast and Stable Approximation of Analytic Functions from Equispaced Samples via Polynomial Frames

We consider approximating analytic functions on the interval [-1, 1] from their values at a set of m + 1 equispaced nodes. A result of Platte, Trefethen & Kuijlaars states that fast and stable approximation from equispaced samples is generally impossible. In particular, any method that converges exponentially fast must also be exponentially ill-conditioned. We prove a positive counterpart to this 'impossibility' theorem. Our 'possibility' theorem shows that there is a well-conditioned method that provides exponential decay of the error down to a finite, but user-controlled tolerance epsilon > 0, which in practice can be chosen close to machine epsilon. The method is known as polynomial frame approximation or polynomial extensions. It uses algebraic polynomials of degree n on an extended interval [-gamma, gamma], gamma > 1, to construct an approximation on [-1, 1] via a SVD-regularized least-squares fit. A key step in the proof of our main theorem is a new result on the maximal behaviour of a polynomial of degree n on [-1, 1] that is simultaneously bounded by one at a set of m + 1 equispaced nodes in [-1, 1] and 1/epsilon on the extended interval [-gamma, gamma]. We show that linear oversampling, i.e. m = cn log(1/epsilon)/root gamma(2) - 1, is sufficient for uniform boundedness of any such polynomial on [-1, 1]. This result aside, we also prove an extended impossibility theorem, which shows that such a possibility theorem (and consequently the method of polynomial frame approximation) is essentially optimal.