Approximating Sparse Matrices and their Functions using Matrix-vector products
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911474758189056 |
|---|---|
| author | Park, Taejun Nakatsukasa, Yuji |
| author_facet | Park, Taejun Nakatsukasa, Yuji |
| contents | The computation of a matrix function $f(A)$ is an important task in scientific computing appearing in machine learning, network analysis and the solution of partial differential equations. In this work, we use only matrix-vector products $x\mapsto Ax$ to approximate functions of sparse matrices and matrices with similar structures such as sparse matrices $A$ themselves or matrices that have a similar decay property as matrix functions. We show that when $A$ is a sparse matrix with an unknown sparsity pattern, techniques from compressed sensing can be used under natural assumptions. Moreover, if $A$ is a banded matrix then certain deterministic matrix-vector products can efficiently recover the large entries of $f(A)$. We describe an algorithm for each of the two cases and give error analysis based on the decay bound for the entries of $f(A)$. We finish with numerical experiments showing the accuracy of our algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05625 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximating Sparse Matrices and their Functions using Matrix-vector products Park, Taejun Nakatsukasa, Yuji Numerical Analysis 65F50, 65F55, 65F60 The computation of a matrix function $f(A)$ is an important task in scientific computing appearing in machine learning, network analysis and the solution of partial differential equations. In this work, we use only matrix-vector products $x\mapsto Ax$ to approximate functions of sparse matrices and matrices with similar structures such as sparse matrices $A$ themselves or matrices that have a similar decay property as matrix functions. We show that when $A$ is a sparse matrix with an unknown sparsity pattern, techniques from compressed sensing can be used under natural assumptions. Moreover, if $A$ is a banded matrix then certain deterministic matrix-vector products can efficiently recover the large entries of $f(A)$. We describe an algorithm for each of the two cases and give error analysis based on the decay bound for the entries of $f(A)$. We finish with numerical experiments showing the accuracy of our algorithms. |
| title | Approximating Sparse Matrices and their Functions using Matrix-vector products |
| topic | Numerical Analysis 65F50, 65F55, 65F60 |
| url | https://arxiv.org/abs/2310.05625 |