Linear-size sparsification from self-concordant barriers
Version 1 / Nov 20, 2026 / CC BY 4.0
Abstract
A -self-concordant barrier gives -sparsifiers with summands and 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
References
- G. W. Anderson, A. Guionnet and O. Zeitouni. An introduction to random matrices (https://doi.org/10.1017/CBO9780511801334). Cambridge University Press, 2010.DOI
- 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
- 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
- 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
- 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
- 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
- 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
- Y. Nesterov. Lectures on convex optimization (https://doi.org/10.1007/978-3-319-91578-4). Springer, 2018.DOI
- Y. Nesterov and A. Nemirovskii. Interior-point polynomial algorithms in convex programming (https://doi.org/10.1137/1.9781611970791). SIAM, 1994.DOI
- 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