We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph @math and a parameter @math , we produce a weighted subgraph @math of @math such that @math and for all vectors @math @math This improves upon the sparsifiers constructed by Spielman and Teng, which had @math edges for some large constant @math , and upon those of Bencz 'ur and Karger, which only satisfied (*) for @math . 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 @math time.
In addition to the graph sparsifiers of @cite_6 @cite_9 @cite_20 , there is a large body of work on sparse @cite_3 @cite_1 and low-rank @cite_4 @cite_1 @cite_0 @cite_23 @cite_16 approximations for general matrices. The algorithms in this literature provide guarantees of the form @math , where @math is the original matrix and @math is obtained by entrywise or columnwise sampling of @math . This is analogous to satisfying ) only for vectors @math in the span of the dominant eigenvectors of @math ; thus, if we were to use these sparsifiers on graphs, they would only preserve the large cuts. Interestingly, our proof uses some of the same machinery as the low-rank approximation result of Rudelson and Vershynin @cite_0 --- the sampling of edges in our algorithm corresponds to picking @math columns at random from a certain rank @math matrix of dimension @math (this is the matrix @math introduced in Section 3).
@cite_4 @cite_9 @cite_1 @cite_3 @cite_6 @cite_0 @cite_23 @cite_16 @cite_20
1970950689 1581656968 2051540665 1998058722 1587887312 2045107949
Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral features, that is, when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to A. Our technique amounts to independently sampling and or quantizing the entries of A, thus speeding up computation by reducing the number of nonzero entries and or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix N to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A p N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm. We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the Chernoff-Hoeffding bounds. Despite the simplicity, the approximation is comparable and sometimes better than previous work. Our algorithm computes the sparse matrix approximation in a single pass over the data. Further, most of the entries in the output matrix are quantized, and can be succinctly represented by a bit vector, thus leading to much savings in space. We study random submatrices of a large matrix A. We show how to approximately compute A from its random submatrix of the smallest possible size O(rlog r) with a small error in the spectral norm, where r e VAV2F VAV22 is the numerical rank of A. The numerical rank is always bounded by, and is a stable relaxation of, the rank of A. This yields an asymptotically optimal guarantee in an algorithm for computing low-rank approximations of A. We also prove asymptotically optimal estimates on the spectral norm and the cut-norm of random submatrices of A. The result for the cut-norm yields a slight improvement on the best-known sample complexity for an approximation algorithm for MAX-2CSP problems. We use methods of Probability in Banach spaces, in particular the law of large numbers for operator-valued random variables. Given an m ? n matrix A and an n ? p matrix B, we present 2 simple and intuitive algorithms to compute an approximation P to the product A ? B, with provable bounds for the norm of the "error matrix" P - A ? B. Both algorithms run in 0(mp+mn+np) time. In both algorithms, we randomly pick s = 0(1) columns of A to form an m ? s matrix S and the corresponding rows of B to form an s ? p matrix R. After scaling the columns of S and the rows of R, we multiply them together to obtain our approximation P. The choice of the probability distribution we use for picking the columns of A and the scaling are the crucial features which enable us to fairly elementary proofs of the error bounds. Our first algorithm can be implemented without storing the matrices A and B in Random Access Memory, provided we can make two passes through the matrices (stored in external memory). The second algorithm has a smaller bound on the 2-norm of the error matrix, but requires storage of A and B in RAM. We also present a fast algorithm that "describes" P as a sum of rank one matrices if B = AT. We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy e in time linear in their number of non-zeros and log (κ f (A) e), where κ f (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.