Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices

DOI10.1142/S1793830921501093zbMath1482.05202arXiv2009.11133OpenAlexW3134472578MaRDI QIDQ5063290

Marcos Villagra, Sergio Mercado

Publication date: 17 March 2022

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

nonnegative matricessymmetric matricesspectral graph theoryspectral sparsification

Mathematics Subject Classification ID

General topics of discrete mathematics in relation to computer science (68R01) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Hermitian, skew-Hermitian, and related matrices (15B57)

Cites Work

• Unnamed Item
• Unnamed Item
• Quadratic programming with one negative eigenvalue is NP-hard
• Principal component analysis.
• A Matrix Hyperbolic Cosine Algorithm and Applications
• Spectral Sparsification of Graphs
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• A useful variant of the Davis–Kahan theorem for statisticians
• The Rotation of Eigenvectors by a Perturbation. III