Superfast 1-Norm Estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916760320475136 |
|---|---|
| author | Go, Soo Pan, Victor Y. |
| author_facet | Go, Soo Pan, Victor Y. |
| contents | A matrix algorithm is said to be superfast (that is, runs at sublinear cost) if it involves much fewer scalars and flops than the input matrix has entries. Such algorithms have been extensively studied and widely applied in modern computations for matrices with low displacement rank and more recently for low-rank approximation of matrices, even though they are known to fail on worst-case inputs in the latter application. We devise novel superfast algorithms that consistently produce accurate 1-norm estimates for real-world matrices and discuss some promising extensions of our surprisingly simple techniques. With further testing and refinement, our algorithms can potentially be adopted in practical computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20528 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Superfast 1-Norm Estimation Go, Soo Pan, Victor Y. Numerical Analysis 65F35, 65Y20, 68Q25 A matrix algorithm is said to be superfast (that is, runs at sublinear cost) if it involves much fewer scalars and flops than the input matrix has entries. Such algorithms have been extensively studied and widely applied in modern computations for matrices with low displacement rank and more recently for low-rank approximation of matrices, even though they are known to fail on worst-case inputs in the latter application. We devise novel superfast algorithms that consistently produce accurate 1-norm estimates for real-world matrices and discuss some promising extensions of our surprisingly simple techniques. With further testing and refinement, our algorithms can potentially be adopted in practical computations. |
| title | Superfast 1-Norm Estimation |
| topic | Numerical Analysis 65F35, 65Y20, 68Q25 |
| url | https://arxiv.org/abs/2505.20528 |