A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality

Given a matrix A∈Rn×nA∈Rn×n, we present a simple, element-wise sparsification algorithm that zeroes out all sufficiently small elements of A and then retains some of the remaining elements with probabilities proportional to the square of their magnitudes. We analyze the approximation accuracy of the proposed algorithm using a recent, elegant non-commutative Bernstein inequality, and compare our bounds with all existing (to the best of our knowledge) element-wise matrix sparsification algorithms.

► We present a simple, element-wise matrix sparsification algorithm. ► Our algorithm retains elements of the matrix in a randomized manner. ► Our analysis leverages a non-commutative Bernstein inequality. ► We obtain the best known bounds for element-wise matrix sparsification.