{
  "id": "2309.02877",
  "version": "v1",
  "published": "2023-09-06T10:05:14.000Z",
  "updated": "2023-09-06T10:05:14.000Z",
  "title": "A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format",
  "authors": [
    "Alberto Bucci",
    "Leonardo Robol"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "The Nystr\\\"om method offers an effective way to obtain low-rank approximation of SPD matrices, and has been recently extended and analyzed to nonsymmetric matrices (leading to the generalized Nystr\\\"om method). It is a randomized, single-pass, streamable, cost-effective, and accurate alternative to the randomized SVD, and it facilitates the computation of several matrix low-rank factorizations. In this paper, we take these advancements a step further by introducing a higher-order variant of Nystr\\\"om's methodology tailored to approximating low-rank tensors in the Tucker format: the multilinear Nystr\\\"om technique. We show that, by introducing appropriate small modifications in the formulation of the higher-order method, strong stability properties can be obtained. This algorithm retains the key attributes of the generalized Nystr\\\"om method, positioning it as a viable substitute for the randomized higher-order SVD algorithm.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-06T10:05:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "15A69",
      "65F55"
    ],
    "keywords": [
      "multilinear nyström algorithm",
      "low-rank approximation",
      "tucker format",
      "randomized higher-order svd algorithm",
      "strong stability properties"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}