Directed Singular-Value Sparsifiers with O(n log n/ε²) Arcs

Given an unweighted directed graph, a sparsifier is a nonnegative reweighting of original arcs that preserves every in-degree and out-degree exactly. In this work, we study singular-value sparsifiers, which are generalizations of spectral sparsifiers. Singular-value sparsifiers find a number of applications in theoretical computer science, such as maintaining directed cuts and flows, speeding up directed Laplacian solvers, and sparsifying dense weight matrices in neural networks. Strong singular-value (SV) approximation supports sparse representations of directed random walks with guarantees that remain stable under products, and controls bilinear error in the left and right Schur-complement metrics. We prove that every unweighted directed graph on n vertices admits an ε-SV sparsifier with O(nlog(2n)/ε²) arcs, improving the O(nlog⁵ n/ε²) support bound of Lau, Wang, and Zhou. The sparsifier is a nonnegative reweighting of original arcs and preserves every in-degree and out-degree exactly. We also give a randomized construction with Õ(m+n) real-arithmetic running time, where m is the input support size, and the output has the same support bound and rational weights of polynomial bit length.