(S, T)-WEAK TRACTABILITY OF MULTIVARIATE LINEAR PROBLEMS IN THE AVERAGE CASE SETTING

doi:10.1007/s10473-019-0409-x

数学物理学报(英文版) ›› 2019, Vol. 39 ›› Issue (4): 1033-1052.doi: 10.1007/s10473-019-0409-x

(S, T)-WEAK TRACTABILITY OF MULTIVARIATE LINEAR PROBLEMS IN THE AVERAGE CASE SETTING

刘永平¹, 许贵桥²

1. School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China;
2. Department of Mathematics, Tianjin Normal University, Tianjin 300387, China

收稿日期:2017-10-24 修回日期:2018-07-02 出版日期:2019-08-25 发布日期:2019-09-12
作者简介:Yongping LIU,E-mail:ypliu@bnu.edu.cn;Guiqiao XU,E-mail:Xuguiqiao@aliyun.com
基金资助:
This work was supported by the National Natural Science Foundation of China (11471043, 11671271) and the Beijing Natural Science Foundation (1172004).

(S, T)-WEAK TRACTABILITY OF MULTIVARIATE LINEAR PROBLEMS IN THE AVERAGE CASE SETTING

Yongping LIU¹, Guiqiao XU²

1. School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China;
2. Department of Mathematics, Tianjin Normal University, Tianjin 300387, China

Received:2017-10-24 Revised:2018-07-02 Online:2019-08-25 Published:2019-09-12
Supported by:
This work was supported by the National Natural Science Foundation of China (11471043, 11671271) and the Beijing Natural Science Foundation (1172004).

摘要/Abstract

摘要： 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.

关键词: (s,t)-weak tractability, linear problem, linear tensor product problem, Hilbert space, average case setting

Abstract: 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.

Key words: (s,t)-weak tractability, linear problem, linear tensor product problem, Hilbert space, average case setting

中图分类号:

41A63

刘永平, 许贵桥. (S, T)-WEAK TRACTABILITY OF MULTIVARIATE LINEAR PROBLEMS IN THE AVERAGE CASE SETTING[J]. 数学物理学报(英文版), 2019, 39(4): 1033-1052.

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.

参考文献

[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

(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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

Metrics

本文评价

推荐阅读 5

[1]	Yekini SHEHU, Olaniyi. S. IYIOLA. CONVERGENCE OF HYBRID VISCOSITY AND STEEPEST-DESCENT METHODS FOR PSEUDOCONTRACTIVE MAPPINGS AND NONLINEAR HAMMERSTEIN EQUATIONS[J]. 数学物理学报(英文版), 2018, 38(2): 610-626.
[2]	赵静, 王盛楠. VISCOSITY APPROXIMATION METHODS FOR THE SPLIT EQUALITY COMMON FIXED POINT PROBLEM OF QUASI-NONEXPANSIVE OPERATORS[J]. 数学物理学报(英文版), 2016, 36(5): 1474-1486.
[3]	唐金芳, 张石生, 刘敏. GENERAL SPLIT FEASIBILITY PROBLEMS FOR TWO FAMILIES OF NONEXPANSIVE MAPPINGS IN HILBERT SPACES[J]. 数学物理学报(英文版), 2016, 36(2): 602-613.
[4]	Huaixin CAO, Zhengli CHEN, Li LI, Baomin YU. AN APPLICABLE APPROXIMATION METHOD AND ITS APPLICATION[J]. 数学物理学报(英文版), 2015, 35(5): 1189-1202.
[5]	范海宁, 刘晓春. MULTIPLE POSITIVE SOLUTIONS FOR A CLASS OF QUASI-LINEAR ELLIPTIC EQUATIONS INVOLVING CRITICAL SOBOLEV EXPONENT[J]. 数学物理学报(英文版), 2014, 34(4): 1111-1126.
[6]	H.R. SAHEBI, A. RAZANI. A SOLUTION OF A GENERAL EQUILIBRIUM PROBLEM[J]. 数学物理学报(英文版), 2013, 33(6): 1598-1614.
[7]	B. YOUSEFI, Sh. KHOSHDEL, Y. JAHANSHAHI. MULTIPLICATION OPERATORS ON INVARIANT SUBSPACES OF FUNCTION SPACES[J]. 数学物理学报(英文版), 2013, 33(5): 1463-1470.
[8]	陈泽乾, 孙牧. AREA INTEGRAL FUNCTIONS AND H^∞ FUNCTIONAL CALCULUS FOR SECTORIAL OPERATORS ON HILBERT SPACES[J]. 数学物理学报(英文版), 2013, 33(4): 989-997.
[9]	B.Yousefi. UNIVERSAL INTERPOLATING SEQUENCES ON SPACES OF ANALYTIC FUNCTIONS[J]. 数学物理学报(英文版), 2011, 31(1): 68-72.
[10]	康东升. SOLUTIONS FOR THE QUASILINEAR ELLIPTIC PROBLEMS INVOLVING CRITICAL HARDY--SOBOLEV EXPONENTS[J]. 数学物理学报(英文版), 2010, 30(5): 1529-1540.
[11]	王瑞东. ON LINEAR EXTENSION OF 1-LIPSCHITZ MAPPING FROM HILBERT SPACE INTO A NORMED SPACE[J]. 数学物理学报(英文版), 2010, 30(1): 161-165.
[12]	丁夏畦, 罗佩珠. Generalized expansions in Hilbert space[J]. 数学物理学报(英文版), 1999, 19(3): 241-250.
[13]	喻小培, 蹇明. MEAN VALUE OF ANALYTIC OPERATOR FUNCTIONS[J]. 数学物理学报(英文版), 1995, 15(4): 468-473.
[14]	胡国庆, 李开泰. EXTENDED SYSTEM, BIFURCATION PROBLEM AND HIGH ORDER SINGULARITIES[J]. 数学物理学报(英文版), 1995, 15(1): 65-73.