  Randomized matrix sparsification has proven to be a fruitful technique for
producing faster algorithms in applications ranging from graph partitioning to
semidefinite programming. In the decade or so of research into this technique,
the focus has been--with few exceptions--on ensuring the quality of
approximation in the spectral and Frobenius norms. For certain graph
algorithms, however, the $(\infty,1)$ norm may be a more natural measure of
performance.
  This paper addresses the problem of approximating a real matrix A by a sparse
random matrix X with respect to several norms. It provides the first results on
approximation error in the $(\infty, 1)$ and $(\infty, 2)$ norms, and it uses a
result of Latala to study approximation error in the spectral norm. These
bounds hold for random sparsification schemes which ensure that the entries of
X are independent and average to the corresponding entries of A. Optimality of
the $(\infty, 1)$ and $(\infty,2)$ error estimates is established.
Concentration results for the three norms hold when the entries of X are
uniformly bounded. The spectral error bound is used to predict the performance
of several sparsification and quantization schemes that have appeared in the
literature; the results are competitive with the performance guarantees given
by earlier scheme-specific analyses.
