Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms

Abstract

We extend the recent work of Reis and Rothvoss on sparsifying sums of ℓ₁ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any ε > 0 and centrally symmetric, convex sets C₁, …, C_m⊆ℝⁿ there is a choice of weights λ₁, … , λ_m ∈ ℝ_{≥ 0} such that at most O(n / ε²) of the weights are non-zero, and (1 − ε)· C⊆∑_{i = 1}^mλ_i· C_i⊆(1 + ε)· C, where C:= C₁ + ⋯ + C_m refers to the Minkowski sums of the sets C₁, …, C_m, and λ· C refers to the dilation of the set C. As immediate applications of this result, we obtain sparsifiers of size O(n / ε²) for sparsifying sums of seminorms in n-dimensional space, improving on the O ( (n log(n/ε) · log^2.5(n))/ε² ) size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with O(n / ε²) hyperedges, improving on the O(n log(n) / ε²) 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.

Optimal Sparsifiers for Abelian Cayley Graphs
Arpon Basu, Pravesh K. Kothari, Raghu Meka +1
arXiv3 Nov 2026PreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Intersections and Minkowski Sums of Four-Corner Cantor Dusts with the Unit Circle
Jiangtao Li, Zhao Shen, Yufeng Wu
arXiv13 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Facet normals of Minkowski sums of staircase simplices
Yushan Qu, Jon Lee
arXiv27 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Minkowski sums with convex curves without pointwise Fourier decay
Alex Iosevich, Zhangze Li, Eyvindur Palsson +2
arXiv28 Aug 2026PreprintarXiv licenceFull textAnalysis & PDEs Geometry & topologyarXiv
Optimal Extrapolation Bounds for Sparse Fourier Sums
Ruizhe Zhang
arXiv13 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEs Numerical analysis & scientific computingarXiv

Cite

BibTeX RIS

BibTeX

@misc{basu2026optimal,
  title = {{Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms}},
  author = {Arpon Basu and Joshua Brakensiek and Yeyuan Chen and Aaron Putterman and Victor Reis and Zihan Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.20238},
  eprint = {2609.20238},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20238},
  note = {CC BY-NC-SA 4.0},
}

RIS

TY  - UNPB
TI  - Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms
AU  - Arpon Basu
AU  - Joshua Brakensiek
AU  - Yeyuan Chen
AU  - Aaron Putterman
AU  - Victor Reis
AU  - Zihan Zhang
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.20238
UR  - https://arxiv.org/abs/2609.20238
AB  - We extend the recent work of Reis and Rothvoss on sparsifying sums of ℓ_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 ε > 0 and centrally symmetric, convex sets C_1, …, C_m⊆ℝ^n there is a choice of weights λ_1, … , λ_m ∈ ℝ_≥ 0 such that at most O(n / ε^2) of the weights are non-zero, and (1 − ε)· C⊆∑_i = 1^mλ_i· C_i⊆(1 + ε)· C, where C:= C_1 + ⋯ + C_m refers to the Minkowski sums of the sets C_1, …, C_m, and λ· C refers to the dilation of the set C. As immediate applications of this result, we obtain sparsifiers of size O(n / ε^2) for sparsifying sums of seminorms in n-dimensional space, improving on the O ( (n log(n/ε) · log^2.5(n))/ε^2 ) size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with O(n / ε^2) hyperedges, improving on the O(n log(n) / ε^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.
ER  -

Abstract

Related

Cite