数学系Seminar第1631期 任意正交基上的稀疏多项式插值算法

创建时间:  2018/05/25  龚惠英   浏览次数:   返回

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

报告人: Erich Kaltofen 教授 (美国北卡罗琳娜大学数学系)

报告时间:2018年 6月8日(周五)14:00

报告地点:校本部G507

邀请人:曾振柄

主办部门:太阳成集团tyc33455数学系

报告摘要: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.

欢迎教师、员工参加 !

上一条:数学系Seminar第1632期 Configuration空间的上同调群和表示稳定性

下一条:数学系Seminar第1630期 用切比雪夫基计算带纠错的稀疏插值


数学系Seminar第1631期 任意正交基上的稀疏多项式插值算法

创建时间:  2018/05/25  龚惠英   浏览次数:   返回

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

报告人: Erich Kaltofen 教授 (美国北卡罗琳娜大学数学系)

报告时间:2018年 6月8日(周五)14:00

报告地点:校本部G507

邀请人:曾振柄

主办部门:太阳成集团tyc33455数学系

报告摘要: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.

欢迎教师、员工参加 !

上一条:数学系Seminar第1632期 Configuration空间的上同调群和表示稳定性

下一条:数学系Seminar第1630期 用切比雪夫基计算带纠错的稀疏插值