Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929677753384960 |
|---|---|
| author | Chu, Ya-Chi Cortinovis, Alice |
| author_facet | Chu, Ya-Chi Cortinovis, Alice |
| contents | In this work, we analyze the variance of a stochastic estimator for computing Schatten norms of matrices. The estimator extracts information from a single sketch of the matrix, that is, the product of the matrix with a few standard Gaussian random vectors. While this estimator has been proposed and used in the literature before, the existing variance bounds are often pessimistic. Our work provides a new upper bound and estimates of the variance of this estimator. These theoretical findings are supported by numerical experiments, demonstrating that the new bounds are significantly tighter than the existing ones in the case of numerically low-rank matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_17414 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices Chu, Ya-Chi Cortinovis, Alice Numerical Analysis 65F35 (primary), 62J10, 68W20 (secondary) In this work, we analyze the variance of a stochastic estimator for computing Schatten norms of matrices. The estimator extracts information from a single sketch of the matrix, that is, the product of the matrix with a few standard Gaussian random vectors. While this estimator has been proposed and used in the literature before, the existing variance bounds are often pessimistic. Our work provides a new upper bound and estimates of the variance of this estimator. These theoretical findings are supported by numerical experiments, demonstrating that the new bounds are significantly tighter than the existing ones in the case of numerically low-rank matrices. |
| title | Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices |
| topic | Numerical Analysis 65F35 (primary), 62J10, 68W20 (secondary) |
| url | https://arxiv.org/abs/2408.17414 |