Sparse polynomial interpolation with arbitrary orthogonal polynomial bases

An algorithm for interpolating a polynomial f from evaluation points whose running time depends on the sparsity t of the polynomial when it is represented as a sum of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients is given by Lakshman Y. N. and Saunders [SIAM J. Comput., vol. 24, nr. 2 (1995)]; Kaltofen and Lee [JSC, vol. 36, nr. 3–4 (2003)] analyze a randomized early termination version which computes the sparsity t. Those algorithms mirror Prony’s algorithm for the standard power basis to the Chebyshev Basis of the First Kind. An alternate algorithm by Arnold’s and Kaltofen’s [Proc. ISSAC 2015, Sec. 4] uses Prony’s original algorithm for standard power terms. Here we give sparse interpolation algorithms for generalized Chebyshev polynomials, which include the Chebyshev Bases of the Second, Third and Fourth Kind. Our algorithms also reduce to Prony’s algorithm. If given on input a bound B ≥ t for the sparsity, our new algorithms deterministically recover the sparse representation in the First, Second, Third and Fourth Kind Chebyshev representation from exactly t + B evaluations. Finally, we generalize our algorithms to bases whose Chebyshev recurrences have parametric scalars. We also show how to compute those parameter values which optimize the sparsity of the representation in the corresponding basis, similar to computing a sparsest shift.