Tractability of tensor product problems in the average case setting

Anargyros Papageorgiou, Iasonas Petras

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem S=Sd in the average case setting to be weakly tractable but not polynomially tractable. As a result of the tensor product structure, the eigenvalues of the covariance operator of the induced measure in the one-dimensional problem characterize the complexity of approximating Sd d≥1, with accuracy ε. If ∑j=j=1 λj ≥ 1 and λ2 > 0, we know that S is not polynomially tractable iff lim sup j→∞λjjp =∞ for all p > 1. Thus we settle the open problem by showing that S is weakly tractable iff ∑j>n λj=o(ln-2n). In particular, assume that ℓ=lim/j→∞λjjln 3(j+1), exists. Then S is weakly tractable iff ℓ = 0.

Original languageEnglish (US)
Pages (from-to)273-280
Number of pages8
JournalJournal of Complexity
Volume27
Issue number3-4
DOIs
StatePublished - 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Complexity
  • Multivariate problem
  • Tractability

Fingerprint

Dive into the research topics of 'Tractability of tensor product problems in the average case setting'. Together they form a unique fingerprint.

Cite this