Error Bounds for Random Matrix Approximation Schemes

Abstract

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.

16 pages, no figures

Cited by in corpus (7)

• A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality
• Tensor sparsification via a bound on the spectral norm of random tensors
• Randomized spectral co-clustering for large-scale directed networks
• Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
• On the approximation of a matrix
• Quantum strategies are better than classical in almost any XOR game
• Deterministic matrix sketches for low-rank compression of high-dimensional simulation data