- Series
- Algebra Seminar
- Time
- Friday, March 17, 2017 - 11:05am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Erich Kaltofen – North Carolina State University
- Organizer
- Anton Leykin
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 multivariate polynomial and rational function
interpolation algorithm combines Zippel's symbolic sparse
polynomial interpolation technique [Ph.D. Thesis MIT 1979]
with the numeric algorithm by Kaltofen, Yang, and Zhi [Proc.
SNC 2007], and removes outliers (cleans up data'') by
techniques from the Welch/Berlekamp decoder for Reed-Solomon
codes.
Our algorithms can build a sparse function model from a
number of evaluations that is linear in the sparsity of the
model, assuming that there are a constant number of ouliers
and that the function probes can be randomly chosen.