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.
In @cite_5 , Spielman and Srivastava improve upon this sampling scheme, instead keeping an edge with probability proportional to its ---a measure of how likely it is to appear in a random spanning tree of the graph. They provide an algorithm which produces a sparsifier with @math edges, where @math is the number of vertices in the graph. They obtain this result by reducing the problem to the behavior of projection matrices @math and @math associated with the original graph and the sparsifier, and appealing to a spectral norm concentration result.
@cite_5
2125664420
We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G=(V,E,w) and a parameter e>0, we produce a weighted subgraph H=(V, E, w) of G such that | E|=O(n log n e2) and for all vectors x in RV. (1-e) ∑uv ∈ E (x(u)-x(v))2wuv≤ ∑uv in E(x(u)-x(v))2 wuv ≤ (1+e)∑uv ∈ E(x(u)-x(v))2wuv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O(n logc n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in 0,1 V. We conjecture the existence of sparsifiers with O(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in O(log n) time.