{
  "id": "2308.05814",
  "version": "v1",
  "published": "2023-08-10T18:30:11.000Z",
  "updated": "2023-08-10T18:30:11.000Z",
  "title": "Randomized low-rank approximations beyond Gaussian random matrices",
  "authors": [
    "Arvind K. Saibaba",
    "Agnieszka Międlar"
  ],
  "comment": "37 pages, appendix is really supplementary materials",
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "This paper expands the analysis of randomized low-rank approximation beyond the Gaussian distribution to four classes of random matrices: (1) independent sub-Gaussian entries, (2) independent sub-Gaussian columns, (3) independent bounded columns, and (4) independent columns with bounded second moment. Using a novel interpretation of the low-rank approximation error involving sample covariance matrices, we provide insight into the requirements of a \\textit{good random matrix} for the purpose of randomized low-rank approximation. Although our bounds involve unspecified absolute constants (a consequence of the underlying non-asymptotic theory of random matrices), they allow for qualitative comparisons across distributions. The analysis offers some details on the minimal number of samples (the number of columns $\\ell$ of the random matrix $\\boldsymbol\\Omega$) and the error in the resulting low-rank approximation. We illustrate our analysis in the context of the randomized subspace iteration method as a representative algorithm for low-rank approximation, however, all the results are broadly applicable to other low-rank approximation techniques. We conclude our discussion with numerical examples using both synthetic and real-world test matrices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-10T18:30:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random matrix",
      "randomized low-rank approximation",
      "gaussian random matrices",
      "independent sub-gaussian entries",
      "independent sub-gaussian columns"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}