Sparse multivariate function recovery with a small number of evaluations. (July 2016)

• Record Type: Journal Article
• Authors: Kaltofen, Erich L.; Yang, Zhengfeng
• Is Part Of: Journal of symbolic computation. Volume 75(2016)
• Page Start: 209
• Page End: 218
• Publication Date: 2016-07
• Subjects: Error correcting coding -- Fault tolerance -- Cauchy interpolation -- Multivariate rational function model; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.11.015
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: InKaltofen 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 / q is quite high, say q = 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 ) evaluations rather than O ( T 2 ) (cf. Candès and Tao sparse sensing), the latter of which we have proved in 2007. Here we prove that T + O ( 1 ) evaluations at random points indeed suffice.