Rapidly computing sparse Legendre expansions via sparse Fourier transforms

In this paper, we propose a general strategy for rapidly computing sparse Legendre expansions. The resulting methods yield a new class of fast algorithms capable of approximating a given function f : ?1, 1] → ? with a near-optimal linear combination of s Legendre polynomials of degree ≤ N in just \((s \log N)^{\mathcal {O}(1)}\)-time. When s ? N, these algorithms exhibit sublinear runtime complexities in N, as opposed to traditional Ω(NlogN)-time methods for computing all of the first N Legendre coefficients of f. Theoretical as well as numerical results demonstrate the effectiveness of the proposed methods.