2009/11/20 by Alex Gittens, Joel A. Tropp, Gittens, Alex +1 · 1 citation
Computer Science · Mathematics · #65C99 #65F50 (Secondary) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.0911.4108
openalex publication_date 2009/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (∞,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 (∞, 1) and (∞, 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 (∞, 1) and (∞,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.