»ã±¨Ö÷Ì⣺ËÁÒâÕý½»»ùÉϵÄÏ¡ÉÙ¶àÏîʽ²åÖµËã·¨

»ã±¨ÈË£º 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.

Ó­½ÓÀÏʦ¡¢Ñ§Éú²ÎÓë £¡