The purpose of this article is to investigate (s,t)-weak tractability of multivariate linear problems in the average case setting. The considered algorithms use finitely many evaluations of arbitrary linear functionals. Generally, we obtained matching necessary and sufficient conditions for (s,t)-weak tractability in terms of the corresponding non-increasing sequence of eigenvalues. Specifically, we discussed (s,t)-weak tractability of linear tensor product problems and obtained necessary and sufficient conditions in terms of the corresponding one-dimensional problem. As an example of applications, we discussed also (s,t)-weak tractability of a multivariate approximation problem.
Yongping LIU
,
Guiqiao XU
. (S, T)-WEAK TRACTABILITY OF MULTIVARIATE LINEAR PROBLEMS IN THE AVERAGE CASE SETTING[J]. Acta mathematica scientia, Series B, 2019
, 39(4)
: 1033
-1052
.
DOI: 10.1007/s10473-019-0409-x
[1] Traub J, Wasilkowski G, Wózniakowski H. Information-Based Complexity. New York:Academic Press, 1988
[2] Wózniakowski H. Tractability and strong tractability of linear multivariate problems. J Complexity, 1994, 10:96-128
[3] Siedlecki P, Weimar M. Notes on (s, t)-weak tractability:A refined classification of problems with (sub)exponential information complexity. J Approx Theory, 2015, 200:227-258
[4] Novak E, Wózniakowski H. Tractability of multivariate problems. Volume I:Linear Information//EMS Tracts in Mathematics. Vol 6. Zürich:European Mathematical Society (EMS), 2008
[5] Novak E, Wózniakowski H. Tractability of multivariate problems. Volume Ⅱ:Standard Information for Functionals//EMS Tracts in Mathematics. Vol 12. Zürich:European Mathematical Society (EMS), 2010
[6] Novak E, Wózniakowski H. Tractability of multivariate problems. Volume Ⅲ:Standard Information for Operator//EMS Tracts in Mathematics. Vol 18. Zürich:European Mathematical Society (EMS), 2012
[7] Hickernell F J, Wasilkowski G W, Wózniakowski H. Tractability of linear multivariate problems in the average case setting//Keller A, Heinrich S, Niederreiter H. Monte Carlo and Quasi-Monte Carlo Methods 2006. Berlin:Springer, 2008:461-494
[8] Hickernell F J, Wózniakowski H. Integration and approximation in arbitrary dimension. Adv Comput Math, 2000, 12:25-58
[9] Lifshits M A, Papageorgiou A, Wózniakowski H. Average case tractability of non-homogeneous tensor product problems. J Complexity, 2012, 28:539-561
[10] Xu G Q. Quasi-polynomial tractability of linear problems in the average case setting. J Complexity, 2014, 30:54-68
[11] Xu G Q. Tractability of linear problems defined over Hilbert spaces. J Complexity, 2014, 30:735-749
[12] Papageorgiou A, Petras I. Tractability of tensor product problems in the average case setting. J Complexity, 2011, 27:273-280
[13] Siedlecki P. Uniform weak tractability. J Complexity, 2013, 29:438-453
[14] Lifshits M A, Papageorgiou A, Wózniakowski H. Tractability of multi-parametric Euler and Wiener integrated processes. Probability and Mathematical Statistics, 2012, 32(1):131-165
[15] Siedlecki P. Uniform weak tractability of multivariate problems with increasing smoothness. J Complexity, 2014, 30:716-734
[16] Khartov A A. A simplified criterion for quasi-polynomial tractability of approximation of random elements and its application. J Complexity, 2016, 34:30-41
[17] Siedlecki P. (s, t)-weak tractability of Euler and Wiener integrated processes. J Comolexity, 2016, 45:55-66
[18] Weimar M. Breaking the curse of dimensionality[D]. Marburg:Philipps University Marburg, 2015, 505:1-112
[19] Lifshits M, Zani M. Approximation of additive random fields based on standard information:Average case and probabilistic settings. J Complexity, 2015, 31:659-674
[20] Liu Y P, Xu G Q. Average case tractability of a multivariate approximation problem. J Complexity, 2017, 43:76-102
[21] Werschulz A G, Wózniakowski H. A new characterization of (s, t)-weak tractability. J Complexity, 2017, 38:68-79
[22] Dick J, Kritzer P, Pillichshammer F, Wózniakowski H. Approximation of analytic functions in Korobov spaces. J Complexity, 2014, 30:2-28
