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

Given a matrix A is an element of R-nxn, 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. (C) 2011 Elsevier B.V. All rights reserved.