Sparse sums of positive semidefinite matrices

DOI10.1145/2746241MaRDI QIDQ4962206zbMATH OpenOpenAlexFDO

Authors Nicholas J. A. Harvey, Cristiane M. Sato, Marcel Kenji De Carli Silva

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

derandomizationLaplacian matrixpositive semidefinite matricesrandomized algorithmsspectral sparsifiers

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Positive matrices and their generalizations; cones of matrices (15B48) Computational methods for sparse matrices (65F50) Randomized algorithms (68W20)

Abstract: Recently there has been much interest in "sparsifying" sums of rank one matrices: modifying the coefficients such that only a few are nonzero, while approximately preserving the matrix that results from the sum. Results of this sort have found applications in many different areas, including sparsifying graphs. In this paper we consider the more general problem of sparsifying sums of positive semidefinite matrices that have arbitrary rank. We give several algorithms for solving this problem. The first algorithm is based on the method of Batson, Spielman and Srivastava (2009). The second algorithm is based on the matrix multiplicative weights update method of Arora and Kale (2007). We also highlight an interesting connection between these two algorithms. Our algorithms have numerous applications. We show how they can be used to construct graph sparsifiers with auxiliary constraints, sparsifiers of hypergraphs, and sparse solutions to semidefinite programs.

Recommendations

• Twice-Ramanujan sparsifiers
• Faster spectral sparsification and numerical algorithms for SDD matrices
• Spectral sparsification of graphs
• An SDP-based algorithm for linear-sized spectral sparsification
• Improved spectral sparsification and numerical algorithms for SDD matrices

Cited in

(15)

• Toward a spectral theory of cellular sheaves
• A matrix hyperbolic cosine algorithm and applications
• Extracting a basis with fixed block inside a matrix
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• Hamiltonian sparsification and gap-simulation
• A Spectral Approach to Network Design
• ON RANDOM WEIGHTED SUM OF POSITIVE SEMI-DEFINITE MATRICES
• Sparsification of two-variable valued constraint satisfaction problems
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• A conjecture on spectral sparsification with respect to hyperbolicity cones
• On the cut-query complexity of approximating max-cut
• Cut sparsification and succinct representation of submodular hypergraphs
• Spectrahedral geometry of graph sparsifiers
• Approximation of the average of some random matrices

This page was built for publication: Sparse sums of positive semidefinite matrices

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