  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.
