Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations

Brice Boyer (), Matthew T. Comer () and Erich L. Kaltofen ()
Additional contact information
Brice Boyer: North Carolina State University, Department of Mathematics
Matthew T. Comer: North Carolina State University, Department of Mathematics
Erich L. Kaltofen: North Carolina State University, Department of Mathematics

A chapter in Computer Mathematics, 2014, pp 183-197 from Springer

Abstract: Abstract We compute approximate sparse polynomial models of the form $$\widetilde{f}(x) = \sum _{j=1}^t \widetilde{c}_j (x - \widetilde{s})^{e_j}$$ f ~ ( x ) = ∑ j = 1 t c ~ j ( x - s ~ ) e j to a function $$f(x)$$ f ( x ) , of which an approximation of the evaluation $$f(\zeta )$$ f ( ζ ) at any complex argument value $$\zeta $$ ζ can be obtained. We assume that several of the returned function evaluations $$f(\zeta )$$ f ( ζ ) are perturbed not just by approximation/noise errors but also by highly perturbed outliers. None of the $$\widetilde{c}_j$$ c ~ j , $$\widetilde{s}$$ s ~ , $$e_j$$ e j and the location of the outliers are known beforehand. We use a numerical version of an exact algorithm by [4] together with a numerical version of the Reed–Solomon error correcting coding algorithm. We also compare with a simpler approach based on root finding of derivatives, while restricted to characteristic $$0$$ 0 . In this preliminary report, we discuss how some of the problems of numerical instability and ill-conditioning in the arising optimization problems can be overcome. By way of experiments, we show that our techniques can recover approximate sparse shifted polynomial models, provided that there are few terms $$t$$ t , few outliers and that the sparse shift is relatively small.

Keywords: Approximate function recovery; Numeric and exact polynomial interpolation; Outlier detection; Sparse representations (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-43799-5_16

Ordering information: This item can be ordered from
http://www.springer.com/9783662437995

DOI: 10.1007/978-3-662-43799-5_16

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().