Tractability of multivariate problems. Volume I: Linear information

DOI10.4171/026zbMath1156.65001MaRDI QIDQ940799

Erich Novak, Henryk Woźniakowski

Publication date: 3 September 2008

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

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

zbMATH Keywords

textbook; discrepancy; weighted norms; Monte Carlo algorithms; curse of dimensionality; randomized algorithms; multivariate integration; tractability; linear information; worst case setting; finite-order weights; information based complexity; high-dimensional numerical problems; product weights

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65C05: Monte Carlo methods

46E30: Spaces of measurable functions ((L^p)-spaces, Orlicz spaces, Köthe function spaces, Lorentz spaces, rearrangement invariant spaces, ideal spaces, etc.)

65-02: Research exposition (monographs, survey articles) pertaining to numerical analysis

41A63: Multidimensional problems

46E22: Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces)

65D32: Numerical quadrature and cubature formulas

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

28C20: Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.)

65Y20: Complexity and performance of numerical algorithms

Related Items

Optimal recovery of twice differentiable functions based on symmetric splines, On the complexity of computing the \(L_q\) norm, Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems, Recovery algorithms for high-dimensional rank one tensors, Tractability of the Fredholm problem of the second kind, Random weights, robust lattice rules and the geometry of the \(cbcrc\) algorithm, Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness, A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids, Function values are enough for \(L_2\)-approximation. II, Sample numbers and optimal Lagrange interpolation in Sobolev spaces, Algorithms and complexity for functions on general domains, Tractability properties of the discrepancy in Orlicz norms, Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals, Instances of computational optimal recovery: refined approximability models, The recovery of ridge functions on the hypercube suffers from the curse of dimensionality, How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings, A note on Korobov lattice rules for integration of analytic functions, Integration and approximation in cosine spaces of smooth functions, Truncation in average and worst case settings for special classes of \(\infty \)-variate functions, Solvable integration problems and optimal sample size selection, Tractability of multivariate approximation over weighted standard Sobolev spaces, EC-tractability of \(\mathbb{L}_p\)-approximation in Korobov spaces with exponential weights, Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition, Weighted integration over a hyperrectangle based on digital nets and sequences, Secure pseudorandom bit generators and point sets with low star-discrepancy, Tractability for Volterra problems of the second kind with convolution kernels, Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time, Lower bounds for the error of quadrature formulas for Hilbert spaces, On optimal recovery in \(L_2\), Sample numbers and optimal Lagrange interpolation of Sobolev spaces \(W_1^r\), Gelfand numbers of embeddings of Schatten classes, Optimal pointwise sampling for \(L^2\) approximation, Complexity and tractability for a class of elliptic partial integro-differential equations, Optimal Birkhoff interpolation and Birkhoff numbers in some function spaces, A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids, Sampling based approximation of linear functionals in reproducing kernel Hilbert spaces, Spectral flatness and the volume of intersections of \(p\)-ellipsoids, On the power of standard information for tractability for \(L_2\)-approximation in the average case setting, Asymptotic analysis in multivariate average case approximation with Gaussian kernels, Sampling discretization and related problems, Optimal recovery of functions from numerical information on them and limiting error of the optimal computing unit, 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, Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces, Approximation in periodic Gevrey spaces, EC-\((t_1,t_2)\)-tractability of approximation in weighted Korobov spaces in the worst case setting, A variant of Schur's product theorem and its applications, On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting, On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability, 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, On the relation of the spectral test to isotropic discrepancy and \(L_q\)-approximation in Sobolev spaces, 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, Complexity of parametric initial value problems in Banach spaces, Multivariate approximation by translates of the Korobov function on Smolyak grids, Uniform weak tractability, Quasi-polynomial tractability of linear problems in the average case setting, Weighted discrepancy and numerical integration in function spaces, On lower bounds for integration of multivariate permutation-invariant functions, 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, An introduction to the Hilbert-Schmidt SVD using iterated Brownian bridge kernels, Approximation of infinitely differentiable multivariate functions is intractable, Approximation complexity of sums of random processes, 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, Absolute value information for IBC problems, Quadrature points via heat kernel repulsion, Dimension-dependent error estimates for sampling recovery on Smolyak grids based on B-spline quasi-interpolation, Computational (numerical) diameter in a context of general theory of a recovery, Sampling numbers of a class of infinitely differentiable functions, On the history of St. Petersburg school of probability and mathematical statistics. II: Random processes and dependent variables, Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration, Theory of generalized discrepancies on a ball of arbitrary finite dimensions and algorithms for finding low-discrepancy point sets, Information based complexity for high dimensional sparse functions, Optimal confidence for Monte Carlo integration of smooth functions, Sharp exponential bounds for the Gaussian regularized Whittaker-Kotelnikov-Shannon sampling series, Probabilistic integration: a role in statistical computation?, Super-resolution meets machine learning: approximation of measures, 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, On some aspects of approximation of ridge functions, Distributing many points on spheres: minimal energy and designs, Proof techniques in quasi-Monte Carlo theory, Integration in Hermite spaces of analytic functions, On embeddings of weighted tensor product Hilbert spaces, 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, Gelfand numbers of embeddings of mixed Besov spaces, \(\mathbb{L}_\infty\)-approximation in Korobov spaces with exponential weights, Complexity of oscillatory integrals on the real line, Constructing lattice rules based on weighted degree of exactness and worst case error, (\(s, \ln^\kappa\))-weak tractability of linear problems, Equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in \(L_p\), Order estimates of the norms of derivatives of functions with zero values on linear functionals and their applications, 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, Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, Approximation of eigenfunctions in kernel-based spaces, Tensor-sparsity of solutions to high-dimensional elliptic partial differential equations, A note on equivalence of anchored and ANOVA spaces; lower bounds, Product rules are optimal for numerical integration in classical smoothness spaces, A new characterization of \((s,t)\)-weak tractability, Average approximation of tensor product-type random fields of increasing dimension, Mercer's theorem on general domains: on the interaction between measures, kernels, and RKHSs, Ultrastability of \(n\)th minimal errors, Learning functions of few arbitrary linear parameters in high dimensions, An exact order of discrepancy of the Smolyak grid and some general conclusions in the theory of numerical integration, Joint spectra of Toeplitz operators and optimal recovery of analytic functions, Average case tractability of non-homogeneous tensor product problems, Uniform weak tractability of multivariate problems with increasing smoothness, Tractability of linear problems defined over Hilbert spaces, A survey of average case complexity for linear multivariate problems, Complexity of oscillatory integration for univariate Sobolev spaces, On the complexity of computing quadrature formulas for marginal distributions of SDEs, Approximation of high-dimensional rank one tensors, Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence, Approximation of additive random fields based on standard information: average case and probabilistic settings, 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, 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, Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions, On positive positive-definite functions and Bochner's theorem, Tractability of tensor product problems in the average case setting, Quasi-polynomial tractability, Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\), The randomized complexity of indefinite integration, Liberating the dimension for function approximation: standard information, The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), Lower bounds for the complexity of linear functionals in the randomized setting, Liberating the dimension for function approximation, Approximation of functions of few variables in high dimensions, Tractability of approximating multivariate linear functionals, Tractability of infinite-dimensional integration in the worst case and randomized settings, Optimal cubature formulas for tensor products of certain classes of functions, Tractability results for weighted Banach spaces of smooth functions, Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules, Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension, Tractability through increasing smoothness, Liberating the dimension, Introduction to convex optimization in financial markets, Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods, Optimal recovery of three times differentiable functions on a convex polytope inscribed in a sphere, Pointwise multipliers for Besov spaces of dominating mixed smoothness. II, On the tractability of linear tensor product problems in the worst case, Randomized approximation of Sobolev embeddings. II, Randomized approximation of Sobolev embeddings. III, Entropy and sampling numbers of classes of ridge functions, Tractability of multivariate approximation over a weighted unanchored Sobolev space, Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions, Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, 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, Quadrature for self-affine distributions on \(\mathbb R^d\), Optimal recovery of Besov classes of generalized smoothness and Sobolev classes on the sphere, New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness, 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, Informative cardinality of trigonometric Fourier coefficients and their limiting error in the discretization of a differentiation operator in multidimensional Sobolev classes, Approximation in probability of tensor product-type random fields of increasing parametric dimension, Numerical integration in log-Korobov and log-cosine spaces, Optimal importance sampling for the approximation of integrals, Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\), On the power of standard information for \(L_{\infty}\) approximation in the randomized setting, On the approximation of smooth functions using generalized digital nets, Tractability of the Helmholtz equation with non-homogeneous Neumann boundary conditions: the relation to the \(L_{2}\)-approximation, Efficient finite-dimensional solution of initial value problems in infinite-dimensional Banach spaces, 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, Uniform recovery of high-dimensional \(C^r\)-functions, Tractability of \(\mathbb{L}_2\)-approximation in hybrid function spaces, Optimal \(L_{p}\)-discrepancy bounds for second order digital sequences, Tensor power sequences and the approximation of tensor product operators, \textsc{OpenCL} based parallel algorithm for RBF-PUM interpolation, Multivariate approximation for analytic functions with Gaussian kernels, \((s, t)\)-weak tractability of Euler and Wiener integrated processes, Tractability properties of the weighted star discrepancy of the Halton sequence, Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm, Average case tractability of multivariate approximation with Gaussian kernels, Lattice rules in non-periodic subspaces of Sobolev spaces, Optimal Monte Carlo methods for \(L^2\)-approximation, The difficulty of Monte Carlo approximation of multivariate monotone functions, Simple characterizations of exponential tractability for linear multivariate problems, \(\varepsilon\)-dimension in infinite dimensional hyperbolic cross approximation and application to parametric elliptic PDEs, Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness, Tractability properties of the weighted star discrepancy of regular grids, Optimal order quadrature error bounds for infinite-dimensional higher-order digital sequences, The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces, Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory, Ian Sloan and Lattice Rules, Tractability of Multivariate Problems for Standard and Linear Information in the Worst Case Setting: Part II, The Analysis of Vertex Modified Lattice Rules in a Non-periodic Sobolev Space, An Upper Bound of the Minimal Dispersion via Delta Covers, Tractability of Approximation for Some Weighted Spaces of Hybrid Smoothness, Isotropic and dominating mixed Besov spaces: A comparison, On the Optimal Order of Integration in Hermite Spaces with Finite Smoothness, Unnamed Item, Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters, Scaled lattice rules for integration on ℝ^{𝕕} achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces, Random sections of ellipsoids and the power of random information, EC-tractability of multivariate approximation in Hermite spaces for the standard information class, Full error analysis for the training of deep neural networks, A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm, Construction-Free Median Quasi-Monte Carlo Rules for Function Spaces with Unspecified Smoothness and General Weights, Discrepancy of Digital Sequences: New Results on a Classical QMC Topic, Exponential Tractability of Linear Tensor Product Problems, Maximum Likelihood Estimation and Uncertainty Quantification for Gaussian Process Approximation of Deterministic Functions, A Method for Dimensionally Adaptive Sparse Trigonometric Interpolation of Periodic Functions, Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights, On the Wasserstein distance between classical sequences and the Lebesgue measure, Overcoming the curse of dimensionality in the numerical approximation of semilinear parabolic partial differential equations, C*-algebraic Schur product theorem, P\'{o}lya-Szeg\H{o}-Rudin question and Novak's conjecture, Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls, Bayesian Probabilistic Numerical Methods in Time-Dependent State Estimation for Industrial Hydrocyclone Equipment, Strang Splitting in Combination with Rank-1 and Rank-r Lattices for the Time-Dependent Schrödinger Equation, 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, Entropy, Randomization, Derandomization, and Discrepancy, Liberating the Dimension for Function Approximation and Integration, Cubature, Approximation, and Isotropy in the Hypercube, Reproducing kernels of Sobolev spaces on ℝd and applications to embedding constants and tractability, 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, Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality, The best constants in the Wirtinger inequality, Multilevel Accelerated Quadrature for PDEs with Log-Normally Distributed Diffusion Coefficient, Tractability of the approximation of high-dimensional rank one tensors, Hyperbolic cross approximation in infinite dimensions, Open type quasi-Monte Carlo integration based on Halton sequences in weighted Sobolev spaces, On the discrepancy of jittered sampling, Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions. Error bounds and tractability, On quasi-Monte Carlo methods in weighted ANOVA spaces, Nonlinear approximation spaces for inverse problems, Density Estimation in RKHS with Application to Korobov Spaces in High Dimensions, Deep ReLU neural networks in high-dimensional approximation, Overall error analysis for the training of deep neural networks via stochastic gradient descent with random initialisation, Random sections of \(\ell_p\)-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators, 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, Pointwise multipliers for Sobolev and Besov spaces of dominating mixed smoothness, Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration, Average case tractability of a multivariate approximation problem, Functional reproducing kernel Hilbert spaces for non-point-evaluation functional data, ABC on IBC, Asymptotic analysis of average case approximation complexity of additive random fields, On lower bounds for the \(L_2\)-discrepancy, Complexity of approximation of functions of few variables in high dimensions, Lattice rules for nonperiodic smooth integrands, \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations, 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, A new criterion for tractability of multivariate problems, An estimate of average case approximation complexity for tensor degrees of random processes, A sharp upper bound for sampling numbers in \(L_2\), Best \(n\)-term approximation of diagonal operators and application to function spaces with mixed smoothness, Local approximation of operators, Exponential tractability of \(L_2\)-approximation with function values, A note on the CBC-DBD construction of lattice rules with general positive weights, The BMO-discrepancy suffers from the curse of dimensionality, Average case tractability of non-homogeneous tensor product problems with the absolute error criterion, Overcoming the curse of dimensionality in the numerical approximation of backward stochastic differential equations, Optimal recovery from inaccurate data in Hilbert spaces: regularize, but what of the parameter?, An Explicit Construction of Optimal Order Quasi--Monte Carlo Rules for Smooth Integrands, Infinite-dimensional integration on weighted Hilbert spaces, Automatic evaluations of cross-derivatives, Green’s Functions: Taking Another Look at Kernel Approximation, Radial Basis Functions, and Splines, Probabilistic Star Discrepancy Bounds for Double Infinite Random Matrices, Hit-and-Run for Numerical Integration, On the quasi-Monte Carlo method with Halton points for elliptic PDEs with log-normal diffusion, Multivariate integration for analytic functions with Gaussian kernels, Counting Via Entropy: New Preasymptotics for the Approximation Numbers of Sobolev Embeddings, Some Results on the Complexity of Numerical Integration, Tractability of Multivariate Integration in Hybrid Function Spaces, Bernstein Numbers and Lower Bounds for the Monte Carlo Error, Tractability of Function Approximation with Product Kernels, Exponential convergence and tractability of multivariate integration for Korobov spaces, The curse of dimensionality for numerical integration of smooth functions, Optimal Reduced Model Algorithms for Data-Based State Estimation, The weighted star discrepancy of Korobov’s $p$-sets, On the exponent of discrepancies, Tractability of \(L_2\)-approximation and integration in weighted Hermite spaces of finite smoothness, On a reduced component-by-component digit-by-digit construction of lattice point sets, New lower bounds for the integration of periodic functions