{
  "id": "2101.03665",
  "version": "v1",
  "published": "2021-01-11T02:15:02.000Z",
  "updated": "2021-01-11T02:15:02.000Z",
  "title": "On the power of standard information for tractability for $L_2$-approximation in the randomized setting",
  "authors": [
    "Wanting Lu",
    "Heping Wang"
  ],
  "comment": "25 pages",
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "We study approximation of multivariate functions from a separable Hilbert space in the randomized 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 linear functionals. We use the weighted least squares regression algorithm to obtain the upper estimates of the minimal randomized error using $\\Lambda^{\\rm std}$. We investigate the equivalences of various notions of algebraic and exponential tractability for $\\Lambda^{\\rm std}$ and $\\Lambda^{\\rm all}$ for the normalized or absolute error criterion. We show that in the randomized setting for the normalized or absolute error criterion, the power of $\\Lambda^{\\rm std}$ is the same as that of $\\Lambda^{\\rm all}$ for all notions of exponential and algebraic tractability without any condition. Specifically, we solve four Open Problems 98, 100-102 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-11T02:15:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "41A63",
      "65C05",
      "65D15",
      "65Y20"
    ],
    "keywords": [
      "standard information",
      "randomized setting",
      "tractability",
      "absolute error criterion",
      "approximation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}