Sparse interpolation in terms of multivariate Chebyshev polynomials

DOI10.1007/S10208-021-09535-7MaRDI QIDQ2098236zbMATH OpenOpenAlexFDO

Authors Evelyne Hubert, Michael F. Singer

Publication date 17 November 2022

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.09144

zbMATH Keywords

Chebyshev polynomialsHankel matrixroot systemssparse interpolationWeyl groups

Mathematics Subject Classification ID

Actions of groups on commutative rings; invariant theory (13A50) Representations of Lie algebras and Lie superalgebras, algebraic theory (weights) (17B10) Root systems (17B22) Moment problems and interpolation problems in the complex plane (30E05) Orthogonal polynomials and functions associated with root systems (33C52) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Symbolic computation and algebraic computation (68W30)

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.

Review text

Sparse interpolation determines an element from a linear space of functions from evaluations at particular points. This article deals with the spare interpolation problem for linear combinations of multivariate Chebyshev polynomials of first and second kind [\textit{M. E. Hoffman} and \textit{W. D. Withers}, Trans. Am. Math. Soc. 308, No. 1, 91--104 (1988; Zbl 0681.33020)]. The primarily symbolic algorithms bear similarities to a multivariate version of Prony's method and, as an intermediate step, use Hankel or mixed Hankel-Toepliz matrices for the recovery of the support of a linear form. In order to increase efficiency, it is key to exploit the underlying symmetry of the problem that comes from the interpretation of Chebyshev polynomials in terms of root systems and their Weyl group. This symmetry is the main theme in this rather long but comprehensive, well-written, and self-contained article.

Recommendations

• Sparse polynomial interpolation in Chebyshev bases
• Sparse polynomial interpolation with arbitrary orthogonal polynomial bases
• Sparse Polynomial Interpolation in Nonstandard Bases
• On sparse interpolation and the design of deterministic interpolation points
• A new algorithm for sparse interpolation of multivariate polynomials

Cites work

• A multivariate generalization of Prony's method
• Algorithms for computing cubatures based on moment theory
• An improved early termination sparse interpolation algorithm for multivariate polynomials
• Border basis relaxation for polynomial optimization
• Computation of Character Decompositions of Class Functions on Compact Semisimple Lie Groups
• Cubature formulae for orthogonal polynomials in terms of elements of finite order of compact simple Lie groups
• Discrete Fourier analysis on fundamental domain and simplex of \(A_{d}\) lattice in \(d\)-variables
• Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
• Early termination in sparse interpolation algorithms
• Error-correcting sparse interpolation in the Chebyshev basis
• Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
• Exponential data fitting and its applications
• Finite rank multivariable Hankel forms
• From quantum to classical molecular dynamics: Reduced models and numerical analysis.
• Gaussian cubature arising from hybrid characters of simple Lie groups
• Generalized Chebyshev Polynomials Associated with Affine Weyl Groups
• scientific article; zbMATH DE number 51906 (Why is no real title available?)
• scientific article; zbMATH DE number 3515658 (Why is no real title available?)
• scientific article; zbMATH DE number 1976856 (Why is no real title available?)
• scientific article; zbMATH DE number 217454 (Why is no real title available?)
• scientific article; zbMATH DE number 3231961 (Why is no real title available?)
• scientific article; zbMATH DE number 3237914 (Why is no real title available?)
• scientific article; zbMATH DE number 3274385 (Why is no real title available?)
• scientific article; zbMATH DE number 3297198 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Introduction to Lie Algebras and Representation Theory
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• Multidimensional ESPRIT for Damped and Undamped Signals: Algorithm, Computations, and Perturbation Analysis
• Multiplicative invariant theory
• Multivariate Chebyshev polynomials
• Multivariate sparse interpolation using randomized Kronecker substitutions
• On group Fourier analysis and symmetry preserving discretizations of PDEs
• On multivariate Chebyshev polynomials and spectral approximations on triangles
• Orthogonal polynomials of compact simple Lie groups
• Polynomial-exponential decomposition from moments
• Prony's method in several variables: symbolic solutions by universal interpolation
• Sparse interpolation over finite fields via low-order roots of unity
• Sparse multidimensional exponential analysis with an application to radar imaging
• Sparse polynomial interpolation in Chebyshev bases
• Sparse Polynomial Interpolation in Nonstandard Bases
• Sums of squares, moment matrices and optimization over polynomials
• Symbolic-numeric sparse interpolation of multivariate polynomials
• Symmetry groups, semidefinite programs, and sums of squares
• The BMS Algorithm
• The interpolation problem for \(k\)-sparse polynomials and character sums
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
• Through the kaleidoscope: symmetries, groups and Chebyshev-approximations from a computational point of view
• Using Algebraic Geometry
• Waring, tangential and cactus decompositions

Cited in

(13)

• Sparse polynomial interpolation with finitely many values for the coefficients
• Sparse polynomial interpolation in Chebyshev bases
• Sparse multivariate function recovery with a small number of evaluations
• Error-correcting sparse interpolation in the Chebyshev basis
• On sparse interpolation and the design of deterministic interpolation points
• Sparse sums with bases of Chebyshev polynomials of the third and fourth kind
• Sparse polynomial interpolation with arbitrary orthogonal polynomial bases
• Robust algorithms for sparse interpolation of multivariate polynomials
• Sparse interpolation of multivariate rational functions
• Orbit spaces of Weyl groups acting on compact tori: a unified and explicit polynomial description
• Sparse interpolation of symmetric polynomials
• Additive and multiplicative coinvariant spaces of Weyl groups in the light of harmonics and graded transfer
• Chebyshev varieties

This page was built for publication: Sparse interpolation in terms of multivariate Chebyshev polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2098236)