Sparse multivariate function recovery with a high error rate in the evaluations
Sparse multivariate function recovery with a high error rate in the evaluations
复制标题
评估中错误率较高的稀疏多元函数恢复
DOI：
10.1145/2608628.2608637
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Zhengfeng Yang
中科院分区：
文献类型：
--
作者：
E. Kaltofen;Zhengfeng Yang
在[Kaltofen和Yang，Proc. ISSAC 2013]中，我们将代数纠错解码推广到来自可能在数值上不准确的评估的多变量稀疏有理函数插值，并且其中几个评估可能具有严重的错误（“离群值”）。在这里，我们提出了一种不同的算法，可以从错误率为1/q的任何q > 2的评估中插值稀疏多元有理函数，这是我们的ISSAC 2013算法无法处理的。例如，当作为数值算法实现时，我们可以在50个变量中重建一部分15度的三项式，其相对噪声的非离群值评估值高达10-7，并且14717个评估值中有1/4是相对误差小至0.01的离群值（我们的方法很容易定位大的离群值）。
对于精确的算术和精确值在非错误点的算法，我们提供了一个证明，随机评估可以避免二次过采样。我们的论点已经适用于我们最初的2007年稀疏有理函数插值算法[Kaltofen，Yang和Zhi，Proc. SNC 2007]，其中我们通过实验观察到，对于稀疏候选模型中的T个未知非零系数，只需要T +O（1）求值，而不是证明的O（T2）（cf. Candès and Tao sparse sensing）.在这里，我们终于可以对这一事实进行概率分析。
In [Kaltofen and Yang, Proc. ISSAC 2013] we have generalized algebraic error-correcting decoding to multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors ("outliers"). Here we present a different algorithm that can interpolate a sparse multivariate rational function from evaluations where the error rate is 1/q for any q > 2, which our ISSAC 2013 algorithm could not handle. When implemented as a numerical algorithm we can, for instance, reconstruct a fraction of trinomials of degree 15 in 50 variables with non-outlier evaluations of relative noise as large as 10-7 and where as much as 1/4 of the 14717 evaluations are outliers with relative error as small as 0.01 (large outliers are easily located by our method).
For the algorithm with exact arithmetic and exact values at non-erroneous points, we provide a proof that for random evaluations one can avoid quadratic oversampling. Our argument 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 the proven O(T2) (cf. Candès and Tao sparse sensing). Here we finally can give the probabilistic analysis for this fact.