Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Friday, October, 10, 2014, at University of Waterloo
Cleaning-up Data With Errors: When Symbolic-Numeric Sparse Interpolation Meets Error-Correcting Codes
Erich Kaltofen, North Carolina State University

Abstract:

Algebraic error-correcting decoding is generalized to multivariate sparse polynomial and rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (``outliers'').

Our univariate solution for numerical Prony-Blahut/ Giesbrecht-Labahn-Lee sparse interpolation can identify and remove outliers (``cleans up data'') by a voting scheme and Sudan's list decoding. Our multivariate solution for numerical Zippel/Kaltofen-Yang-Zhi sparse rational function interpolation removes outliers by techniques from the Welch/Berlekamp decoder for Reed-Solomon codes.

Our algorithms are doubly hybrid: they combine exact with numerical methods, in fact, constitute a numerical version of the algebraic error-correcting decoders, and recover both discrete outputs, the term degrees in the sparse support, and continuous data, the real or complex coefficients that approximately fit the data.

This is joint work with Matthew Comer [now at CNU], Clement Pernet [U. Grenoble] and Zhengfeng Yang [ECNU Shanghai].

 

Last modified on Sunday, 23 November 2014, at 22:23 hours.