Rapidly computing sparse Legendre expansions via sparse Fourier transforms (Q521921)

The problem is to approximate a real function on \([-1,1]\) by a linear combination of \(s\ll N\) Legendre polynomials of degree at most \(N\) in least squares sense. Therefore, the Legendre problem for \(f\) is transformed into a Fourier problem for another function \(f_r\) such that for \(f_r\) known sparse Fourier transforms based on random sampling can be implemented with fast Fourier transform techniques. The value \(r\in(0,1]\) is a parameter used in the Iserles transform [\textit{A. Iserles}, Numer. Math. 117, No. 3, 529--553 (2011; Zbl 1211.33001)] which defines how fast the entries in the matrix connecting the Legendre and the Fourier coefficients will decay. The result is a stable algorithm with time complexity of order \((s\log N)^{O(1)}\).