Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding
share
We present sparse interpolation algorithms for recovering a polynomial with ≤ B terms from N evaluations at distinct values for the variable when ≤ E of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars 𝖪 and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of 𝖪 is 2. Our algorithms return a list of valid sparse interpolants for the N support points and run in polynomial-time. For standard power basis our algorithms sample at N = ⌊4/3 E + 2 ⌋ B points, which are fewer points than N = 2(E+1)B - 1 given by Kaltofen and Pernet in 2014. For Chebyshev basis our algorithms sample at N = ⌊3/2 E + 2 ⌋ B points, which are also fewer than the number of points required by the algorithm given by Arnold and Kaltofen in 2015, which has N = 74 ⌊E/13 + 1 ⌋ for B = 3 and E ≥ 222. Our method shows how to correct 2 errors in a block of 4B points for standard basis and how to correct 1 error in a block of 3B points for Chebyshev Basis.
READ FULL TEXT