Tractability of multivariate problems. Volume II: Standard information for functionals.

DOI10.4171/084zbMath1241.65025OpenAlexW2497677836MaRDI QIDQ982085

Henryk Woźniakowski, Erich Novak

Publication date: 5 July 2010

Published in: EMS Tracts in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4171/084

zbMATH Keywords

monographalgorithmsquantum computationlattice rulespath integrationnonlinear functionalsdecomposable kernelsnumerical multivariate integrationSmolyak/sparse grid algorithmstractability of multivariate problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Multidimensional problems (41A63) Algorithms for approximation of functions (65D15) Approximate quadratures (41A55) Numerical quadrature and cubature formulas (65D32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)

Related Items

On the power of standard information for tractability for \(L_2\)-approximation in the average case setting, A simplified criterion for quasi-polynomial tractability of approximation of random elements and its applications, A note on tractability of multivariate analytic problems, Optimal sampling points in reproducing kernel Hilbert spaces, Approximation in Hermite spaces of smooth functions, Tractability of multivariate problems for standard and linear information in the worst case setting. I., Tractability of multivariate approximation defined over Hilbert spaces with exponential weights, Optimal approximation of multivariate periodic Sobolev functions in the sup-norm, Sampling discretization and related problems, Approximation numbers of Sobolev and Gevrey type embeddings on the sphere and on the ball -- preasymptotics, asymptotics, and tractability, The curse of dimensionality for numerical integration on general domains, Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions, Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, Novel results for the anisotropic sparse grid quadrature, Product rules are optimal for numerical integration in classical smoothness spaces, A new characterization of \((s,t)\)-weak tractability, BMO and exponential Orlicz space estimates of the discrepancy function in arbitrary dimension, Average approximation of tensor product-type random fields of increasing dimension, Tractability of \(\mathbb{L}_2\)-approximation in hybrid function spaces, Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, Tractability of the Fredholm problem of the second kind, Quasi-Monte Carlo tractability of high dimensional integration over products of simplices, Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements, Construction of scrambled polynomial lattice rules over \(\mathbb{F}_{2}\) with small mean square weighted \(\mathcal{L}_{2}\) discrepancy, Lower bounds for the complexity of linear functionals in the randomized setting, Liberating the dimension for function approximation, On evil Kronecker sequences and lacunary trigonometric products, Quadrature for self-affine distributions on \(\mathbb R^d\), On a projection-corrected component-by-component construction, New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness, Random weights, robust lattice rules and the geometry of the \(cbcrc\) algorithm, Tight tractability results for a model second-order Neumann problem, Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence, Tractability of approximating multivariate linear functionals, Approximation in probability of tensor product-type random fields of increasing parametric dimension, Numerical integration in log-Korobov and log-cosine spaces, Asymptotic behavior of average \(L_p\)-discrepancies, Multivariate approximation for analytic functions with Gaussian kernels, On the dispersion of sparse grids, An upper bound on the minimal dispersion, Tractability properties of the weighted star discrepancy of the Halton sequence, Average case tractability of non-homogeneous tensor product problems, Tractability of infinite-dimensional integration in the worst case and randomized settings, Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm, Uniform weak tractability of multivariate problems with increasing smoothness, Tractability of linear problems defined over Hilbert spaces, A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights, Average case tractability of multivariate approximation with Gaussian kernels, On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms, Tractability results for weighted Banach spaces of smooth functions, On the complexity of computing quadrature formulas for marginal distributions of SDEs, A note on the dispersion of admissible lattices, Multivariate \(L_{\infty}\) approximation in the worst case setting over reproducing kernel Hilbert spaces, Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules, Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence, Simple characterizations of exponential tractability for linear multivariate problems, Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension, A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids, Function values are enough for \(L_2\)-approximation. II, Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity, Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation, \(\varepsilon\)-dimension in infinite dimensional hyperbolic cross approximation and application to parametric elliptic PDEs, Tractability properties of the weighted star discrepancy of regular grids, Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions, Preasymptotics and asymptotics of approximation numbers of anisotropic Sobolev embeddings, Sampling and cubature on sparse grids based on a B-spline quasi-interpolation, Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients, On convergence rate of a rectangular partition based global optimization algorithm, Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions, Algorithms and complexity for functions on general domains, Tractability properties of the discrepancy in Orlicz norms, On the fixed volume discrepancy of the Fibonacci sets in the integral norms, Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals, The recovery of ridge functions on the hypercube suffers from the curse of dimensionality, A note on Korobov lattice rules for integration of analytic functions, Integration and approximation in cosine spaces of smooth functions, A lower bound for the dispersion on the torus, Quasi-Monte Carlo methods for lattice systems: a first look, Solvable integration problems and optimal sample size selection, Tractability of multivariate approximation over weighted standard Sobolev spaces, The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces, EC-tractability of \(\mathbb{L}_p\)-approximation in Korobov spaces with exponential weights, Quasi-polynomial tractability, Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\), The randomized complexity of indefinite integration, Weighted integration over a hyperrectangle based on digital nets and sequences, Introduction to convex optimization in financial markets, Points on manifolds with asymptotically optimal covering radius, Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods, Toeplitz Monte Carlo, Secure pseudorandom bit generators and point sets with low star-discrepancy, Pointwise multipliers for Besov spaces of dominating mixed smoothness. II, Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems, Tractability for Volterra problems of the second kind with convolution kernels, Lower bounds for the error of quadrature formulas for Hilbert spaces, On optimal recovery in \(L_2\), Entropy and sampling numbers of classes of ridge functions, Curve based approximation of measures on manifolds by discrepancy minimization, Complexity and tractability for a class of elliptic partial integro-differential equations, Uniformly distributed sequences generated by a greedy minimization of the \(L_2\) discrepancy, Random sections of ellipsoids and the power of random information, EC-tractability of multivariate approximation in Hermite spaces for the standard information class, MDFEM: Multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM, Full error analysis for the training of deep neural networks, Entropy, Randomization, Derandomization, and Discrepancy, High-Discrepancy Sequences for High-Dimensional Numerical Integration, A Monte Carlo Method for Integration of Multivariate Smooth Functions, Worst case tractability of linear problems in the presence of noise: linear information, Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration, Deep ReLU neural networks in high-dimensional approximation, The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\), Spectral decomposition of discrepancy kernels on the Euclidean ball, the special orthogonal group, and the Grassmannian manifold, Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series, Overall error analysis for the training of deep neural networks via stochastic gradient descent with random initialisation, The fast reduced QMC matrix-vector product, Optimal approximation of infinite-dimensional holomorphic functions, On the information complexity for integration in subspaces of the Wiener algebra, Complexity for a class of elliptic ordinary integro-differential equations, Lower bounds for artificial neural network approximations: a proof that shallow neural networks fail to overcome the curse of dimensionality, Fast hyperbolic wavelet regression meets ANOVA, Tractability of \(L_2\)-approximation and integration in weighted Hermite spaces of finite smoothness, New lower bounds for the integration of periodic functions, On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting, Asymptotic analysis in multivariate worst case approximation with Gaussian kernels, Expected integration approximation under general equal measure partition, Discrepancy of Digital Sequences: New Results on a Classical QMC Topic, Exponential Tractability of Linear Tensor Product Problems, An Upper Bound of the Minimal Dispersion via Delta Covers, Tractability of Approximation for Some Weighted Spaces of Hybrid Smoothness, Reproducing kernels of Sobolev spaces on ℝd and applications to embedding constants and tractability, Effective Dimension of Some Weighted Pre-Sobolev Spaces with Dominating Mixed Partial Derivatives, Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights, Isotropic and dominating mixed Besov spaces: A comparison, Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces, Average case tractability of approximating ∞-variate functions, Probabilistic discrepancy bound for Monte Carlo point sets, Extreme and periodic $L_2$ discrepancy of plane point sets, Overcoming the curse of dimensionality in the numerical approximation of semilinear parabolic partial differential equations, On the fixed volume discrepancy of the Korobov point sets, Tractability of the approximation of high-dimensional rank one tensors, Open type quasi-Monte Carlo integration based on Halton sequences in weighted Sobolev spaces, On the discrepancy of jittered sampling, Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls, A constraint on extensible quadrature rules, Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions. Error bounds and tractability, Bayesian Probabilistic Numerical Methods in Time-Dependent State Estimation for Industrial Hydrocyclone Equipment, Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality, Rapid mixing of Swendsen–Wang dynamics in two dimensions, Bayesian Probabilistic Numerical Methods, Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters, On quasi-Monte Carlo methods in weighted ANOVA spaces, Computation of Expectations by Markov Chain Monte Carlo Methods, Discrepancy Theory and Quasi-Monte Carlo Integration, Calculation of Discrepancy Measures and Applications, Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration, \(\mathbb{L}_\infty\)-approximation in Korobov spaces with exponential weights, The weighted star discrepancy of Korobov’s $p$-sets, Lower bounds for integration and recovery in \(L_2\), Deterministic constructions of high-dimensional sets with small dispersion, Strong equivalences of approximation numbers and tractability of weighted anisotropic Sobolev embeddings, Deep neural network approximations for solutions of PDEs based on Monte Carlo algorithms, \((s, t)\)-weak tractability of multivariate linear problems in the average case setting, The curse of dimensionality for numerical integration of smooth functions, Probabilistic Star Discrepancy Bounds for Double Infinite Random Matrices, Complexity of Banach Space Valued and Parametric Integration, Hit-and-Run for Numerical Integration, (\(s, \ln^\kappa\))-weak tractability of linear problems, On the randomized complexity of Banach space valued integration, On the size of the largest empty box amidst a point set, Order estimates of the norms of derivatives of functions with zero values on linear functionals and their applications, Pointwise multipliers for Sobolev and Besov spaces of dominating mixed smoothness, Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube, Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration, Approximation in periodic Gevrey spaces, EC-\((t_1,t_2)\)-tractability of approximation in weighted Korobov spaces in the worst case setting, Average case tractability of a multivariate approximation problem, A universal algorithm for multivariate integration, A note on the periodic \(L_2\)-discrepancy of Korobov's \(p\)-sets, A sharp upper bound for sampling numbers in \(L_2\), On the quasi-Monte Carlo method with Halton points for elliptic PDEs with log-normal diffusion, Multivariate integration for analytic functions with Gaussian kernels, Best \(n\)-term approximation of diagonal operators and application to function spaces with mixed smoothness, On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting, ABC on IBC, Some Results on the Complexity of Numerical Integration, Reliable Adaptive Cubature Using Digital Sequences, Optimal Point Sets for Quasi-Monte Carlo Integration of Bivariate Periodic Functions with Bounded Mixed Derivatives, Adaptive Multidimensional Integration Based on Rank-1 Lattices, Tractability of Multivariate Integration in Hybrid Function Spaces, Uniform Weak Tractability of Weighted Integration, On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability, Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games, On lower bounds for the \(L_2\)-discrepancy, Overcoming the curse of dimensionality in the approximative pricing of financial derivatives with default risks, Exponential tractability of \(L_2\)-approximation with function values, The BMO-discrepancy suffers from the curse of dimensionality, Average case tractability of non-homogeneous tensor product problems with the absolute error criterion, Fully Symmetric Kernel Quadrature, Lattice rules for nonperiodic smooth integrands, Quasi Monte Carlo Integration and Kernel-Based Function Approximation on Grassmannians, Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory, Multivariate Approximation in Downward Closed Polynomial Spaces, Ian Sloan and Lattice Rules, Tractability of Multivariate Problems for Standard and Linear Information in the Worst Case Setting: Part II, Integral Equations, Quasi-Monte Carlo Methods and Risk Modeling, \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations, Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension, Approximation of analytic functions in Korobov spaces, Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions, Approximation numbers of Sobolev embeddings-sharp constants and tractability, The curse of dimensionality for numerical integration of smooth functions. II, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, On weak tractability of the Clenshaw-Curtis Smolyak algorithm, Function values are enough for \(L_2\)-approximation, Tractability of approximation in the weighted Korobov space in the worst-case setting -- a complete picture, A note on EC-tractability of multivariate approximation in weighted Korobov spaces for the standard information class, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, Worst-case recovery guarantees for least squares approximation using random samples, Tractability results for the weighted star-discrepancy, Uniform weak tractability, Quasi-polynomial tractability of linear problems in the average case setting, Weighted discrepancy and numerical integration in function spaces, Global solutions of Navier-Stokes equations for large initial data belonging to spaces with dominating mixed smoothness, On weak tractability of the Smolyak algorithm for approximation problems, Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness, The curse of dimensionality for the class of monotone functions and for the class of convex functions, A new criterion for tractability of multivariate problems, Quadrature points via heat kernel repulsion, Dimension-dependent error estimates for sampling recovery on Smolyak grids based on B-spline quasi-interpolation, Sampling numbers of a class of infinitely differentiable functions, Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration, Convergence analysis of deterministic kernel-based quadrature rules in misspecified settings, On efficiency of a single variable bi-objective optimization algorithm, Optimal Monte Carlo integration on closed manifolds, Information based complexity for high dimensional sparse functions, On the Scenario-Tree Optimal-Value Error for Stochastic Programming Problems, Optimal confidence for Monte Carlo integration of smooth functions, A solution to the energy minimization problem constrained by a density function, A simple proof of Stolarsky’s invariance principle, A weighted discrepancy bound of quasi-Monte Carlo importance sampling, Infinite-dimensional integration on weighted Hilbert spaces, Probabilistic integration: a role in statistical computation?, EC-tractability of approximation problems in function spaces defined over products of simplices, A note about EC-\((s, t)\)-weak tractability of multivariate approximation with analytic Korobov kernels, EC-\((s, t)\)-weak tractability of multivariate linear problems in the average case setting, Automatic evaluations of cross-derivatives, On some aspects of approximation of ridge functions, Proof techniques in quasi-Monte Carlo theory, Integration in Hermite spaces of analytic functions, On embeddings of weighted tensor product Hilbert spaces, Approximation of multivariate periodic functions by trigonometric polynomials based on sampling along rank-1 lattice with generating vector of Korobov form, Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets, Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling, Exponential convergence-tractability of general linear problems in the average case setting, Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces