Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity

DOI10.1016/j.jat.2015.07.007zbMath1329.68148arXiv1411.3466OpenAlexW2591645921MaRDI QIDQ498476

Paweł Siedlecki, Markus Weimar

Publication date: 28 September 2015

Published in: Journal of Approximation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.3466

zbMATH Keywords

approximationHilbert spacesintegrationinformation-based complexitytractabilitymultivariate numerical problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Multidimensional problems (41A63) Complexity and performance of numerical algorithms (65Y20)

Related Items (35)

On the power of standard information for tractability for \(L_2\)-approximation in the average case setting ⋮ Tractability of multivariate approximation defined over Hilbert spaces with exponential weights ⋮ Approximation numbers of Sobolev and Gevrey type embeddings on the sphere and on the ball -- preasymptotics, asymptotics, and tractability ⋮ EC-tractability of multivariate approximation in Hermite spaces for the standard information class ⋮ \((s, t)\)-weak tractability of multivariate linear problems in the average case setting ⋮ A new characterization of \((s,t)\)-weak tractability ⋮ (\(s, \ln^\kappa\))-weak tractability of linear problems ⋮ Approximation in periodic Gevrey spaces ⋮ Average case tractability of a multivariate approximation problem ⋮ Rate-optimal sparse approximation of compact break-of-scale embeddings ⋮ Multivariate integration for analytic functions with Gaussian kernels ⋮ Counting Via Entropy: New Preasymptotics for the Approximation Numbers of Sobolev Embeddings ⋮ On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting ⋮ Uniform Weak Tractability of Weighted Integration ⋮ On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting ⋮ Average case tractability of non-homogeneous tensor product problems with the absolute error criterion ⋮ Exponential Tractability of Linear Tensor Product Problems ⋮ New Preasymptotic Estimates for Approximation of Periodic Sobolev Functions ⋮ Multivariate approximation for analytic functions with Gaussian kernels ⋮ \((s, t)\)-weak tractability of Euler and Wiener integrated processes ⋮ Tractability of Approximation for Some Weighted Spaces of Hybrid Smoothness ⋮ Average case tractability of multivariate approximation with Gaussian kernels ⋮ A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids ⋮ 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 ⋮ Preasymptotics and asymptotics of approximation numbers of anisotropic Sobolev embeddings ⋮ 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 ⋮ Tractability of multivariate approximation over weighted standard Sobolev spaces ⋮ Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems ⋮ Tractability for Volterra problems of the second kind with convolution kernels ⋮ Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls ⋮ 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

Cites Work

• Unnamed Item
• Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \(H^\gamma\)
• Tractability of linear problems defined over Hilbert spaces
• Quasi-polynomial tractability
• Tractability of multivariate problems. Volume III: Standard information for operators
• On the tractability of linear tensor product problems in the worst case
• Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
• Tractability of multivariate problems. Volume I: Linear information
• Regularity and approximability of electronic wave functions
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Optimized tensor-product approximation spaces
• Uniform weak tractability
• On lower bounds for integration of multivariate permutation-invariant functions
• Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling
• Approximation numbers of Sobolev embeddings-sharp constants and tractability
• The curse of dimensionality for numerical integration of smooth functions. II
• On weak tractability of the Clenshaw-Curtis Smolyak algorithm
• A new criterion for tractability of multivariate problems
• Tractability of multivariate analytic problems
• Breaking the curse of dimensionality

This page was built for publication: Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity