Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms

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, ldots, C_msubseteqmathbb{R}^n$ there is a choice of weights $lambda_1, dots , lambda_m in mathbb{R}_{geq 0}$ such that at most $O(n/{\epsilon }^2)$ of the weights are non-zero, and $$(1 – varepsilon)cdot Csubseteqsum_{i = 1}^mlambda_icdot C_isubseteq(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{nlog(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(nlog(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.