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

DOI10.1016/J.JAT.2015.07.007zbMATH Open1329.68148arXiv1411.3466OpenAlexW2591645921MaRDI QIDQ498476FDOQ498476

Authors: Paweł Siedlecki, Markus Weimar 

Publication date: 28 September 2015

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

Abstract: In the last 20 years a whole hierarchy of notions of tractability was proposed and analyzed by several authors. These notions are used to classify the computational hardness of continuous numerical problems $S=(S_d{)}_{dinmathbbN}$ in terms of the behavior of their information complexity $n(epsilon,S_d)$ as a function of the accuracy $epsilon$ and the dimension $d$. By now a lot of effort was spend on either proving quantitative positive results (such as, e.g., the concrete dependence on $epsilon$ and $d$ within the well-established framework of polynomial tractability), or on qualitative negative results (which, e.g., state that a given problem suffers from the so-called curse of dimensionality). Although several weaker types of tractability were introduced recently, the theory of information-based complexity still lacks a notion which allows to quantify the exact (sub-/super-)exponential dependence of $n(epsilon,S_d)$ on both parameters $epsilon$ and $d$. In this paper we present the notion of $(s,t)$-weak tractability which attempts to fill this gap. Within this new framework the parameters $s$ and $t$ are used to quantitatively refine the huge class of polynomially intractable problems. For linear, compact operators between Hilbert spaces we provide characterizations of $(s,t)$-weak tractability w.r.t. the worst case setting in terms of singular values. In addition, our new notion is illustrated by classical examples which recently attracted some attention. In detail, we study approximation problems between periodic Sobolev spaces and integration problems for classes of smooth functions. Keywords: Information-based complexity, Multivariate numerical problems, Hilbert spaces, Tractablity, Approximation, Integration.

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

Recommendations

• (\(s, \ln^\kappa\))-weak tractability of linear problems
• A new characterization of \((s,t)\)-weak tractability
• Uniform weak tractability
• \((s, t)\)-weak tractability of multivariate linear problems in the average case setting
• \((s, t)\)-weak tractability of Euler and Wiener integrated processes

zbMATH Keywords

approximationintegrationHilbert spacestractabilityinformation-based complexitymultivariate numerical problems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (38)

• Counting via entropy: new preasymptotics for the approximation numbers of Sobolev embeddings
• A unified treatment of tractability for approximation problems defined on Hilbert spaces
• Selected aspects of tractability analysis
• The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
• Tractability of multivariate approximation defined over Hilbert spaces with exponential weights
• A note about EC-\((s, t)\)-weak tractability of multivariate approximation with analytic Korobov kernels
• EC-tractability of approximation problems in function spaces defined over products of simplices
• Uniform weak tractability of weighted integration
• Exponential Tractability of Linear Tensor Product Problems
• New Preasymptotic Estimates for Approximation of Periodic Sobolev Functions
• Rate-optimal sparse approximation of compact break-of-scale embeddings
• A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids
• Approximation in periodic Gevrey spaces
• Approximation numbers of Sobolev and Gevrey type embeddings on the sphere and on the ball -- preasymptotics, asymptotics, and tractability
• Multivariate integration for analytic functions with Gaussian kernels
• Tractability for Volterra problems of the second kind with convolution kernels
• Multivariate approximation for analytic functions with Gaussian kernels
• On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting
• (\(s, \ln^\kappa\))-weak tractability of linear problems
• Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems
• Tractability of approximation for some weighted spaces of hybrid smoothness
• Uniform weak tractability
• Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals
• Tractability of multivariate approximation over weighted standard Sobolev spaces
• A note on EC-tractability of multivariate approximation in weighted Korobov spaces for the standard information class
• Tractability of approximation in the weighted Korobov space in the worst-case setting -- a complete picture
• A new characterization of \((s,t)\)-weak tractability
• EC-tractability of multivariate approximation in Hermite spaces for the standard information class
• EC-\((s, t)\)-weak tractability of multivariate linear problems in the average case setting
• \((s, t)\)-weak tractability of multivariate linear problems in the average case setting
• Average case tractability of non-homogeneous tensor product problems with the absolute error criterion
• Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls
• On the power of standard information for tractability for \(L_2\)-approximation in the average case setting
• Preasymptotics and asymptotics of approximation numbers of anisotropic Sobolev embeddings
• \((s, t)\)-weak tractability of Euler and Wiener integrated processes
• On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting
• Average case tractability of a multivariate approximation problem
• Average case tractability of multivariate approximation with Gaussian kernels

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q498476)