Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Foundations of Computational Mathematics
Published in: Foundations of Computational Mathematics 6/2022

09-09-2021

Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials

Authors: Evelyne Hubert, Michael F. Singer

Published in: Foundations of Computational Mathematics | Issue 6/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Matrix Concentration for Products
next article Deep Composition of Tensor-Trains Using Squared Inverse Rosenblatt Transports

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
in the proof we show that the distance to the nearest integer is less than \(\frac{1}{2}\) so this is well defined.
 
2
To simplify notation, we will not introduce new symbols to distinguish between an element of \(\mathbb {K}[x^{\pm }]\) and its image in \(\mathbb {K}[x^{\pm }]/J\).
 
Literature
1.
M. Abril Bucero and B. Mourrain. Border basis relaxation for polynomial optimization. Journal of Symbolic Computation, 74:378 – 399, 2016.
2.
A. Arnold. Sparse Polynomial Interpolation and Testing. PhD thesis, University of Waterloo, 3 2016.
3.
A. Arnold, M. Giesbrecht, and D. Roche. Sparse interpolation over finite fields via low-order roots of unity. In ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 27–34. ACM, New York, 2014.
4.
A. Arnold and E. Kaltofen. Error-correcting sparse interpolation in the Chebyshev basis. In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’15, pages 21–28, New York, NY, USA, 2015. ACM.
5.
A. Arnold and D. Roche. Multivariate sparse interpolation using randomized Kronecker substitutions. In ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 35–42. ACM, New York, 2014.
6.
T. Becker and V. Weispfenning. Gröbner Bases - A Computational Approach to Commutative Algebra. Springer-Verlag, New York, 1993.MATH
7.
M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pages 301–309, New York, NY, USA, 1988. ACM.
8.
9.
J. Berthomieu, B. Boyer, and J.-C. Faugère. Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences. Journal of Symbolic Computation, 83:36 – 67, 2017. Special issue on the conference ISSAC 2015: Symbolic computation and computer algebra.
10.
N. Bourbaki. Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines. Actualités Scientifiques et Industrielles, No. 1337. Hermann, Paris, 1968.
11.
N. Bourbaki. Éléments de mathématique. Fasc. XXXVIII: Groupes et algèbres de Lie. Chapitre VII: Sous-algèbres de Cartan, éléments réguliers. Chapitre VIII: Algèbres de Lie semi-simples déployées. Actualités Scientifiques et Industrielles, No. 1364. Hermann, Paris, 1975.
12.
13.
M. Collowald and E. Hubert. Algorithms for computing cubatures based on moment theory. Studies in Applied Mathematics, 141(4):501–546, 2018.MathSciNetCrossRefMATH
14.
D. Cox, J. Little, and D. O’Shea. Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. An introduction to computational algebraic geometry and commutative algebra.
15.
D. A. Cox, J. Little, and D. O’Shea. Using algebraic geometry, volume 185 of Graduate Texts in Mathematics. Springer, New York, second edition, 2005.
16.
A. Cuyt, Y. Hou, F. Knaepkens, and W.-S. Lee. Sparse multidimensional exponential analysis with an application to radar imaging. SIAM J. Sci. Comput., 42(3):B675–B695, 2020.MathSciNetCrossRefMATH
17.
J. Dieudonné. Special functions and linear representations of Lie groups, volume 42 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, R.I., 1980. Expository lectures from the CBMS Regional Conference held at East Carolina University, Greenville, North Carolina, March 5–9, 1979.
18.
A. Dress and J. Grabmeier. The interpolation problem for \(k\)-sparse polynomials and character sums. Adv. in Appl. Math., 12(1):57–75, 1991.MathSciNetCrossRefMATH
19.
W. Fulton and J. Harris. Representation theory, volume 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991. A first course, Readings in Mathematics.
20.
K. Gatermann and P. A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra, 192(1-3):95–128, 2004.MathSciNetCrossRefMATH
21.
M. Giesbrecht, G. Labahn, and W. Lee. Symbolic-numeric sparse polynomial interpolation in chebyshev basis and trigonometric interpolation. In CASC 2004, 2004.
22.
M. Giesbrecht, G. Labahn, and W.-S. Lee. Symbolic-numeric sparse interpolation of multivariate polynomials. J. Symbolic Comput., 44(8):943–959, 2009.MathSciNetCrossRefMATH
23.
W. H. Greub. Linear algebra. Third edition. Die Grundlehren der Mathematischen Wissenschaften, Band 97. Springer-Verlag New York, Inc., New York, 1967.
24.
D. Grigoriev, M. Karpinski, and M. Singer. The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators. Adv. in Appl. Math., 12(1):76–81, 1991.MathSciNetCrossRefMATH
25.
B. Hall. Lie groups, Lie algebras, and representations, volume 222 of Graduate Texts in Mathematics. Springer, Cham, second edition, 2015. An elementary introduction.
26.
M. Hoffman and W. Withers. Generalized Chebyshev polynomials associated with affine Weyl groups. Trans. Amer. Math. Soc., 308(1):91–104, 1988.MathSciNetCrossRefMATH
27.
Q. Huang. An improved early termination sparse interpolation algorithm for multivariate polynomials. J. Syst. Sci. Complex., 31(2):539–551, 2018.MathSciNetCrossRefMATH
28.
J. Humphreys. Introduction to Lie algebras and representation theory. Springer-Verlag, New York-Berlin, 1972. Graduate Texts in Mathematics, Vol. 9.
29.
E. Kaltofen and Y. Lakshman. Improved sparse multivariate polynomial interpolation algorithms. In Symbolic and algebraic computation (Rome, 1988), volume 358 of Lecture Notes in Comput. Sci., pages 467–474. Springer, Berlin, 1989.
30.
E. Kaltofen and W.-S. Lee. Early termination in sparse interpolation algorithms. J. Symbolic Comput., 36(3-4):365–400, 2003. International Symposium on Symbolic and Algebraic Computation (ISSAC’2002) (Lille).
31.
E. Kaltofen, W.-S. Lee, and A. Lobo. Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel’s algorithm. In Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (St. Andrews), pages 192–201, New York, 2000. ACM.
32.
S. Kunis, T. Peter, T. Römer, and U. von der Ohe. A multivariate generalization of Prony’s method. Linear Algebra Appl., 490:31–47, 2016.MathSciNetCrossRefMATH
33.
34.
M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, volume 149 of IMA Vol. Math. Appl., pages 157–270. Springer, New York, 2009.
35.
H. Li and Y. Xu. Discrete Fourier analysis on fundamental domain and simplex of \(A_d\) lattice in \(d\)-variables. J. Fourier Anal. Appl., 16(3):383–433, 2010.MathSciNetCrossRefMATH
36.
M. Lorenz. Multiplicative invariant theory, volume 135 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, Berlin, 2005. Invariant Theory and Algebraic Transformation Groups, VI.
37.
C. Lubich. From quantum to classical molecular dynamics: reduced models and numerical analysis. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zürich, 2008.
38.
V. D. Lyakhovsky and Ph. V. Uvarov. Multivariate Chebyshev polynomials. J. Phys. A, 46(12):125201, 22, 2013.
39.
R. Moody, L. Motlochová, and J. Patera. Gaussian cubature arising from hybrid characters of simple Lie groups. J. Fourier Anal. Appl., 20(6):1257–1290, 2014.MathSciNetCrossRefMATH
40.
R. Moody and J. Patera. Computation of character decompositions of class functions on compact semisimple Lie groups. Math. Comp., 48(178):799–827, 1987.MathSciNetCrossRefMATH
41.
R. Moody and J. Patera. Cubature formulae for orthogonal polynomials in terms of elements of finite order of compact simple Lie groups. Adv. in Appl. Math., 47(3):509–535, 2011.MathSciNetCrossRefMATH
42.
B. Mourrain. Polynomial–exponential decomposition from moments. Foundations of Computational Mathematics, 18(6):1435–1492, Dec 2018.MathSciNetCrossRefMATH
43.
H. Munthe-Kaas. On group Fourier analysis and symmetry preserving discretizations of PDEs. J. Phys. A, 39(19):5563–5584, 2006.MathSciNetCrossRefMATH
44.
H. Munthe-Kaas, M. Nome, and B. Ryland. Through the kaleidoscope: symmetries, groups and Chebyshev-approximations from a computational point of view. In Foundations of computational mathematics, Budapest 2011, volume 403 of London Math. Soc. Lecture Note Ser., pages 188–229. Cambridge Univ. Press, Cambridge, 2013.
45.
M. Nesterenko, J. Patera, and A. Tereszkiewicz. Orthogonal polynomials of compact simple Lie groups. Int. J. Math. Math. Sci., 2011.
46.
47.
48.
49.
C. (Baron de Prony) Riche. Essai expérimental et analytique sur les lois de la dilatabilité des fluides élastique et sur celles de la force expansive de la vapeur de l’eau et de la vapeur de l’alkool, à différentes températures. J. de l’École Polytechnique, 1:24–76, 1795.
50.
C. Riener, T. Theobald, L. J. Andrén, and J. B. Lasserre. Exploiting symmetries in SDP-relaxations for polynomial optimization. Math. Oper. Res., 38(1):122–141, 2013.MathSciNetCrossRefMATH
51.
B. Ryland and H. Munthe-Kaas. On multivariate Chebyshev polynomials and spectral approximations on triangles. In Spectral and high order methods for partial differential equations, volume 76 of Lect. Notes Comput. Sci. Eng., pages 19–41. Springer, Heidelberg, 2011.
52.
S. Sahnoun, K. Usevich, and P. Comon. Multidimensional ESPRIT for Damped and Undamped Signals: Algorithm, Computations, and Perturbation Analysis. IEEE Transactions on Signal Processing, 65(22):5897–5910, 2017.MathSciNetCrossRefMATH
53.
S. Sakata. The BMS algorithm. In M. Sala, S. Sakata, T. Mora, C. Traverso, and L. Perret, editors, Gröbner Bases, Coding, and Cryptography, pages 143–163. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.CrossRef
54.
T. Sauer. Prony’s method in several variables: symbolic solutions by universal interpolation. J. Symbolic Comput., 84:95–112, 2018.MathSciNetCrossRefMATH
55.
J.-P. Serre. Algèbres de Lie semi-simples complexes. W. A. Benjamin, inc., New York-Amsterdam, 1966.MATH
56.
N. Vilenkin. Special functions and the theory of group representations. Translated from the Russian by V. N. Singh. Translations of Mathematical Monographs, Vol. 22. American Mathematical Society, Providence, R. I., 1968.
Metadata
Title
Sparse Interpolation in Terms of Multivariate Chebyshev Polynomials
Authors
Evelyne Hubert
Michael F. Singer
Publication date
09-09-2021
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 6/2022
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-021-09535-7

Other articles of this Issue 6/2022

Foundations of Computational Mathematics 6/2022 Go to the issue

OriginalPaper

Matrix Concentration for Products

OriginalPaper

Euclidean Distance Degree and Mixed Volume

OriginalPaper

Deep Composition of Tensor-Trains Using Squared Inverse Rosenblatt Transports

OriginalPaper

Tropical Bisectors and Voronoi Diagrams

OriginalPaper

Robust Group Synchronization via Cycle-Edge Message Passing

Premium Partner

    Image Credits