Sparse Multivariate Rational Function Model Discovery

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.