Average case tractability of non-homogeneous tensor product problems

DOI10.1016/J.JCO.2012.05.003zbMATH Open1262.65212arXiv1112.4251OpenAlexW2063089937MaRDI QIDQ454823FDOQ454823

Authors: A. Papageorgiou, H. Woźniakowski, M. A. Lifshits 

Publication date: 10 October 2012

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

Abstract: We study d-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. Our interest is focused on measures having a structure of non-homogeneous linear tensor product, where covariance kernel is a product of univariate kernels. We consider the normalized average error of algorithms that use finitely many evaluations of arbitrary linear functionals. The information complexity is defined as the minimal number n(h,d) of such evaluations for error in the d-variate case to be at most h. The growth of n(h,d) as a function of h^{-1} and d depends on the eigenvalues of the covariance operator and determines whether a problem is tractable or not. Four types of tractability are studied and for each of them we find the necessary and sufficient conditions in terms of the eigenvalues of univariate kernels. We illustrate our results by considering approximation problems related to the product of Korobov kernels characterized by a weights g_k and smoothnesses r_k. We assume that weights are non-increasing and smoothness parameters are non-decreasing. Furthermore they may be related, for instance g_k=g(r_k) for some non-increasing function g. In particular, we show that approximation problem is strongly polynomially tractable, i.e., n(h,d)le C h^{-p} for all d and 0<h<1, where C and p are independent of h and d, iff liminf |ln g_k|/ln k >1. For other types of tractability we also show necessary and sufficient conditions in terms of the sequences g_k and r_k.

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

Recommendations

• Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems
• Average case tractability of multivariate approximation with Gaussian kernels
• Quasi-polynomial tractability of linear problems in the average case setting
• Average case tractability of a multivariate approximation problem
• Tractability of linear multivariate problems in the average case setting

zbMATH Keywords

eigenvaluesalgorithmGaussian measurequasi-polynomial tractabilitymultivariate approximationcovariance operatorinformation complexityweak tractabilityKorobov kernelslinear multivariate tensor product problemspolynomial tractability

Mathematics Subject Classification ID

Gaussian processes (60G15) Random fields (60G60) Complexity and performance of numerical algorithms (65Y20) Multidimensional problems (41A63)

Cites Work

• Title not available (Why is that?)
• Curse of dimensionality in approximation of random fields
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume III: Standard information for operators
• Approximation complexity of additive random fields
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of tensor product problems in the average case setting
• Tractability of linear multivariate problems in the average case setting
• Tractability through increasing smoothness
• On the average complexity of multivariate problems

Cited In (26)

• Asymptotic analysis in multivariate average case approximation with Gaussian kernels
• A simplified criterion for quasi-polynomial tractability of approximation of random elements and its applications
• Convergence types and rates in generic Karhunen-Loève expansions with applications to sample path properties
• Exponential convergence-tractability of general linear problems in the average case setting
• Tractability of function approximation with product kernels
• Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements
• Tractability of linear problems defined over Hilbert spaces
• Uniform weak tractability of multivariate problems with increasing smoothness
• On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting
• ABC on IBC
• On the tractability of linear tensor product problems in the worst case
• Average-case complexity of the min-sum matrix product problem
• Average case \((s, t)\)-weak tractability of non-homogeneous tensor product problems
• Quasi-polynomial tractability of linear problems in the average case setting
• Asymptotics of Average Case Approximation Complexity for Tensor Products of Euler Integrated Processes
• EC-\((s, t)\)-weak tractability of multivariate linear problems in the average case setting
• On the history of St. Petersburg school of probability and mathematical statistics. II: Random processes and dependent variables
• Approximation of additive random fields based on standard information: average case and probabilistic settings
• \((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
• Asymptotic analysis of average case approximation complexity of additive random fields
• \((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 approximation: convergence and tractability of Gaussian kernels
• Average case tractability of a multivariate approximation problem
• Average case tractability of multivariate approximation with Gaussian kernels

This page was built for publication: Average case tractability of non-homogeneous tensor product problems

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