Near-Optimal Entrywise Sampling of Numerically Sparse Matrices

Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan +1

Many real-world data sets are sparse or almost sparse. One method to measure this for a matrix $A\in {\mathbb{R}}^{n\times n}$ is the \emph{numerical sparsity}, denoted $\mathsf{ns}(…