2023/10/04 by Tasuku Soma, Soma, Tasuku, Kam Chuen Tung +3 · 2 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2310.02643
We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (ε, δ)-spectral sparsifier with multiplicative error ε and additive error δ that has O(ε-2 n log n log r log(1 + εW/δn)) hyperedges with high probability, where ε, δ∈ (0,1), n is the number of nodes, and W is the sum of edge weights. The space complexity of our algorithm is O(n2), while previous algorithms require the space complexity of Ω(m), where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.