## Sparse Multivariate Rational Function Model Discovery

Series:
Algebra Seminar
Friday, March 17, 2017 - 11:05am
1 hour (actually 50 minutes)
Location:
Skiles 006
,
North Carolina State University
Organizer:
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.