{
  "id": "1402.5011",
  "version": "v2",
  "published": "2014-02-20T14:37:49.000Z",
  "updated": "2014-12-02T16:57:24.000Z",
  "title": "Tractability of the approximation of high-dimensional rank one tensors",
  "authors": [
    "Erich Novak",
    "Daniel Rudolf"
  ],
  "comment": "15 pages, to appear in Constr. Approx",
  "categories": [
    "math.NA"
  ],
  "abstract": "We study the approximation of high-dimensional rank one tensors using point evaluations and consider deterministic as well as randomized algorithms. We prove that for certain parameters (smoothness and norm of the $r$th derivative) this problem is intractable while for other parameters the problem is tractable and the complexity is only polynomial in the dimension for every fixed $\\varepsilon>0$. For randomized algorithms we completely characterize the set of parameters that lead to easy or difficult problems, respectively. In the \"difficult\" case we modify the class to obtain a tractable problem: The problem gets tractable with a polynomial (in the dimension) complexity if the support of the function is not too small.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-02-20T14:37:49.000Z",
      "abstract": "We study the approximation of high-dimensional rank one tensors using point evaluations. We prove that for certain parameters (smoothness and norm of the $r$th derivative) this problem is intractable while for other parameters the problem is tractable and the complexity is only polynomial in the dimension. We completely characterize the set of parameters that lead to easy or difficult problems, respectively. In the \"difficult\" case we modify the class to obtain a tractable problem: The problem gets tractable with a polynomial (in the dimension) complexity if the support of the function is not too small.",
      "comment": "13 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-12-02T16:57:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65D15",
      "65Y20",
      "41A25",
      "41A63",
      "65C05"
    ],
    "keywords": [
      "high-dimensional rank",
      "approximation",
      "tractability",
      "parameters",
      "point evaluations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.5011N"
    }
  }
}