Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms

Abstract

We extend the recent work of Reis and Rothvoss on sparsifying sums of ${\ell }_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\epsilon >0$ and centrally symmetric, convex sets $C_1,\dots ,C_m\subseteq {\mathbb{R}}^n$ there is a choice of weights ${\lambda }_1,\dots ,{\lambda }_m\in {\mathbb{R}}_{\ge 0}$ such that at most $O(n/{\epsilon }^2)$ of the weights are non-zero, and \[(1 - \varepsilon)\cdot C\subseteq\sum_{i = 1}^mλ_i\cdot C_i\subseteq(1 + \varepsilon)\cdot C,\] where $C:=C_1+\cdots +C_m$ refers to the Minkowski sums of the sets $C_1,\dots ,C_m$, and $\lambda \cdot C$ refers to the dilation of the set $C$. As immediate applications of this result, we obtain sparsifiers of size $O(n/{\epsilon }^2)$ for sparsifying sums of seminorms in $n$-dimensional space, improving on the $O\left(\frac{n\log (n/\epsilon )\cdot {\log }^{2.5}(n)}{{\epsilon }^2}\right)$ size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with $O(n/{\epsilon }^2)$ hyperedges, improving on the $O(n\log (n)/{\epsilon }^2)$ size sparsifiers from the work of Chen, Khanna, and Nagda (FOCS 2020). More generally, this also gives optimal size sparsifiers for sums of symmetric submodular functions.