Polynomial approximation of symmetric functions

Mathematics of Computation, vol. 93, pp. 811–839

Abstract

We study the polynomial approximation of symmetric multivariate functions and of multi-set functions. Specifically, we consider f ( x 1 , … , x N ) f(x_1, \dots , x_N) , where x i ∈ R d x_i \in \mathbb {R}^d , and f f is invariant under permutations of its N N arguments. We demonstrate how these symmetries can be exploited to improve the cost versus error ratio in a polynomial approximation of the function f f , and in particular study the dependence of that ratio on d , N d, N and the polynomial degree. These results are then used to construct approximations and prove approximation rates for functions defined on multi-sets where N N becomes a parameter of the input.

Authors 4

1. Markus Bachmayr Aachen Institut für Geometrie und Praktische Mathematik

   RWTH Aachen University

   Affiliation as printed

   Institut für Geometrie und Praktische Mathematik, RWTH Aachen University, Templergraben 55, 52056 Aachen, Germany

2. Geneviève Dusson

   Centre National de la Recherche Scientifique · Laboratoire de Mathématiques de Besançon · Université de Franche-Comté

   Affiliation as printed

   Laboratoire de Mathématiques de Besançon, UMR CNRS 6623, Université de Franche-Comté, 16 route de Gray, 25030 Besançon, France

3. Christoph Ortner

   University of British Columbia

   Affiliation as printed

   Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, British Columbia, V6T 1Z2, Canada

4. Jack Thomas

   University of Warwick

   Affiliation as printed

   Mathematics Institute, Zeeman Building, University of Warwick, CV4 7AL, United Kingdom