报告主题：任意正交基上的稀疏多项式插值算法
报告人： 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 evalsuations that can be numerically inaccurate and where several evalsuations can have severe errors (“outliers”). Our 2014 algorithm can interpolate a sparse multivariate rational function from evalsuations 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 evalsuation 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) evalsuations 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) evalsuations at random points indeed suffice.
欢迎教师、学生参加 ！
