Computer Science – Data Structures and Algorithms
Scientific paper
2011-03-14
Computer Science
Data Structures and Algorithms
16 pages, simplified proof and corrected acknowledging of prior work in (current) Section 4
Scientific paper
In this paper, we generalize Spencer's hyperbolic cosine algorithm to the matrix-valued setting. We apply the proposed algorithm to several problems by analyzing its computational efficiency under two special cases of matrices; one in which the matrices have a group structure and an other in which they have rank-one. As an application of the former case, we present a deterministic algorithm that, given the multiplication table of a finite group of size $n$, it constructs an expanding Cayley graph of logarithmic degree in near-optimal O(n^2 log^3 n) time. For the latter case, we present a fast deterministic algorithm for spectral sparsification of positive semi-definite matrices, which implies an improved deterministic algorithm for spectral graph sparsification of dense graphs. In addition, we give an elementary connection between spectral sparsification of positive semi-definite matrices and element-wise matrix sparsification. As a consequence, we obtain improved element-wise sparsification algorithms for diagonally dominant-like matrices.
No associations
LandOfFree
A Matrix Hyperbolic Cosine Algorithm and Applications 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 A Matrix Hyperbolic Cosine Algorithm and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Matrix Hyperbolic Cosine Algorithm and Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-138237