Sparse multivariate function recovery with a small number of evaluations

In Kaltofen and Yang (2014) we give an algorithm based algebraic error-correcting decoding for multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (“outliers”). Our 2014 algorithm can interpolate a sparse multivariate rational function from evaluations where the error rate 1/q1/q is quite high, say q=5q=5.For the algorithm with exact arithmetic and exact values at non-erroneous points, one avoids quadratic oversampling by using random evaluation points. Here we give the full probabilistic analysis for this fact, thus providing the missing proof to Theorem 2.1 in Section 2 of our ISSAC 2014 paper. Our argumentation already applies to our original 2007 sparse rational function interpolation algorithm (Kaltofen et al., 2007), where we have experimentally observed that for T   unknown non-zero coefficients in a sparse candidate ansatz one only needs T+O(1)T+O(1) evaluations rather than O(T2)O(T2) (cf. Candès and Tao sparse sensing), the latter of which we have proved in 2007. Here we prove that T+O(1)T+O(1) evaluations at random points indeed suffice.