Tractability of multivariate problems. Volume I: Linear information
curse of dimensionalitydiscrepancyfinite-order weightshigh-dimensional numerical problemsinformation based complexitylinear informationMonte Carlo algorithmsmultivariate integrationproduct weightsrandomized algorithmstextbooktractabilityweighted normsworst case setting
Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Multidimensional problems (41A63) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22) 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) Monte Carlo methods (65C05) Numerical quadrature and cubature formulas (65D32) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
This book is a first of three volumes of the authors devoted to the study of the tractability of multivariate problems. The authors present various existing results obtained by many authors during last years, as well as numerous new results. This volume begins with twelve examples of particular multivariate problems, along with a survey of results in information based complexity that are especially relevant to tractability. This list comprises integration, approximation of \(C^{\infty}\) functions, discrepancy, absolute, relative and normalized errors and Monte Carlo algorithms, among others. The rest of the volume is devoted to the tractability of algorithms using linear information (arbitrary continuous linear functionals). The tractability results are illustrated for many specific multivariate problems, general linear problems including multivariate integration, approximation, as well as a number of specific non-linear problems such as partial differential and integral equations. The book contains a number of open problems that could be of interest to a general audience of mathematicians, and very long list of 296 references.
- Tractability of multivariate problems for standard and linear information in the worst case setting. II
- Tractability of multivariate problems for standard and linear information in the worst case setting. I.
- Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information
- Tractability of multivariate problems. Volume III: Standard information for operators
- Tractability of multivariate problems. Volume II: Standard information for functionals.
- Generalized tractability for multivariate problems. II: Linear tensor product problems, linear information, and unrestricted tractability
- Tractability and strong tractability of linear multivariate problems
- Tractability of multivariate problem
- Tractability of multivariate analytic problems
- A new criterion for tractability of multivariate problems
- 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
- 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₂
- 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₁,t₂)-tractability of approximation in weighted Korobov spaces in the worst case setting
- A variant of Schur's product theorem and its applications
- Multivariate algorithms and information-based complexity
- 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₂-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
This page was built for publication: Tractability of multivariate problems. Volume I: Linear information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q940799)
