Matching works

1 work

math.OC — Optimization and Control

Linear-size sparsification from self-concordant barriers

Contributed by Yilin Liu

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.

Primarily AI-generated textHuman understanding: no partscone sparsificationconic liftshyperbolicity conesnuclear normpartial coloringself-concordant barriers
Nov 20, 20268 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations