EC-(s,t)-weak tractability of multivariate linear problems in the average case setting

Anargyros Papageorgiou, Iasonas Petras, Guiqiao Xu, Dong Yanqi

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

We study EC-(s,t)-weak tractability of multivariate linear problems in the average case setting. This paper extends earlier work in the worst case setting. The parameters s≥0 and t≥0 allow us to study the information complexity n(ε,d) of a d-variate problem with respect to different powers of lnε−1, corresponding to the bits of accuracy, and d. We consider the absolute and normalized error criteria. In particular, a multivariate problem is EC-(s,t)-weakly tractable iff limd+ε−1→∞lnn(ε,d)∕[dt+lnsε−1]=0. We deal with general linear problems and linear tensor product problems. We show necessary and sufficient conditions for EC-(s,t)-weak tractability. In the case of general linear problem these conditions are matching. For linear tensor product problems, we also show matching conditions with the exception of some cases where s>1, in general.

Original languageEnglish (US)
Article number101425
JournalJournal of Complexity
Volume55
DOIs
StatePublished - Dec 1 2019

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics(all)
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Average case setting
  • EC-(s,t)-weak tractability
  • Hilbert space
  • Linear problem
  • Linear tensor product problem

Fingerprint Dive into the research topics of 'EC-(s,t)-weak tractability of multivariate linear problems in the average case setting'. Together they form a unique fingerprint.

  • Cite this