# Randomized low-rank approximations beyond Gaussian random matrices

Source: [Randomized low-rank approximations beyond Gaussian random matrices](<https://www.sota2.com/research/paper/68fa5ab31e209131ce9c210e>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T16:38:49.818Z

Authors: Arvind K. Saibaba, Agnieszka Mi\\k{e}dlar

Published: 2023-08-10T18:30:11.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2308.05814>)

[PDF](<https://arxiv.org/pdf/2308.05814.pdf>)
