Sparse multivariate function recovery from values with noise and outlier errors

In [Kaltofen and Yang, Proc. ISSAC 2013] we have generalized algebraic error-correcting decoding to multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (“outliers”). Here we present a different algorithm that can interpolate a sparse mul-tivariate rational function from evaluations where the error rate is 1/q for any q> 2, which our ISSAC 2013 algorithm could not handle. When implemented as a numerical algorithm we can, for instance, reconstruct a fraction of trinomials of degree 15 in 50 variables with non-outlier evaluations of relative noise as large as 10−7 and where as much as 1/4 of the 14717 evaluations are outliers with relative error as small as 0.01. For the algorithm with exact arithmetic and exact values at non-erroneous points, we provide a proof that for random evaluations one can avoid quadratic oversampling. Our argument already applies to our original 2007 sparse rational function interpolation algorithm [Kaltofen, Yang and Zhi, Proc. SNC 2007], where we have experimentally observed that for T unknown non-zero coefficients in a sparse candidate ansatz one only needs T + O(1) evaluations rather than the proven O(T 2) (cf. Candès and Tao sparse sensing). Here we finally can give the probabilistic analysis for this fact. 1