Mathematics – Numerical Analysis
Scientific paper
2009-11-20
Mathematics
Numerical Analysis
16 pages, no figures
Scientific paper
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.
Gittens Alex
Tropp Joel A.
No associations
LandOfFree
Error Bounds for Random Matrix Approximation Schemes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Error Bounds for Random Matrix Approximation Schemes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error Bounds for Random Matrix Approximation Schemes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-315655