×

Hyperbolic cross approximation in infinite dimensions. (English) Zbl 1349.41053

Summary: We give tight upper and lower bounds of the cardinality of the index sets of certain hyperbolic crosses which reflect mixed Sobolev-Korobov-type smoothness and mixed Sobolev-analytic-type smoothness in the infinite-dimensional case where specific summability properties of the smoothness indices are fulfilled. These estimates are then applied to the linear approximation of functions from the associated spaces in terms of the \(\varepsilon\)-dimension of their unit balls. Here, the approximation is based on linear information. Such function spaces appear for example for the solution of parametric and stochastic PDEs. The obtained upper and lower bounds of the approximation error as well as of the associated \(\varepsilon\)-complexities are completely independent of any parametric or stochastic dimension. Moreover, the rates are independent of the parameters which define the smoothness properties of the infinite-variate parametric or stochastic part of the solution. These parameters are only contained in the order constants. This way, linear approximation theory becomes possible in the infinite-dimensional case and corresponding infinite-dimensional problems get tractable.

MSC:

41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
41A29 Approximation with constraints
41A63 Multidimensional problems
65D15 Algorithms for approximation of functions
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Babenko, K., On the approximation of a certain class of periodic functions of several variables by trigonometric polynomials, Dokl. Akad. Nauk SSSR, 132, 247-250 (1960), English transl. in Soviet Math. Dokl., 1, (1960)
[2] Babuska, I.; Nobile, F.; Tempone, R., A stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal., 45, 1005-1034 (2007) · Zbl 1151.65008
[3] Baldeaux, J.; Gnewuch, M., Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition, SIAM J. Numer. Anal., 52, 3, 1128-1155 (2014) · Zbl 1318.65002
[4] Beck, J.; Nobile, F.; Tamellini, L.; Tempone, R., On the optimal polynomial approximation of stochastic PDEs by Galerkin and collocation methods, Math. Models Methods Appl. Sci., 22, 9, 1250023 (2012) · Zbl 1262.65009
[5] Beck, J.; Nobile, F.; Tamellini, L.; Tempone, R., Convergence of quasi-optimal stochastic Galerkin methods for a class of PDEs with random coefficients, Comput. Math. Appl., 67, 4, 732-751 (2014) · Zbl 1350.65003
[6] Beged-Dov, A., Lower and upper bounds for the number of lattice points in a simplex, SIAM J. Appl. Math., 22, 1, 106-108 (1972) · Zbl 0242.90027
[7] Bratteli, O.; Robinson, D., Operator Algebras and Quantum Statistical Mechanics, Vol. 1 (2002), Springer-Verlag
[8] Bungartz, H.-J.; Griebel, M., Sparse grids, Acta Numer., 13, 1-123 (2004)
[9] Chernov, A.; Dũng, D., New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness, J. Complexity (2015)
[10] Chkifa, A., Sparse polynomial methods in high dimension. Application to parametric PDE (2014), Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie Paris, (PhD-Thesis)
[11] Chkifa, A.; Cohen, A.; DeVore, R.; Schwab, C., Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs, ESAIM Math. Model. Numer. Anal., 47, 1, 253-280 (2013) · Zbl 1273.65009
[12] Chkifa, A.; Cohen, A.; Schwab, C., High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs, Found. Comput. Math., 14, 4, 601-633 (2014) · Zbl 1298.65022
[13] Cohen, A.; DeVore, R.; Schwab, C., Convergence rates of best N-term Galerkin approximations for a class of elliptic sPDEs, Found. Comput. Math., 10, 6, 615-646 (2010) · Zbl 1206.60064
[14] Cohen, A.; DeVore, R.; Schwab, C., Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDEs, Anal. Appl., 9, 1, 11-47 (2011) · Zbl 1219.35379
[15] Creutzig, J.; Dereich, S.; Müller-Gronbach, T.; Ritter, K., Infinite-dimensional quadrature and approximation of distributions, Found. Comput. Math., 9, 391-429 (2009) · Zbl 1177.65011
[16] Dick, J.; Gnewuch, M., Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition, J. Approx. Theory, 184, 111-145 (2014) · Zbl 1296.41025
[17] Dick, J.; Gnewuch, M., Infinite-dimensional integration in weighted Hilbert spaces: Anchored decompositions, optimal deterministic algorithms, and higher-order convergence, Found. Comput. Math., 14, 5, 1027-1077 (2014) · Zbl 1312.65002
[18] Dick, J.; Kuo, F.; Sloan, I., High-dimensional integration: The quasi-Monte Carlo way, Acta Numer., 22, 133-288 (2013) · Zbl 1296.65004
[19] Dũng, D., Some approximative characteristics of the classes of smooth functions of several variables in the metric of \(L_2\), Uspekhi Mat. Nauk, 34, 189-190 (1979) · Zbl 0435.41009
[20] Dũng, D., Mean \(\varepsilon \)-dimension of the functional class \(B_{G, p}\), Mat. Zametki, 28, 727-736 (1980) · Zbl 0462.42014
[21] Dũng, D., The number of integral points in some sets and approximation of functions of several variables, Mat. Zametki, 36, 479-491 (1984)
[22] Dũng, D., Approximation of functions of several variables on tori by trigonometric polynomials, Mat. Sb., 131, 251-271 (1986) · Zbl 0634.42005
[23] Dũng, D., Sampling and cubature on sparse grids based on a B-spline quasi-interpolation, Found. Comput. Math. (2015)
[24] Dũng, D.; Dryanov, D., The minimal number of sample values for recovery of non-bandlimited functions, Atti Semin. Mat. Fis. Univ. Modena, 39, 423-431 (1991) · Zbl 0768.41024
[25] Dũng, D.; Magaril-Il’jaev, G., Problems of Bernstein and Favard type and the mean \(\varepsilon \)-dimension of some classes functions, Dokl. Akad. Nauk SSSR, 249, 783-786 (1979)
[26] Dũng, D.; Ullrich, T., N-widths and \(\varepsilon \)-dimensions for high-dimensional approximations, Found. Comput. Math., 13, 965-1003 (2013) · Zbl 1284.42001
[27] Fasshauer, G.; Hickernell, F.; Woźniakowski, H., On dimension-independent rates of convergence for function approximation with Gaussian kernels, SIAM J. Numer. Anal., 50, 1, 247-271 (2012) · Zbl 1243.65025
[28] Gerstner, T.; Griebel, M., Dimension-adaptive tensor-product quadrature, Computing, 71, 1, 65-87 (2003) · Zbl 1030.65015
[29] Gnewuch, M., Infinite-dimensional integration on weighted Hilbert spaces, Math. Comp., 81, 2175-2205 (2012) · Zbl 1284.65044
[30] Gnewuch, M.; Mayer, S.; Ritter, K., On weighted Hilbert spaces and integration of functions of infinitely many variables, J. Complexity, 30, 2, 29-47 (2014) · Zbl 1286.65039
[31] Griebel, M.; Harbrecht, H., A note on the construction of \(L\)-fold sparse tensor product spaces, Constr. Approx., 38, 2, 235-251 (2013) · Zbl 1283.41015
[32] Griebel, M.; Oettershagen, J., Dimension-adaptive sparse grid quadrature for integrals with boundary singularities, (Garcke, J.; Pflüger, D., Sparse Grids and Applications. Sparse Grids and Applications, Lecture Notes in Computational Science and Engineering, vol. 97 (2014), Springer), 109-136 · Zbl 1316.65032
[33] Gunzburger, M.; Webster, C.; Zhang, G., Stochastic finite element methods for partial differential equations with random input data, Acta Numer., 23, 521-650 (2014) · Zbl 1398.65299
[34] Hickernell, F.; Müller-Gronbach, T.; Niu, B.; Ritter, K., Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(R^N\), J. Complexity, 26, 229-254 (2010) · Zbl 1207.65005
[35] Hickernell, F.; Wang, X., The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Math. Comp., 71, 1641-1661 (2002) · Zbl 1032.65006
[36] Hoang, V.; Schwab, C., N-term Wiener chaos approximation rates for elliptic PDEs with log-normal Gaussian random inputs, Math. Models Methods Appl. Sci., 24, 4, 797-826 (2014) · Zbl 1294.65010
[37] Jakeman, J.; Roberts, S., Local and dimension adaptive stochastic collocation for uncertainty quantification, (Griebel, M.; Garcke, J., Sparse Grids and Applications. Sparse Grids and Applications, Lecture Notes in Computational Science and Engineering, vol. 88 (2013), Springer), 181-203
[38] Kolmogorov, A., Über die beste Annäherung von Funktionen einer Funktionklasse, Ann. of Math., 37, 107-111 (1936)
[40] Kühn, T.; Sickel, W.; Ullrich, T., Approximation numbers of Sobolev embeddings - sharp constants and tractability, J. Complexity, 30, 95-116 (2014) · Zbl 1334.47028
[41] Kühn, T.; Sickel, W.; Ullrich, T., Approximation of mixed order Sobolev functions on the d-torus - asymptotics, preasymptotics and d-dependence, Constr. Approx. (2015) · Zbl 1485.47025
[42] Kuo, F.; Sloan, I.; Wasilkowski, G.; Woźniakowski, H., Liberating the dimension, J. Complexity, 26, 422-454 (2010) · Zbl 1203.65057
[43] Le Maître, O.; Knio, O., (Spectral Methods for Uncertainty Quantification. Spectral Methods for Uncertainty Quantification, Scientific Computation (2010), Springer: Springer New York) · Zbl 1193.76003
[44] Niu, B.; Hickernell, F.; Müller-Gronbach, T.; Ritter, K., Deterministic multilevel algorithms for infinite-dimensional integration on \(R^N\), J. Complexity, 27, 331-351 (2011) · Zbl 1218.65005
[45] Nobile, F.; Tempone, R.; Webster, C., A sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal., 46, 5, 2309-2345 (2008) · Zbl 1176.65137
[46] Nobile, F.; Tempone, R.; Webster, C., An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal., 46, 5, 2411-2442 (2008) · Zbl 1176.65007
[47] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems, Volume I: Linear Information. Tractability of Multivariate Problems, Volume I: Linear Information, EMS Tracts in Mathematics, vol. 6 (2008), Eur. Math. Soc. Publ. House: Eur. Math. Soc. Publ. House Zürich) · Zbl 1156.65001
[48] Padberg, M., A remark on “An inequality for the number of lattice points in a simplex”, SIAM J. Appl. Math., 20, 4, 638-641 (1971) · Zbl 0235.90040
[49] Papageorgiou, A.; Woźniakowski, H., Tractability through increasing smoothness, J. Complexity, 26, 409-421 (2010) · Zbl 1221.65106
[50] Plaskota, L.; Wasilkowski, G., Tractability of infinite-dimensional integration in the worst case and randomized settings, J. Complexity, 27, 505 (2011) · Zbl 1230.65037
[51] Plaskota, L.; Wasilkowski, G.; Woźniakowski, H., A new algorithm and worst case complexity for Feynman-Kac path integration, J. Comput. Phys., 164, 335-353 (2000) · Zbl 1052.81520
[52] Sloan, I.; Woźniakowski, H., When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. Complexity, 14, 1-33 (1998) · Zbl 1032.65011
[53] Sloan, I.; Woźniakowski, H., Tractability of multivariate integration for weighted Korobov classes, J. Complexity, 17, 697-721 (2001) · Zbl 0998.65004
[54] Sloan, I.; Woźniakowski, H., Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces, J. Complexity, 18, 479-499 (2002) · Zbl 1011.65008
[55] Temlyakov, V., Approximation of Functions with Bounded Mixed Derivative (1986), Nauka: Nauka Moscow, English transl. in Proceedings of Steklov Inst., AMS, Providence, 1989 · Zbl 0625.41028
[56] Tikhomirov, V., Widths of sets in function spaces and the theory of best approximations, Uspekhi Mat. Nauk, 15, (3)93, 81-120 (1960), English translation in Russian Math. Survey, 15, 1960
[57] Tran, H.; Webster, C.; Zhang, G., Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients, report ORNL/TM-2014/468 (2015), Department of Computational and Applied Mathematics, Computer Science and Mathematics Division, Oak Ridge National Laboratory
[58] Wasilkowski, G., Liberating the dimension for function approximation and integration, (Plaskota, L.; Woźniakowski, H., Monte Carlo and Quasi-Monte Carlo Methods 2012 (2012), Springer: Springer Heidelberg), 211-231 · Zbl 1271.65049
[59] Wasilkowski, G., Liberating the dimension for \(L_2\)-approximation, J. Complexity, 28, 304-319 (2012) · Zbl 1247.65013
[60] Wasilkowski, G.; Woźniakowski, H., On tractability of path integration, J. Math. Phys., 37, 2071-2088 (1996) · Zbl 0863.65006
[61] Wasilkowski, G.; Woźniakowski, H., Liberating the dimension for function approximation, J. Complexity, 27, 86-110 (2011) · Zbl 1208.65024
[62] Wasilkowski, G.; Woźniakowski, H., Liberating the dimension for function approximation: Standard information, J. Complexity, 27, 417-440 (2011) · Zbl 1227.65140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.