Complexity of Monte Carlo integration for Besov classes on the unit sphere
Tóm tắt
We obtain the exact orders of the complexity of the integration of functions from Besov classes
$$BB_{p,\theta }^\Omega$$
on the unit sphere of d-dimensional Euclidean space in the deterministic and randomized settings. The corresponding optimal quadrature rules have been constructed in both settings. Our results show that Monte Carlo algorithm can provide a faster convergence rate than that of the deterministic one. Quantitatively, the improvement amounts to the factors
$$N^{-1/2}$$
for
$$2\le p\le \infty$$
and
$$N^{-1+1/p}$$
for
$$1< p<2$$
, where N is the number of function evaluations involved into the computational process.
Tài liệu tham khảo
Bakhvalov, N.S.: On a rate of convergence of indeterministic integration processes within the functional classes \(W_p^{(l)}\). Theory Probab. Appl. 7, 227 (1962)
Beckmann, J., Mhaskar, H.N., Prestin, J.: Local numerical integration on the sphere. GEM Int. J. Geomath. 5, 143–162 (2014)
Brauchart, J.S., Dick, J.: Quasi-Monte Carlo rules for numerical integration over the unit sphere. Numer. Math. 121(3), 473–502 (2012)
Brauchart, J.S., Hesse, K.: Numerical integration over spheres of arbitrary dimension. Constr. Approx. 25, 41–71 (2007)
Brown, G., Dai, F.: Approximation of smooth functions on compact two-point homogeneous spaces. J. Funct. Anal. 220, 401–423 (2005)
Cao, F.L., Lin, S.B., Chang, X.Y., Xu, Z.B.: Learning rates of regularized regression on the unit sphere. Sci. China Math. 56, 861–876 (2013)
Dai, F., Wang, H.P.: Optimal cubature formulas in weighted Besov spaces with \(A_\infty\) weights on multivariate domains. Constr. Approx. 37, 167–194 (2013)
Dai, F., Xu, Y.: Approximation Theory and Harmonics Analysis on Spheres and Balls. Springer, New York (2013)
Duan, L.Q., Ye, P.X.: Information complexity of Monte Carlo integration in Sobolev classes with mixed derivative. Information 15, 83–90 (2012)
Duan, L.Q., Ye, P.X.: Complexity of the integration on Hölder–Nikolskii classes with mixed smoothness. Appl. Math. Inf. Sci. 10(1), 351–356 (2016)
Duan, L.Q., Ye, P.X.: Randomized approximation numbers on Besov classes with mixed smoothness. Int. J. Wavelets Multiresolut. Inf. Process. 18(4), 2050023 (2020)
Fang, G.S., Ye, P.X.: Integration error for multivariate functions from anisotropic classes. J. Complex. 19, 610–627 (2003)
Freeden, W.: Multiscale Modelling of Spaceborne Geodata. B.G. Teubner, Stuttgart (1999)
Grabner, P.J., Stepanyuk, T.A.: Upper and lower estimates for numerical integration errors on spheres of arbitrary dimension. J. Complex. 53, 113–132 (2019)
Heinrich, S.: Random approximation in numerical analysis. In: Bierstedt, K.D., et al. (eds.) Functional Analysis: Proceedings of the Essen Conference, vol. 150. Lecture Notes in Pure and Applied Mathematics, pp. 123–171, New York (1994)
Heinrich, S.: Quantum summation with an application to integration. J. Complex. 18, 1–50 (2002)
Heinrich, S.: Quantum integration in Sobolev classes. J. Complex. 19, 19–42 (2003)
Hesse, K.: A lower bound for the worst-case cubature error on spheres of arbitrary dimension. Numer. Math. 103, 413–433 (2006)
Hesse, K., Mhaskar, H.N., Sloan, I.H.: Quadrature in Besov spaces on the Euclidean sphere. J. Complex. 23, 528–552 (2007)
Hesse, K., Sloan, I.H., Womersley, R.S.: Numerical integration on the sphere. In: Freeden, W., Nashed, Z., Sonar, T. (eds.) Handbook of Geomathematics. Springer, Berlin (2010)
Huang, Z.X., Wang, H.P.: Optimal recovery of functions on the sphere on a Sobolev spaces with a Gaussian measure in the average case setting. Anal. Theory Appl. 31(2), 154–166 (2015)
König, H.: Eigenvalue Distribution of Compact Operators. Birkhauser, Basel (1986)
Krieg, D., Novak, E.: A universal algorithm for multivariate integration. Found. Comput. Math. 17, 895–916 (2017)
Lin, S.B.: Nonparametric regression using needlet kernels spherical data. J. Complex. 50, 66–83 (2019)
Lozorkin, P.I., Rustamov, K.P.: On some equivalent normings of a Nikolskii–Besov space on the sphere. Sov. Math. Dokl. 45, 58–62 (1992)
Mathé, P.: Approximation Theory of Stochastic Numerical Methods. Habilitationsschrift, Fachbereich Mathematik, Freie Universität Berlin (1994)
Muscalu, C., Schlag, W.: Classical and Multilinear Harmonic Analysis, vol. I. Cambridge University Press, New York (2013)
Novak, E.: Deterministic and Stochastic Error Bound in Numerical Analysis. Lecture Notes in Mathematics, vol. 1349. Springer, Berlin (1988)
Novak, E.: Stochastic properties of quadrature formulas. Numer. Math. 53, 609–620 (1988)
Pawelke, S.: Über die Approximationsordnung bei Kugelfunktionen und algebraischen Polynomen. Tôhoku Math. J. 24, 473–486 (1972)
Reimer, M.: Multivariate Polynomial Approximation. Birkhäuser, Basel (2003)
Sloan, I.H., Womersley, R.S.: Extremal systems of points and numerical integration on the sphere. Adv. Comput. Math. 21, 107–125 (2004)
Traub, J.F., Wasilkowski, G.W., Woźniakowski, H.: Information-Based Complexity. Academic Press, New York (1988)
Ullrich, M., Ullrich, T.: The role of Frolov’s cubature formula for functions with bounded mixed derivative. SIAM J. Numer. Anal. 54, 969–993 (2016)
Ullrich, M.: A Monte Carlo method for integration of multivariate smooth functions. SIAM J. Numer. Anal. 55, 1188–1200 (2017)
Wang, H.P.: Optimal lower estimates for the worse case cubature error and the approximation by hyperinterpolation operators in the Sobolev space setting on the sphere. Int. J. Wavelets Multiresolut. Inf. Process. 7(6), 813–823 (2009)
Wang, H.P., Tang, S.: Widths of Besov classes of generalized smoothness on the sphere. J. Complex. 28, 468–488 (2012)
Wang, H.P., Wang, K.: Optimal recovery of Besov classes of generalized smoothness and Sobolev classes on the sphere. J. Complex. 32, 40–52 (2016)
Wang, H.P., Xu, G.Q.: Sampling numbers of a class of infinitely differentiable functions. J. Math. Anal. Appl. 484, 123689 (2020)
Xu, G.Q., Liu, Z.H., Wang, H.: Sample numbers and optimal Lagrange interpolation of Sobolev spaces \(W_{1}^{r}\). Chin. Ann. Math. Ser. B 42, 519–528 (2021)
Zhang, J., Liu, Y.P.: Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls. Int. J. Wavelets Multiresolut. Inf. Process. 17(6), 1950043 (2019)