A matrix hyperbolic cosine algorithm and applications

DOI10.1007/978-3-642-31594-7_71MaRDI QIDQ2843307zbMATH OpenOpenAlexFDO

Authors Anastasios Zouzias

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.2793

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Recommendations

• Sparse sums of positive semidefinite matrices
• Twice-Ramanujan sparsifiers
• Spectral sparsification of graphs
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Faster spectral sparsification and numerical algorithms for SDD matrices

Cited in

(15)

• Upper and lower bounds for matrix discrepancy
• Efficient computation of the matrix cosine
• Constructing linear-sized spectral sparsification in almost-linear time
• Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices
• A general framework for graph sparsification
• New Algorithms for Computing the Matrix Sine and Cosine Separately or Simultaneously
• Vector balancing in Lebesgue spaces
• A conjecture on spectral sparsification with respect to hyperbolicity cones
• On the concentration of Gaussian Cayley matrices
• Spectral sparsification via bounded-independence sampling
• Better sparsifiers for directed Eulerian graphs
• Average-case matrix discrepancy: satisfiability bounds
• Weaver's discrepancy for Gaussian random vectors
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• Small-space spectral sparsification via bounded-independence sampling

This page was built for publication: A matrix hyperbolic cosine algorithm and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843307)