Fixed-sparsity matrix approximation from matrix-vector products
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916177540808704 |
|---|---|
| author | Amsel, Noah Chen, Tyler Keles, Feyza Duman Halikias, Diana Musco, Cameron Musco, Christopher |
| author_facet | Amsel, Noah Chen, Tyler Keles, Feyza Duman Halikias, Diana Musco, Cameron Musco, Christopher |
| contents | We study the problem of approximating a matrix $\mathbf{A}$ with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when $\mathbf{A}$ is accessed only by matrix-vector products. We describe a simple randomized algorithm that returns an approximation with the given sparsity pattern with Frobenius-norm error at most $(1+\varepsilon)$ times the best possible error. When each row of the desired sparsity pattern has at most $s$ nonzero entries, this algorithm requires $O(s/\varepsilon)$ non-adaptive matrix-vector products with $\mathbf{A}$. We also prove a matching lower-bound, showing that, for any sparsity pattern with $Θ(s)$ nonzeros per row and column, any algorithm achieving $(1+ε)$ approximation requires $Ω(s/\varepsilon)$ matrix-vector products in the worst case. We thus resolve the matrix-vector product query complexity of the problem up to constant factors, even for the well-studied case of diagonal approximation, for which no previous lower bounds were known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_09379 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fixed-sparsity matrix approximation from matrix-vector products Amsel, Noah Chen, Tyler Keles, Feyza Duman Halikias, Diana Musco, Cameron Musco, Christopher Data Structures and Algorithms Numerical Analysis We study the problem of approximating a matrix $\mathbf{A}$ with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when $\mathbf{A}$ is accessed only by matrix-vector products. We describe a simple randomized algorithm that returns an approximation with the given sparsity pattern with Frobenius-norm error at most $(1+\varepsilon)$ times the best possible error. When each row of the desired sparsity pattern has at most $s$ nonzero entries, this algorithm requires $O(s/\varepsilon)$ non-adaptive matrix-vector products with $\mathbf{A}$. We also prove a matching lower-bound, showing that, for any sparsity pattern with $Θ(s)$ nonzeros per row and column, any algorithm achieving $(1+ε)$ approximation requires $Ω(s/\varepsilon)$ matrix-vector products in the worst case. We thus resolve the matrix-vector product query complexity of the problem up to constant factors, even for the well-studied case of diagonal approximation, for which no previous lower bounds were known. |
| title | Fixed-sparsity matrix approximation from matrix-vector products |
| topic | Data Structures and Algorithms Numerical Analysis |
| url | https://arxiv.org/abs/2402.09379 |