Finding minimax approximation of a permutation equivariant polynomial

Question

Is there any known method to approximate a given permutation-equivariant smooth function $f: \mathbb{R}^{n} \to \mathbb{R}^{n}$ as multivariable polynomial function $p: \mathbb{R}^{n} \to \mathbb{R}^{n}$ on a given domain $D\subset \mathbb{R}^{n}$, let's say, $[-1, 1]^{n}$ or a unit ball centered at the origin? Here permutation-equivariant means that we have $f(\sigma(\mathbf{x})) = \sigma(f(\mathbf{x}))$ for any $\sigma \in S_n$ ($S_n$ acts on $\mathbb{R}^{n}$ by permuting indices), such as argmax/min function. Minimax approximation means that we want to minimize $L^\infty$ loss in the sense that we want $||p(\mathbf{x}) - f(\mathbf{x})||_{D, \infty}$ to be small. In case of $n=1$ (when permutation equivariant condition is vacuous), Remez's algorithm give a way to find a minimax polynomial approximation on a given interval. It seems that there's no analogue of Remez's algorithm in case of higher dimensions yet, so I wonder if there's any other way to obtain a good approximation. Thanks in advance.

Answer 1

First, if you wish to preserve permutation invariance, you can use the fact that any smooth permutation invariant $f(\mathbf{x}) = F(\mathbf{e})$ for some smooth function $F$ of the elementary symmetric polynomials $\mathbf{e} = (e_1(\mathbf{x}), \ldots, e_n(\mathbf{x}))$. This result is due to Glaeser (1963) (a generalization to smooth invariants on a representation of a compact Lie group is due to Schwarz (1975)).

• Glaeser, Georges, Fonctions composees différentiables, Ann. Math. (2) 77, 193-209 (1963). ZBL0106.31302.
• Schwarz, Gerald W., Smooth functions invariant under the action of a compact Lie group, Topology 14, 63-68 (1975). ZBL0297.57015.

The the problem of approximation of $f(\mathbf{x})$ by an invariant polynomial on say $[0,1]^n$ is reduced to an ordinary polynomial approximation of $F(\mathbf{e})$ on the image of the simplex $\mathbf{e}(\Delta) = \{ \mathbf{e}(\mathbf{x}) \mid 0\le x_1 \le \cdots \le x_n \le 1 \}$, with similar reductions for other domains.

As to actual uniform multivariariate polynomial approximation (also called Chebyshev approximation), I unfortunately don't know much about it. So I'm not sure what the state of the art is, but there does seem to be some recent literature on it, which at least studies the optimality conditions in higher dimensions. For example this one and other publications by Sukhorukova:

• Sukhorukova, Nadezda; Ugon, Julien; Yost, David, Chebyshev multivariate polynomial approximation: alternance interpretation, Wood, David R. (ed.) et al., 2016 MATRIX annals. Cham: Springer (ISBN 978-3-319-72298-6/hbk; 978-3-319-72299-3/ebook). MATRIX Book Series 1, 177-182 (2018). ZBL1401.41019 arXiv:1510.06076

EDIT: About equivariance. There is a trick (or tricks) to go from equivariant functions to invariant ones and back.

The first one introduces an extra vector variable $\mathbf{y}\in \mathbb{R}^n$ so that $g(\mathbf{x},\mathbf{y}) = \mathbf{y}\cdot f(\mathbf{x})$ is invariant under the simultaneous permutation action on $\mathbf{x}$ and $\mathbf{y}$, while $f(\mathbf{x}) = \partial g(\mathbf{x}, \mathbf{y})/\partial \mathbf{y} |_{\mathbf{y}=0}$ for any invariant $g(\mathbf{x},\mathbf{y})$. The problem is that now $g(\mathbf{x},\mathbf{y})$ factors through invariant polynomials that can depend on both $\mathbf{x}$ and $\mathbf{y}$, so the generating set is larger than just the elementary symmetric polynomials $\mathbf{e}(\mathbf{x})$.

Another way notices that for any $\mathbf{x} \in \mathbb{R}^n$ with pairwise unequal components, the vectors $\mathbf{x}^k = (x_1^k,\ldots, x_n^k)$ are linearly independent. Then the invariant functions $f_k(\mathbf{x}) = \mathbf{x}^k \cdot f(\mathbf{x})$ uniquely determine the components of $f(\mathbf{x})$ on an open dense subset of $\mathbb{R}^n$ and hence everywhere. With a little bit of work you can rearrange this observation into a representation $f(\mathbf{x}) = \sum_{k=0}^n g_k(\mathbf{x}) \mathbf{x}^k$, where each scalar $g_k(\mathbf{x})$ is now invariant, but possibly divergent along the subspaces where one or more coordinates of $\mathbf{x}$ coincide.

These tricks might interact in different ways with the uniform approximation, so I can't say which one would be best for your needs.