A Caltech Library Service

Error Bounds for Random Matrix Approximation Schemes

Gittens, A. and Tropp, J. A. (2014) Error Bounds for Random Matrix Approximation Schemes. ACM Technical Reports, 2014-01. California Institute of Technology , Pasadena, CA. (Unpublished)

PDF - Accepted Version
Creative Commons Attribution.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Lata la to study approximation error in the spectral norm. These bounds hold for a reasonable family of random sparsification schemes, those 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.

Item Type:Report or Paper (Technical Report)
Gittens, A.0000-0003-3482-0157
Tropp, J. A.0000-0003-1024-1791
Group:Applied & Computational Mathematics
Series Name:ACM Technical Reports
Issue or Number:2014-01
Record Number:CaltechAUTHORS:20140828-082707636
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49010
Deposited By: Sydney Garstang
Deposited On:29 Aug 2014 20:52
Last Modified:26 Aug 2022 20:56

Repository Staff Only: item control page