Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

Let $\mathbf S \in \mathbb R^{n \times n}$ satisfy $\|\mathbf 1-\mathbf S\|_2\leεn$, where $\mathbf 1$ is the all ones matrix and $\|\cdot\|_2$ is the spectral norm. It is well-known that there exists such an $\mathbf S$ with just $O(n/ε^2)$ non-zero entries: we can let $\mathbf S$ be the scaled adj...

Popoln opis

Bibliografske podrobnosti

Autores principales:	Bhattacharjee, Rajarshi, Dexter, Gregory, Musco, Cameron, Ray, Archan, Sachdeva, Sushant, Woodruff, David P
Format:	Artículo
Izdano:	2023
Teme:	Data Structures and Algorithms Numerical Analysis F.2.1; G.1.3; G.1.2; G.4; I.1.2
Online dostop:	https://arxiv.org/abs/2305.05826 http://arxiv.org/abs/2305.05826
Oznake:	Označite Brez oznak, prvi označite!