Polynomial approximation of symmetric functions

Bachmayr, Markus; Dusson, Geneviève; Ortner, Christoph; Thomas, Jack

doi:10.1090/mcom/3868

Polynomial approximation of symmetric functions
HTML articles powered by AMS MathViewer

by Markus Bachmayr, Geneviève Dusson, Christoph Ortner and Jack Thomas

Math. Comp. 93 (2024), 811-839

DOI: https://doi.org/10.1090/mcom/3868

Published electronically: June 28, 2023

HTML | PDF | Request permission

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.

References

Aharon Gavriel Beged-dov, Lower and upper bounds for the number of lattice points in a simplex, SIAM J. Appl. Math. 22 (1972), 106–108. MR 307685, DOI 10.1137/0122012
Huajie Chen and Christoph Ortner, QM/MM methods for crystalline defects. Part 1: Locality of the tight binding model, Multiscale Model. Simul. 14 (2016), no. 1, 232–264. MR 3463688, DOI 10.1137/15M1022628
Albert Cohen and Ronald DeVore, Approximation of high-dimensional parametric PDEs, Acta Numer. 24 (2015), 1–159. MR 3349307, DOI 10.1017/S0962492915000033
Harm Derksen and Gregor Kemper, Computational invariant theory, Second enlarged edition, Encyclopaedia of Mathematical Sciences, vol. 130, Springer, Heidelberg, 2015. With two appendices by Vladimir L. Popov, and an addendum by Norbert A’Campo and Popov; Invariant Theory and Algebraic Transformation Groups, VIII. MR 3445218, DOI 10.1007/978-3-662-48422-7
R. Drautz, Atomic cluster expansion for accurate and transferable interatomic potentials, Phys. Rev. B Condens. Matter 99 (2019), 014104.
R. Drautz and C. Ortner, Atomic cluster expansion and wave function representations, 2022, arXiv:2206.11375.
Geneviève Dusson, Markus Bachmayr, Gábor Csányi, Ralf Drautz, Simon Etter, Cas van der Oord, and Christoph Ortner, Atomic cluster expansion: completeness, efficiency and stability, J. Comput. Phys. 454 (2022), Paper No. 110946, 37. MR 4371129, DOI 10.1016/j.jcp.2022.110946
P. Erdös, On an elementary proof of some asymptotic formulas in the theory of partitions, Ann. of Math. (2) 43 (1942), 437–450. MR 6749, DOI 10.2307/1968802
Michael Griebel and Jens Oettershagen, On tensor product approximation of analytic functions, J. Approx. Theory 207 (2016), 348–379. MR 3494237, DOI 10.1016/j.jat.2016.02.006
Jiequn Han, Yingzhou Li, Lin Lin, Jianfeng Lu, Jiefu Zhang, and Linfeng Zhang, Universal approximation of symmetric and anti-symmetric functions, Commun. Math. Sci. 20 (2022), no. 5, 1397–1408. MR 4436137, DOI 10.4310/CMS.2022.v20.n5.a8
G. H. Hardy and S. Ramanujan, Asymptotic Formulaae in Combinatory Analysis, Proc. London Math. Soc. (2) 17 (1918), 75–115. MR 1575586, DOI 10.1112/plms/s2-17.1.75
I. Kaliuzhnyi and C. Ortner, Optimal evaluation of symmetry-adapted $n$-correlations via recursive contraction of sparse symmetric tensors, 2022, arXiv:2202.04140.
J. C. Mason, Near-best multivariate approximation by Fourier series, Chebyshev series and Chebyshev interpolation, J. Approx. Theory 28 (1980), no. 4, 349–358. MR 589990, DOI 10.1016/0021-9045(80)90069-6
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
C. R. Qi, H. Su, K. Mo, and L. J. Guibas, Pointnet: Deep Learning on Point Sets for 3D Classification and Segmentation, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
R.B.J.T. Allenby and A. Slomson, How to Count: An Introduction to Combinatorics, Second Edition, CRC Press, July 2011.
J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications, vol. 30, Oxford University Press, Oxford, 2005. MR 2260521, DOI 10.1093/acprof:oso/9780198568209.001.0001
Raymond A. Ryan, Introduction to tensor products of Banach spaces, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2002. MR 1888309, DOI 10.1007/978-1-4471-3903-4
Bruce E. Sagan, The symmetric group, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer-Verlag, New York, 2001. Representations, combinatorial algorithms, and symmetric functions. MR 1824028, DOI 10.1007/978-1-4757-6804-6
Jack Thomas, Huajie Chen, and Christoph Ortner, Body-ordered approximations of atomic properties, Arch. Ration. Mech. Anal. 246 (2022), no. 1, 1–60. MR 4487509, DOI 10.1007/s00205-022-01809-w
Lloyd N. Trefethen, Multivariate polynomial approximation in the hypercube, Proc. Amer. Math. Soc. 145 (2017), no. 11, 4837–4844. MR 3691999, DOI 10.1090/proc/13623
E. Wagstaff, F. Fuchs, M. Engelcke, I. Posner, and M. A. Osborne, On the limitations of representing functions on sets, in Proceedings of the 36th International Conference on Machine Learning, K. Chaudhuri and R. Salakhutdinov, eds., vol. 97 of Proceedings of Machine Learning Research, PMLR, 09–15 Jun 2019, pp. 6487–6494.
Markus Weimar, The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces, J. Approx. Theory 164 (2012), no. 10, 1345–1368. MR 2961185, DOI 10.1016/j.jat.2012.05.016
A. P. Yutsis and A. A. Bandzaitis, Theory of angular momentum in quantum mechanics, Vil’nyus (1965).
M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola, Deep Sets, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds., Advances in Neural Information Processing Systems, vol. 30, Curran Associates, Inc., 2017.