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

Publication date 22 February 2021

Abstract: We present sparse interpolation algorithms for recovering a polynomial with

l e B

terms from

N

evaluations at distinct values for the variable when

l e E

of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars

m a t h s f K

and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of

m a t h s f K

is

e 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 = l f l o o r f r a c 43 E + 2 f l o o r 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 = l f l o o r f r a c 32 E + 2 f l o o r 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 l f l o o r f r a c E 13 + 1 f l o o r

for

B = 3

and

E g e 222

. Our method shows how to correct

2

errors in a block of

4 B

points for standard basis and how to correct

1

error in a block of

3 B

points for Chebyshev Basis.

Cited in

(2)

This page was built for publication: Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding