Fast algorithms for least square problems with Kronecker lower subsets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910919153418240 |
|---|---|
| author | Malik, Osman Asif Xu, Yiming Cheng, Nuojin Becker, Stephen Doostan, Alireza Narayan, Akil |
| author_facet | Malik, Osman Asif Xu, Yiming Cheng, Nuojin Becker, Stephen Doostan, Alireza Narayan, Akil |
| contents | While leverage score sampling provides powerful tools for approximating solutions to large least squares problems, the cost of computing exact scores and sampling often prohibits practical application. This paper addresses this challenge by developing a new and efficient algorithm for exact leverage score sampling applicable to matrices that are lower column subsets of Kronecker product matrices. We synthesize relevant approximation guarantees and detail the algorithm that specifically leverages this structural property for computational efficiency. Through numerical examples, we demonstrate that utilizing efficiently computed exact leverage scores via our methods significantly reduces approximation errors, as compared to established approximate leverage score sampling strategies when applied to this important class of structured matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_05662 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fast algorithms for least square problems with Kronecker lower subsets Malik, Osman Asif Xu, Yiming Cheng, Nuojin Becker, Stephen Doostan, Alireza Narayan, Akil Numerical Analysis Data Structures and Algorithms While leverage score sampling provides powerful tools for approximating solutions to large least squares problems, the cost of computing exact scores and sampling often prohibits practical application. This paper addresses this challenge by developing a new and efficient algorithm for exact leverage score sampling applicable to matrices that are lower column subsets of Kronecker product matrices. We synthesize relevant approximation guarantees and detail the algorithm that specifically leverages this structural property for computational efficiency. Through numerical examples, we demonstrate that utilizing efficiently computed exact leverage scores via our methods significantly reduces approximation errors, as compared to established approximate leverage score sampling strategies when applied to this important class of structured matrices. |
| title | Fast algorithms for least square problems with Kronecker lower subsets |
| topic | Numerical Analysis Data Structures and Algorithms |
| url | https://arxiv.org/abs/2209.05662 |