Abstract
Iterative sparsification algorithms, such as the Batson-Spielman-Srivastava (BSS) algorithm, are essential for producing optimal linear-sized spectral sparsifiers. However, these methods have historically been limited by high computational costs, specifically an $\Omega(d^4)$ time complexity barrier for deterministic versions. This paper introduces a general framework that leverages efficient inner product search data structures to accelerate the iterative selection process. By reframing vector selection as a data structure query problem, the authors achieve a deterministic running time of $O(d^{\omega+1})$, where $\omega$ is the exponent of matrix multiplication, significantly improving upon prior state-of-the-art results.
Introduction
Sparsification is the process of reducing a large, complex object—such as a graph or a high-dimensional matrix—into a much smaller "sparse" version that preserves its essential spectral properties. In spectral sparsification, the goal is to find a small subset of rows from a matrix $V$ such that the eigenvalues of the original matrix are maintained.
The gold standard for this task is the BSS algorithm, which produces optimal sparsifiers. However, BSS is computationally expensive because it requires searching through all $m$ original vectors at each step to satisfy specific spectral constraints. For years, deterministic implementations were stuck at a computational cost of $\Omega(d^4)$, making them impractical for large-scale datasets. The primary challenge is twofold: efficiently finding the correct vector in each iteration and ensuring search accuracy when queries are adaptive (i.e., when the search at step $t+1$ depends on the result of step $t$).
Methods
The authors address the bottleneck of iterative search by developing three specialized data structure tools:
- Positive Inner Product Search (PIPS): A deterministic search tree that stores sums of outer products, allowing the algorithm to find a suitable vector $v_i$ in $O(d^2 \log m)$ time instead of scanning all $m$ vectors.
- Minimum Inner Product Search (Min-IPS): Used for discrepancy problems like Kadison-Singer, this tool utilizes a duality between Min-IP and Approximate Furthest Neighbor (AFN) search.
- TensorSparse Sketching: A new sketching matrix designed for tensor products ($v \otimes v$). This enables the use of dimensionality reduction (Johnson-Lindenstrauss) while remaining robust against "adaptive adversaries"—scenarios where query choices are non-oblivious.
By integrating these data structures into the BSS framework, the authors transform the brute-force search of each iteration into an efficient query process.
Key Results and Insights
The most significant insight of this work is that the bottleneck in sparsification is not the spectral theory itself, but the search for the next vector. By treating the vector set as a database to be queried, the authors unlock standard acceleration techniques from computational geometry.
As shown in the comparison below, the proposed framework (Theorem 3.1) achieves a running time of $O(d^{\omega+1})$ for deterministic construction. This represents a massive improvement over the previous $O(d^4)$ standard.
Beyond spectral sparsification, the authors provided the first fast algorithms for the one-sided Kadison-Singer discrepancy problem and accelerated the "swapping process" used in rounding algorithms for experimental design.
Limitations and Future Work
While $O(d^{\omega+1})$ is theoretically superior, the practical speedup is tied to the efficiency of fast matrix multiplication, where constant factors can be large. Additionally, while this work breaks the deterministic barrier, randomized algorithms using SDP solvers may still be faster in specific graph-based scenarios. The authors suggest that this framework could be extended to other iterative optimization problems, such as sum-of-PSD-matrix sparsification, which remains an open area for further testing.
Summary updated