Affordable Access

Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials

Authors
  • Hubert, Evelyne
  • Singer, Michael
Publication Date
Jan 24, 2020
Source
Kaleidoscope Open Archive
Keywords
Language
English
License
Unknown
External links

Abstract

Sparse interpolation refers to the exact recovery of a function as a short linear combination of basis functions from a limited number of evaluations. For multivariate functions, the case of the monomial basis is well studied, as is now the basis of exponential functions. Beyond the multivariate Chebyshev polynomial obtained as tensor products of univariate Chebyshev polynomials, the theory of root systems allows to define a variety of generalized multivariate Chebyshev polynomials that have connections to topics such as Fourier analysis and representations of Lie algebras. We present a deterministic algorithm to recover a function that is the linear combination of at most r such polynomials from the knowledge of r and an explicitly bounded number of evaluations of this function.

Report this publication

Statistics

Seen <100 times