Tractability of multivariate problems. Volume I: Linear information

DOI10.4171/026zbMath1156.65001OpenAlexW1820164671MaRDI 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

textbookdiscrepancyweighted normsMonte Carlo algorithmscurse of dimensionalityrandomized algorithmsmultivariate integrationtractabilitylinear informationworst case settingfinite-order weightsinformation based complexityhigh-dimensional numerical problemsproduct weights

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Monte Carlo methods (65C05) Spaces of measurable functions ((L^p)-spaces, Orlicz spaces, Köthe function spaces, Lorentz spaces, rearrangement invariant spaces, ideal spaces, etc.) (46E30) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Multidimensional problems (41A63) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22) Numerical quadrature and cubature formulas (65D32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Complexity and performance of numerical algorithms (65Y20)

Related Items

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, 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, Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, Tractability of multivariate approximation over a weighted unanchored Sobolev space, Optimal order of convergence and (in)tractability of multivariate approximation of smooth 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, Tractability of \(\mathbb{L}_2\)-approximation in hybrid function spaces, Optimal \(L_{p}\)-discrepancy bounds for second order digital sequences, The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), Tensor power sequences and the approximation of tensor product operators, 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, Lower bounds for the complexity of linear functionals in the randomized setting, Liberating the dimension for function approximation, 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, Approximation of functions of few variables in high dimensions, 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, 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, Mercer's theorem on general domains: on the interaction between measures, kernels, and RKHSs, Numerical integration in log-Korobov and log-cosine spaces, \textsc{OpenCL} based parallel algorithm for RBF-PUM interpolation, 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, Multivariate approximation for analytic functions with Gaussian kernels, \((s, t)\)-weak tractability of Euler and Wiener integrated processes, Joint spectra of Toeplitz operators and optimal recovery of analytic functions, 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, Optimal cubature formulas for tensor products of certain classes of functions, 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, Average case tractability of multivariate approximation with Gaussian kernels, Lattice rules in non-periodic subspaces of Sobolev spaces, A survey of average case complexity for linear multivariate problems, Tractability results for weighted Banach spaces of smooth functions, Complexity of oscillatory integration for univariate Sobolev spaces, On the complexity of computing quadrature formulas for marginal distributions of SDEs, Optimal Monte Carlo methods for \(L^2\)-approximation, Approximation of high-dimensional rank one tensors, 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, The difficulty of Monte Carlo approximation of multivariate monotone functions, 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, 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, \(\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, 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, Optimal order quadrature error bounds for infinite-dimensional higher-order digital sequences, Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions, The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces, Optimal importance sampling for the approximation of integrals, 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, Tractability through increasing smoothness, Liberating the dimension, Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\), 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, 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, Density Estimation in RKHS with Application to Korobov Spaces in High Dimensions, Scaled lattice rules for integration on ℝ^{𝕕} achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces, Exponential convergence and tractability of multivariate integration for Korobov spaces, Random sections of ellipsoids and the power of random information, The weighted star discrepancy of Korobov’s $p$-sets, EC-tractability of multivariate approximation in Hermite spaces for the standard information class, Green’s Functions: Taking Another Look at Kernel Approximation, Radial Basis Functions, and Splines, The curse of dimensionality for numerical integration of smooth functions, Probabilistic Star Discrepancy Bounds for Double Infinite Random Matrices, Hit-and-Run for Numerical Integration, Pointwise multipliers for Sobolev and Besov spaces of dominating mixed smoothness, Full error analysis for the training of deep neural networks, Entropy, Randomization, Derandomization, and Discrepancy, Liberating the Dimension for Function Approximation and Integration, Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration, A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm, Average case tractability of a multivariate approximation problem, An estimate of average case approximation complexity for tensor degrees of random processes, Functional reproducing kernel Hilbert spaces for non-point-evaluation functional data, Cubature, Approximation, and Isotropy in the Hypercube, Construction-Free Median Quasi-Monte Carlo Rules for Function Spaces with Unspecified Smoothness and General Weights, A sharp upper bound for sampling numbers in \(L_2\), 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, Sampling numbers of smoothness classes via \(\ell^1\)-minimization, 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, Counting Via Entropy: New Preasymptotics for the Approximation Numbers of Sobolev Embeddings, Deep ReLU neural networks in high-dimensional approximation, The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\), ABC on IBC, Asymptotic analysis of average case approximation complexity of additive random fields, 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, Unnamed Item, Local approximation of operators, On lower bounds for the \(L_2\)-discrepancy, Complexity of approximation of functions of few variables in high dimensions, 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, Discrepancy of Digital Sequences: New Results on a Classical QMC Topic, Overcoming the curse of dimensionality in the numerical approximation of backward stochastic differential equations, Exponential Tractability of Linear Tensor Product Problems, Maximum Likelihood Estimation and Uncertainty Quantification for Gaussian Process Approximation of Deterministic Functions, Lattice rules for nonperiodic smooth integrands, Optimal recovery from inaccurate data in Hilbert spaces: regularize, but what of the parameter?, 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, \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations, Reproducing kernels of Sobolev spaces on ℝd and applications to embedding constants and tractability, 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, A Method for Dimensionally Adaptive Sparse Trigonometric Interpolation of Periodic Functions, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, On weak tractability of the Clenshaw-Curtis Smolyak algorithm, Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights, Isotropic and dominating mixed Besov spaces: A comparison, On the Optimal Order of Integration in Hermite Spaces with Finite Smoothness, On the Wasserstein distance between classical sequences and the Lebesgue measure, 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, 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, Multilevel Accelerated Quadrature for PDEs with Log-Normally Distributed Diffusion Coefficient, On the exponent of discrepancies, A new criterion for tractability of multivariate problems, 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, Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls, 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, An Explicit Construction of Optimal Order Quasi--Monte Carlo Rules for Smooth Integrands, Optimal Reduced Model Algorithms for Data-Based State Estimation, Infinite-dimensional integration on weighted Hilbert spaces, Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality, Strang Splitting in Combination with Rank-1 and Rank-r Lattices for the Time-Dependent Schrödinger Equation, Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters, The best constants in the Wirtinger inequality, On quasi-Monte Carlo methods in weighted ANOVA spaces, Computation of Expectations by Markov Chain Monte Carlo Methods, Automatic evaluations of cross-derivatives, 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, Nonlinear approximation spaces for inverse problems, A note on the degree of ill-posedness for mixed differentiation on the \(d\)-dimensional unit cube, 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, Polynomial approximation of symmetric functions, Optimal approximation of infinite-dimensional holomorphic functions, Optimal learning, On the information complexity for integration in subspaces of the Wiener algebra, Complexity for a class of elliptic ordinary integro-differential equations, Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case, 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, On a reduced component-by-component digit-by-digit construction of lattice point sets, New lower bounds for the integration of periodic functions, Learning the random variables in Monte Carlo simulations with stochastic gradient descent: Machine learning for parametric PDEs and financial derivative pricing, On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting, A Universal Median Quasi-Monte Carlo Integration, Randomized complexity of parametric integration and the role of adaption. II: Sobolev spaces, Asymptotic analysis in multivariate worst case approximation with Gaussian kernels, 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, 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, Sampling discretization and related problems, Constructing lattice rules based on weighted degree of exactness and worst case error, 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, (\(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\), Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces, Order estimates of the norms of derivatives of functions with zero values on linear functionals and their applications, 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, Tractability of the Fredholm problem of the second kind, On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting, Random weights, robust lattice rules and the geometry of the \(cbcrc\) algorithm, On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability, Function values are enough for \(L_2\)-approximation, 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, 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, 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, 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, Solvable integration problems and optimal sample size selection, Tractability of multivariate approximation over weighted standard Sobolev spaces, Global solutions of Navier-Stokes equations for large initial data belonging to spaces with dominating mixed smoothness, Optimal recovery of twice differentiable functions based on symmetric splines, On weak tractability of the Smolyak algorithm for approximation problems, An introduction to the Hilbert-Schmidt SVD using iterated Brownian bridge kernels, 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, Approximation of infinitely differentiable multivariate functions is intractable, Weighted integration over a hyperrectangle based on digital nets and sequences, 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, Secure pseudorandom bit generators and point sets with low star-discrepancy, Absolute value information for IBC problems, On the complexity of computing the \(L_q\) norm, Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems, Tractability for Volterra problems of the second kind with convolution kernels, 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, Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time, On the history of St. Petersburg school of probability and mathematical statistics. II: Random processes and dependent variables, Lower bounds for the error of quadrature formulas for Hilbert spaces, On optimal recovery in \(L_2\), Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration, Recovery algorithms for high-dimensional rank one tensors, Theory of generalized discrepancies on a ball of arbitrary finite dimensions and algorithms for finding low-discrepancy point sets, 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, 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, Complexity and tractability for a class of elliptic partial integro-differential equations, Probabilistic integration: a role in statistical computation?, Optimal Birkhoff interpolation and Birkhoff numbers in some function spaces, 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, A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids, 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, Sampling based approximation of linear functionals in reproducing kernel Hilbert spaces