Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914844174712832 |
|---|---|
| author | Levitt, James Martinsson, Per-Gunnar |
| author_facet | Levitt, James Martinsson, Per-Gunnar |
| contents | A randomized algorithm for computing a compressed representation of a given rank-structured matrix $A \in \mathbb{R}^{N\times N}$ is presented. The algorithm interacts with $A$ only through its action on vectors. Specifically, it draws two tall thin matrices $Ω,\,Ψ\in \mathbb{R}^{N\times s}$ from a suitable distribution, and then reconstructs $A$ from the information contained in the set $\{AΩ,\,Ω,\,A^{*}Ψ,\,Ψ\}$. For the specific case of a "Hierarchically Block Separable (HBS)" matrix (a.k.a. Hierarchically Semi-Separable matrix) of block rank $k$, the number of samples $s$ required satisfies $s = O(k)$, with $s \approx 3k$ being representative. While a number of randomized algorithms for compressing rank-structured matrices have previously been published, the current algorithm appears to be the first that is both of truly linear complexity (no $N\log(N)$ factors in the complexity bound) and fully "black box" in the sense that no matrix entry evaluation is required. Further, all samples can be extracted in parallel, enabling the algorithm to work in a "streaming" or "single view" mode. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_02990 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices Levitt, James Martinsson, Per-Gunnar Numerical Analysis 65F05 A randomized algorithm for computing a compressed representation of a given rank-structured matrix $A \in \mathbb{R}^{N\times N}$ is presented. The algorithm interacts with $A$ only through its action on vectors. Specifically, it draws two tall thin matrices $Ω,\,Ψ\in \mathbb{R}^{N\times s}$ from a suitable distribution, and then reconstructs $A$ from the information contained in the set $\{AΩ,\,Ω,\,A^{*}Ψ,\,Ψ\}$. For the specific case of a "Hierarchically Block Separable (HBS)" matrix (a.k.a. Hierarchically Semi-Separable matrix) of block rank $k$, the number of samples $s$ required satisfies $s = O(k)$, with $s \approx 3k$ being representative. While a number of randomized algorithms for compressing rank-structured matrices have previously been published, the current algorithm appears to be the first that is both of truly linear complexity (no $N\log(N)$ factors in the complexity bound) and fully "black box" in the sense that no matrix entry evaluation is required. Further, all samples can be extracted in parallel, enabling the algorithm to work in a "streaming" or "single view" mode. |
| title | Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices |
| topic | Numerical Analysis 65F05 |
| url | https://arxiv.org/abs/2205.02990 |