{
  "id": "2212.09841",
  "version": "v1",
  "published": "2022-12-19T20:38:36.000Z",
  "updated": "2022-12-19T20:38:36.000Z",
  "title": "Matrix recovery from matrix-vector products",
  "authors": [
    "Diana Halikias",
    "Alex Townsend"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "Can one recover a matrix efficiently from only matrix-vector products? If so, how many are needed? This paper describes algorithms to recover structured matrices, such as tridiagonal, Toeplitz, Toeplitz-like, and hierarchical low-rank, from matrix-vector products. In particular, we derive a randomized algorithm for recovering an $N \\times N$ unknown hierarchical low-rank matrix from only $\\mathcal{O}((k+p)\\log(N))$ matrix-vector products with high probability, where $k$ is the rank of the off-diagonal blocks, and $p$ is a small oversampling parameter. We do this by carefully constructing randomized input vectors for our matrix-vector products that exploit the hierarchical structure of the matrix. While existing algorithms for hierarchical matrix recovery use a recursive \"peeling\" procedure based on elimination, our approach uses a recursive projection procedure.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-19T20:38:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "matrix-vector products",
      "unknown hierarchical low-rank matrix",
      "recursive projection procedure",
      "constructing randomized input vectors",
      "small oversampling parameter"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}