Polynomial Approximation of Symmetric Functions

arXiv (Cornell University)

Abstract

We study the polynomial approximation of symmetric multivariate functions and of multi-set functions. Specifically, we consider $f(x_1, \dots, x_N)$, where $x_i \in \mathbb{R}^d$, and $f$ is invariant under permutations of its $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$, and in particular study the dependence of that ratio on $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$ 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 · Université Bourgogne Franche-Comté · Laboratoire de Mathématiques de Besançon

   Affiliation as printed

   Laboratoire de Mathématiques de Besançon , UMR CNRS 6623 , Université Bourgogne 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 , BC , V6T 1Z2 , Canada

4. Jack Thomas

   University of Warwick

   Affiliation as printed

   Mathematics Institute , Zeeman Building , University of Warwick , CV4 7AL , UK