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]\to \mathbb{R}$ with a near-optimal linear combination of $s$ Legendre polynomials of degree $\le N$ in just $(s\log N{)}^{\mathcal{O}(1)}$-time. When $s\ll N$ these algorithms exhibit sublinear runtime complexities in $N$, as opposed to traditional $\mathrm{\Omega }(N\log N)$-time methods for computing all of the first $N$ Legendre coefficients of $f$. Theoretical as well as numerical results demonstrate the promise of the proposed approach.