{
  "id": "2101.05200",
  "version": "v1",
  "published": "2021-01-12T05:24:53.000Z",
  "updated": "2021-01-12T05:24:53.000Z",
  "title": "On the power of standard information for tractability for $L_2$-approximation in the average case setting",
  "authors": [
    "Wanting Lu",
    "Heping Wang"
  ],
  "comment": "23 pages. arXiv admin note: substantial text overlap with arXiv:2101.03665",
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "We study multivariate approximation in the average case setting with the error measured in the weighted $L_2$ norm. We consider algorithms that use standard information $\\Lambda^{\\rm std}$ consisting of function values or general linear information $\\Lambda^{\\rm all}$ consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for $\\Lambda^{\\rm std}$ and $\\Lambda^{\\rm all}$ for the absolute error criterion, and show that the power of $\\Lambda^{\\rm std}$ is the same as that of $\\Lambda^{\\rm all}$ for all notions of algebraic and exponential tractability without any condition. Specifically, we solve Open Problems 116-118 and almost solve Open Problem 115 as posed by E.Novak and H.Wo\\'zniakowski in the book: Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS Tracts in Mathematics, Z\\\"urich, 2012.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-01-12T05:24:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "41A63",
      "65C05",
      "65D15",
      "65Y20"
    ],
    "keywords": [
      "average case setting",
      "standard information",
      "open problem",
      "exponential tractability",
      "general linear information"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}