Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding

Erich L. Kaltofen, Zhi-Hong Yang

We present sparse interpolation algorithms for recovering a polynomial with $\le B$ terms from $N$ evaluations at distinct values for the variable when $\le E$ of the evaluations c…