Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials

Evelyne Hubert 1 Michael Singer 2
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA - National and Kapodistrian University of Athens
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.
Complete list of metadata

Cited literature [57 references]  Display  Hide  Download
Contributor : Evelyne Hubert <>
Submitted on : Friday, January 24, 2020 - 4:20:49 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Saturday, April 25, 2020 - 4:27:05 PM


Files produced by the author(s)


  • HAL Id : hal-02454589, version 1



Evelyne Hubert, Michael Singer. Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials. 2020. ⟨hal-02454589⟩



Record views


Files downloads