报告主题：任意正交基上的稀疏多项式插值算法

报告人： Erich Kaltofen 教授 （美国北卡罗琳娜大学数学系）

报告时间：2018年 6月8日（周五）14:00

报告地点：校本部G507

邀请人：曾振柄

主办部门：理学院数学系

报告摘要：In [Kaltofen and Yang, Proc. ISSAC 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 is 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.1in Section 2 of our ISSAC 2014 paper. Our argumentation 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 O(T2) (cf. Cand`es 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.

欢迎教师、学生参加 ！