Spectral Sparsification by Deterministic Discrepancy Walk
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_ | 1866916353631322112 |
|---|---|
| author | Lau, Lap Chi Wang, Robert Zhou, Hong |
| author_facet | Lau, Lap Chi Wang, Robert Zhou, Hong |
| contents | Spectral sparsification and discrepancy minimization are two well-studied areas that are closely related. Building on recent connections between these two areas, we generalize the "deterministic discrepancy walk" framework by Pesenti and Vladu [SODA~23] for vector discrepancy to matrix discrepancy, and use it to give a simpler proof of the matrix partial coloring theorem of Reis and Rothvoss [SODA~20]. Moreover, we show that this matrix discrepancy framework provides a unified approach for various spectral sparsification problems, from stronger notions including unit-circle approximation and singular-value approximation to weaker notions including graphical spectral sketching and effective resistance sparsification. In all of these applications, our framework produces improved results with a simpler and deterministic analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06146 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spectral Sparsification by Deterministic Discrepancy Walk Lau, Lap Chi Wang, Robert Zhou, Hong Data Structures and Algorithms Combinatorics Spectral sparsification and discrepancy minimization are two well-studied areas that are closely related. Building on recent connections between these two areas, we generalize the "deterministic discrepancy walk" framework by Pesenti and Vladu [SODA~23] for vector discrepancy to matrix discrepancy, and use it to give a simpler proof of the matrix partial coloring theorem of Reis and Rothvoss [SODA~20]. Moreover, we show that this matrix discrepancy framework provides a unified approach for various spectral sparsification problems, from stronger notions including unit-circle approximation and singular-value approximation to weaker notions including graphical spectral sketching and effective resistance sparsification. In all of these applications, our framework produces improved results with a simpler and deterministic analysis. |
| title | Spectral Sparsification by Deterministic Discrepancy Walk |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2408.06146 |