Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals

DOI10.1016/J.JCO.2020.101501MaRDI QIDQ1996878zbMATH OpenOpenAlexWikidataFDO

Authors Peter Kritzer, Friedrich Pillichshammer, H. Woźniakowski

Publication date 26 February 2021

Published in Journal of Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

approximation of compact linear operatorsexponential tractabilityweighted linear tensor product problemworst-case setting

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Complexity and performance of numerical algorithms (65Y20)

Abstract: We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals which is needed to obtain an $varepsilon$-approximation for the $d$-variate problem. It is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function which depends polynomially on $d$ and logarithmically on $varepsilo{n}^{-1}$. The corresponding un-weighted problem was studied recently by Hickernell, Kritzer and Wo'{z}niakowski with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on $d$ and logarithmic dependence on $varepsilo{n}^{-1}$, we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential $(s,t)$-weak tractability with $max(s,t)ge1$. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential $(s,t)$-weak tractability with $max(s,t)<1$ is left for future study.

Recommendations

• Tractability of multivariate approximation defined over Hilbert spaces with exponential weights
• scientific article; zbMATH DE number 5286769
• scientific article; zbMATH DE number 1083138
• Generalized tractability for multivariate problems. II: Linear tensor product problems, linear information, and unrestricted tractability
• Tractability of tensor product linear operators in weighted Hilbert spaces

Cites work

• (\(s, \ln^\kappa\))-weak tractability of linear problems
• \(\mathbb{L}_\infty\)-approximation in Korobov spaces with exponential weights
• A new characterization of (s,t)-weak tractability
• A new criterion for tractability of multivariate problems
• A note about EC-\((s, t)\)-weak tractability of multivariate approximation with analytic Korobov kernels
• A note on tractability of multivariate analytic problems
• Approximation in Hermite spaces of smooth functions
• Approximation of analytic functions in Korobov spaces
• Average case tractability of a multivariate approximation problem
• Discontinuous information in the worst case and randomized settings
• EC-\((s, t)\)-weak tractability of multivariate linear problems in the average case setting
• EC-tractability of approximation problems in function spaces defined over products of simplices
• EC-tractability of general multivariate linear problems
• Exponential convergence and tractability of multivariate integration for Korobov spaces
• Exponential convergence-tractability of general linear problems in the average case setting
• Exponential Tractability of Linear Tensor Product Problems
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 1246413 (Why is no real title available?)
• Integration in Hermite spaces of analytic functions
• Multivariate approximation for analytic functions with Gaussian kernels
• Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces
• Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity
• On the tractability of linear tensor product problems in the worst case
• Quasi-polynomial tractability
• Simple characterizations of exponential tractability for linear multivariate problems
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• Tractability of multivariate approximation defined over Hilbert spaces with exponential weights
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators
• Uniform weak tractability
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(9)

• Weighted tensor product algorithms for linear multivariate problems
• A note on EC-tractability of multivariate approximation in weighted Korobov spaces for the standard information class
• Local approximation of operators
• Tractability of tensor product linear operators in weighted Hilbert spaces
• Tractability of multivariate approximation defined over Hilbert spaces with exponential weights
• scientific article; zbMATH DE number 1790456 (Why is no real title available?)
• EC-tractability of multivariate approximation in Hermite spaces for the standard information class
• EC-tractability of multivariate \(\mathbb{L}_\infty\)-approximation in weighted Korobov spaces
• On the tractability of linear tensor product problems in the worst case

This page was built for publication: Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals

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