Sparse Polynomial Interpolation and Berlekamp/Massey Algorithm That Correct Outlier Errors in Input Values

Abstract : We propose algorithms performing sparse interpolation with errors, based on Prony's-Ben-Or's & Tiwari's algo- rithm, 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 val- ues, where some of the values are wrong, spoiled by ei- ther random or misleading errors. Our algorithm re- quires bounds T t and E e, where e is the num- ber 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. We also investigate the problem of recovering the min- imal linear generator from a sequence of field elements that are linearly generated, but where again e E elements are erroneous. We show that there exist se- quences of < 2t(2e + 1) elements, such that two dis- tinct generators of length t satisfy the linear recurrence up to e faults, at least if the field has characteristic 6= 2. Uniqueness can be proven (for any field charac- teristic) for length 2t(2e + 1) of the sequence with e errors. Finally, we present the Majority Rule Berle- kamp/Massey algorithm, which can recover the unique minimal linear generator of degree t when given bounds T t and E e and the initial sequence segment of 2T(2E + 1) elements. Our algorithm also corrects the sequence segment. The Majority Rule algorithm yields a unique sparse interpolant for the first problem. The algorithms are applied to sparse interpolation al- gorithms with numeric noise, into which we now can bring outlier errors in the values.
Type de document :
Communication dans un congrès
ISSAC \'12: Proceedings of the 2012 international symposium on symbolic and algebraic computation, 2012, Grenoble, France. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00796255
Contributeur : Grégory Mounié <>
Soumis le : samedi 2 mars 2013 - 14:13:44
Dernière modification le : vendredi 12 octobre 2018 - 01:18:01

Identifiants

  • HAL Id : hal-00796255, version 1

Collections

Citation

Matthew T. Comer, Erich L. Kaltofen, Clement Pernet. Sparse Polynomial Interpolation and Berlekamp/Massey Algorithm That Correct Outlier Errors in Input Values. ISSAC \'12: Proceedings of the 2012 international symposium on symbolic and algebraic computation, 2012, Grenoble, France. 2012. 〈hal-00796255〉

Partager

Métriques

Consultations de la notice

214