Sparse multivariate function recovery from values with noise and outlier errors
Sparse multivariate function recovery from values with noise and outlier errors
复制标题
从带有噪声和异常值错误的值中恢复稀疏多元函数
DOI：
10.1145/2465506.2465524
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Zhengfeng Yang
中科院分区：
文献类型：
--
作者：
E. Kaltofen;Zhengfeng Yang
纠错解码被推广到从可能在数值上不准确并且其中几个评估可能具有严重错误(离群值)的评估中恢复多变量稀疏有理函数。2012年，Kaltofen和Pernet将Berlekamp-Welch解码器推广到一元有理函数的精确柯西插值法。基于结构化线性代数，我们给出了一种不同的单变量解，该解产生了一个稳定的浮点算法解码器。我们的多元多项式和有理函数插值算法结合了Zippel的符号稀疏多项式插值技术[博士论文MIT 1979]和Kaltofen，Yang，and Zhi[Proc.SNC 2007]，并通过纠错码中的技术去除离群值(“清理数据”)。我们的多变量算法可以从与模型的稀疏性呈线性关系的一系列评估中构建稀疏模型。
Error-correcting decoding is generalized to multivariate sparse rational function recovery from evaluations that can be numerically inaccurate and where several evaluations can have severe errors ("outliers"). The generalization of the Berlekamp-Welch decoder to exact Cauchy interpolation of univariate rational functions from values with faults is by Kaltofen and Pernet in 2012. We give a different univariate solution based on structured linear algebra that yields a stable decoder with floating point arithmetic. Our multivariate polynomial and rational function interpolation algorithm combines Zippel's symbolic sparse polynomial interpolation technique [Ph.D. Thesis MIT 1979] with the numeric algorithm by Kaltofen, Yang, and Zhi [Proc. SNC 2007], and removes outliers ("cleans up data") through techniques from error correcting codes. Our multivariate algorithm can build a sparse model from a number of evaluations that is linear in the sparsity of the model.