کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
401334 675339 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Symbolic Computation - Volume 75, July–August 2016, Pages 209–218
نویسندگان
, ,