Rapidly Computing Sparse Legendre Expansions via Sparse Fourier Transforms

Abstract

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 $\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.

References in corpus (2)

• Nearly Optimal Sparse Fourier Transform
• A fast FFT-based discrete Legendre transform