Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values
Matthew T. Comer, Erich Kaltofen, Clément Pernet · 2012
We propose algorithms performing sparse interpolation with errors, based on Prony's--Ben-Or's & Tiwari's algorithm, using a Berlekamp/Massey algorithm with early termination. First, we present an algorithm that can recover a t-sparse polynomial f from a sequence of values, where some of the values are wrong, spoiled by either random or misleading errors. Our algorithm requires bounds T ≥ t and E ≥ e, where e is the number of evaluation errors. It interpolates f(ωi) for i = 1,..., 2T(E + 1), where ω is a field element at which each non-zero term evaluates distinctly.