Representation of sparse Legendre expansions

We derive a new deterministic algorithm for the computation of a sparse Legendre expansion f of degree N with M≪N nonzero terms from only 2M function resp. derivative values f(j)(1), j=0,…,2M−1 of this expansion. For this purpose we apply a special annihilating filter method that allows us to separate the computation of the indices of the active Legendre basis polynomials and the evaluation of the corresponding coefficients.