Linear-size sparsification from self-concordant barriers

Primarily AI-generated textHuman understanding: no partsmath.OC — Optimization and Controlcs.DS — Data Structures and Algorithms

Contributed by Yilin Liu ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

A θ\theta-self-concordant barrier gives ε\varepsilon-sparsifiers with O(θ/ε2+r)O(\theta / \varepsilon^2 + r) summands and rr exact linear weight constraints. The proof uses a cone-positivity bound with a sharp exponent. Constrained sparsification is monotone under closed lifts on both sides of duality, and jointly lower semicontinuous in the cone and error tolerance. We sharpen the deterministic support bound for hyperbolicity cones and determine the minimum closed hyperbolic lift degree of the nuclear-norm epigraph. We give matching support bounds for this epigraph, the quantum relative entropy cone, and its dual.

Provenance statement

The author used OpenAI models to formulate results, develop and review proofs, draft the manuscript, and implement finite checks. The source manuscript was prepared with GPT-6 Astra Pro.

References

  1. G. W. Anderson, A. Guionnet and O. Zeitouni. An introduction to random matrices (https://doi.org/10.1017/CBO9780511801334). Cambridge University Press, 2010.DOI
  2. A. Basu, J. Brakensiek, Y. Chen, A. Putterman, V. Reis and Z. Zhang. Optimal sparsifiers for Minkowski sums and sums of seminorms (https://eccc.weizmann.ac.il/report/2026/132/). ECCC TR26-132 (2026).link
  3. J. Batson, D. A. Spielman and N. Srivastava. Twice-Ramanujan sparsifiers (https://doi.org/10.1137/090772873). SIAM Journal on Computing 41(6) (2012), 1704--1721.DOI
  4. H. Fawzi and J. Saunderson. Optimal self-concordant barriers for quantum relative entropies (https://doi.org/10.1137/22M1500216). SIAM Journal on Optimization 33(4) (2023), 2858--2884.DOI
  5. A. Jambulapati, V. Reis and K. Tian. Linear-sized sparsifiers via near-linear time discrepancy theory (https://doi.org/10.1137/1.9781611977912.186). SODA (2024).DOI
  6. L. C. Lau, R. Wang and H. Zhou. Spectral sparsification by deterministic discrepancy walk (https://doi.org/10.1137/1.9781611978315.24). SOSA (2025).DOI
  7. Yilin Liu and GPT-6 Astra Pro. Sparsification from self-concordant barriers (https://github.com/icekylinx/algorithm-frontier/tree/77140c264e7cc9e7d2853a7cc86c76f4a7ad7d28/problems/conic-barrier-sparsification). Algorithm Frontier , source snapshot 77140c2 (2026).link
  8. Y. Nesterov. Lectures on convex optimization (https://doi.org/10.1007/978-3-319-91578-4). Springer, 2018.DOI
  9. Y. Nesterov and A. Nemirovskii. Interior-point polynomial algorithms in convex programming (https://doi.org/10.1137/1.9781611970791). SIAM, 1994.DOI
  10. V. Reis and T. Rothvoss. Vector balancing in Lebesgue spaces (https://doi.org/10.1002/rsa.21113). Random Structures & Algorithms 62(3) (2023), 667--688.DOI
Show all 12 referencesShow fewer references
  1. V. Reis and T. Rothvoss. https://arxiv.org/abs/2606.28147v2 Linear-size ℓ1\ell_1 sparsifiers . arXiv:2606.28147v2 (2026).arXiv
  2. J. Saunderson. Sparsification of sums with respect to convex cones (https://arxiv.org/abs/2512.21812v1). arXiv:2512.21812v1 (2025).arXiv

Version history

  1. v1 · 8 pagesSubmitted by Yilin LiuInitial depositCurrentNov 20, 2026