Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco +3

Let $\mathbf{S}\in {\mathbb{R}}^{n\times n}$ satisfy $\Vert 1-\mathbf{S}{\Vert }_2\le \epsilon n$, where $1$ is the all ones matrix and $\Vert \cdot {\Vert }_2$ is the spectral norm. It is well-kno…