Revisiting Approximate Leverage Score Sketching for Matrix Least Squares
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_ | 1866918413598720000 |
|---|---|
| author | Larsen, Brett W. Kolda, Tamara G. |
| author_facet | Larsen, Brett W. Kolda, Tamara G. |
| contents | We revisit the problem of sketching using approximate leverage scores for matrix least squares problems of the form $\| AX - B \|_F^2$ where the design matrix $A \in \mathbb{R}^{N \times r}$ is tall and skinny with $N \gg r$. We derive the theoretical results from first principles and clarify the relation to previously stated bounds, improving some constants along the way. One can characterize the utility of a sketching scheme according to the number of samples it needs for an $\varepsilon$-accurate solution with high probability. Assuming $\varepsilon$ is suitably small, we will show that approximate leverage score sampling requires $4r/(βδ\varepsilon)$ samples, where $δ$ is the failure probability and $β\in (0,1]$ is a measure of the quality of the approximate leverage scores such that $β=1$ corresponds to using exact leverage scores. In cases where a few approximate leverage scores are very large (summing to $p_{\rm det}$), we also show that using a hybrid deterministic and random sampling scheme reduces the required number of samples by a factor of $1/(1-p_{\rm det})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_10638 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Revisiting Approximate Leverage Score Sketching for Matrix Least Squares Larsen, Brett W. Kolda, Tamara G. Numerical Analysis Data Structures and Algorithms We revisit the problem of sketching using approximate leverage scores for matrix least squares problems of the form $\| AX - B \|_F^2$ where the design matrix $A \in \mathbb{R}^{N \times r}$ is tall and skinny with $N \gg r$. We derive the theoretical results from first principles and clarify the relation to previously stated bounds, improving some constants along the way. One can characterize the utility of a sketching scheme according to the number of samples it needs for an $\varepsilon$-accurate solution with high probability. Assuming $\varepsilon$ is suitably small, we will show that approximate leverage score sampling requires $4r/(βδ\varepsilon)$ samples, where $δ$ is the failure probability and $β\in (0,1]$ is a measure of the quality of the approximate leverage scores such that $β=1$ corresponds to using exact leverage scores. In cases where a few approximate leverage scores are very large (summing to $p_{\rm det}$), we also show that using a hybrid deterministic and random sampling scheme reduces the required number of samples by a factor of $1/(1-p_{\rm det})$. |
| title | Revisiting Approximate Leverage Score Sketching for Matrix Least Squares |
| topic | Numerical Analysis Data Structures and Algorithms |
| url | https://arxiv.org/abs/2201.10638 |