\documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage{lmodern,amsmath,amssymb,amsthm} \usepackage[a4paper,margin=28mm]{geometry} \usepackage{microtype,xcolor} \usepackage[unicode,colorlinks=true,linkcolor=blue!55!black,citecolor=blue!55!black,urlcolor=blue!55!black]{hyperref} \hypersetup{pdftitle={Linear-size sparsification from self-concordant barriers}, pdfauthor={Yilin Liu}, pdfkeywords={cone sparsification, self-concordant barriers, hyperbolicity cones, partial coloring, conic lifts, nuclear norm}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newcommand{\R}{\mathbb R} \newcommand{\Prb}{\mathbb P} \newcommand{\E}{\mathbb E} \newcommand{\one}{\mathbf 1} \newcommand{\Int}{\operatorname{int}} \newcommand{\ri}{\operatorname{ri}} \newcommand{\supp}{\operatorname{supp}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\spn}{\operatorname{span}} \newcommand{\vol}{\operatorname{vol}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\diag}{\operatorname{diag}} \newcommand{\spars}{\operatorname{sp}} \newcommand{\PSD}{\mathbb S_+} \setlength{\emergencystretch}{1em} \clubpenalty=10000 \widowpenalty=10000 \displaywidowpenalty=10000 \allowdisplaybreaks[1] \title{Linear-size sparsification\\from self-concordant barriers} \author{Yilin Liu} \date{19 November 2026} \begin{document} \makeatletter \begin{center} {\LARGE\bfseries\parbox{.99\linewidth}{\centering\@title}\par} \vspace{.8em} {\large\@author\par} \vspace{.4em} {\small\@date\par} \end{center} \makeatother \begin{abstract} A \(\theta\)-self-concordant barrier gives \(\varepsilon\)-sparsifiers with \(O(\theta/\varepsilon^2+r)\) summands and \(r\) 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. \end{abstract} \section{Introduction} For a closed convex cone \(K\) in a finite-dimensional real space, write \(x\preceq_K y\) if \(y-x\in K\). Given \(v_i\in K\) with sum \(e\) and \(0<\varepsilon<1\), an \(\varepsilon\)-sparsifier is a vector \(w\in\R_+^m\) satisfying \begin{equation}\label{eq:sandwich} (1-\varepsilon)e\preceq_K\sum_i w_i v_i \preceq_K(1+\varepsilon)e . \end{equation} Impose \(Aw=A\one\) for a real matrix \(A\) with \(m\) columns. Let \(\spars_K(\varepsilon,r)\) be the worst-case minimum support size over lists with \(e\in\ri K\) and \(\rank A\le r\). Write \(\spars_K(\varepsilon)=\spars_K(\varepsilon,0)\). Saunderson~\cite[Definitions~1.2--1.3]{Saunderson} takes the upper semicontinuous envelope of this pointwise bound. A proper cone is closed, convex, pointed and full-dimensional. On such a cone of positive dimension, a \(\theta\)-self-concordant barrier~\cite{NN,Nesterov} is a convex \(C^3\) function \(\phi:\Int K\to\R\) with positive definite Hessian, diverging to \(+\infty\) at the boundary and satisfying \begin{equation}\label{eq:scb} |D^3\phi(x)[h,h,h]|\le 2(D^2\phi(x)[h,h])^{3/2}, \qquad |D\phi(x)[h]|^2\le\theta D^2\phi(x)[h,h]. \end{equation} Differentiating logarithmic homogeneity \(\phi(tx)=\phi(x)-\nu\log t\) gives the gradient bound with \(\theta=\nu\). \begin{theorem}[Sparsification with exact linear constraints]\label{thm:main} Suppose \(K\) admits a \(\theta\)-self-concordant barrier. For each fixed \(\eta>0\) there is a constant \(C_\eta\) such that every list \(v_i\in K\) and matrix \(A\) of rank \(r\) admit an \(\varepsilon\)-sparsifier, \(0<\varepsilon<1\), with \[ Aw=A\one,\qquad |\supp w|\le \min\!\left\{\dim\spn\{(v_i,A_i):i\in[m]\}, \left\lceil (1+\eta)r+C_\eta\theta/\varepsilon^2\right\rceil\right\}, \] where \(A_i\) is column \(i\) of \(A\). A strong separation oracle for \(K\) and an upper bound in place of \(\theta\) suffice for a construction using \(O_\eta(\log(m+1))\) randomized polynomial-time partial colorings in the oracle model of Reis and Rothvoss~\cite{RRBal}. \end{theorem} Scaling \((v_i,A_i)\) by \(w_i^0\ge0\) extends the theorem to preserving \(Aw^0\) for sparsification of \(\sum_i w_i^0v_i\). \paragraph{Comparison with prior bounds.} Saunderson~\cite[Theorems~1.4--1.5]{Saunderson} gives support \(\lceil(4\nu/\varepsilon)^2\rceil\) for logarithmically homogeneous barriers and states \(\lceil4\nu/\varepsilon^2\rceil\) under pairwise self-concordance. Theorem~\ref{thm:main} answers his question on exact weight constraints~\cite[Section~9]{Saunderson}, extending spectral results~\cite{JRT,LWZ}. We extend Reis and Rothvoss's determinant-based positivity argument~\cite[Section~7]{RRL1}. Basu et al.~\cite{Basu} give \(O(d/\varepsilon^2)\) sparsifiers for Minkowski sums of centrally symmetric convex sets and sums of seminorms on \(\R^d\). \section{Positivity from a barrier} \begin{lemma}\label{lem:potential} For a \(\theta\)-self-concordant barrier \(\phi\), extend \(H=\exp(-\phi)\) by zero off \(\Int K\). Then \(H\) is continuous, nondecreasing in the cone order, convex along cone directions, and \(H(\rho x)\ge\rho^\theta H(x)\) for \(0<\rho\le1\). For \(x\in\Int K\) and \(u\in K\), \begin{equation}\label{eq:barrier-slopes} \sqrt{D^2\phi(x)[u,u]}\le -D\phi(x)[u], \qquad -D\phi(x)[x]\le\theta . \end{equation} \end{lemma} \begin{proof} For \(u\ne0\), let \(g(t)=\phi(x+tu)\), \(t\ge0\). If \(g'>0\) anywhere, convexity and \((1/g')'\le-1/\theta\) give a contradiction as \(t\to\infty\). Thus \(g'\le0\). Self-concordance gives \(g''(t)^{-1/2}\le g''(0)^{-1/2}+t\). Integrate the lower bound on \(g''\) over \([0,\infty)\) to get \(-g'(0)\ge\sqrt{g''(0)}\), which implies \(\theta\ge1\) by~\eqref{eq:scb}. Hence \[ DH(x)[u]\ge0,\qquad D^2H(x)[u,u]=H(x)\bigl(D\phi(x)[u]^2-D^2\phi(x)[u,u]\bigr)\ge0 . \] Along a cone direction, the interior occupies an upper interval. The boundary limit \(H=0\) preserves monotonicity and convexity under extension. For \(q(t)=-\frac{d}{dt}\phi(tx)>0\), integrate \((1/q)'\ge1/\theta\) from \(s\) to \(t\) and let \(s\downarrow0\) to get \(q(t)\le\theta/t\). Evaluate at \(t=1\) for the radial bound and integrate over \([\rho,1]\) for the scaling inequality. \end{proof} \begin{theorem}[Cone positivity]\label{thm:positivity} If \(K\) admits a \(\theta\)-self-concordant barrier, then for \(v_i\in K\) and independent symmetric real random variables \(X_i\), \[ \Prb\!\left[\sum_i X_i v_i\in K\right]\ge \exp(-2\theta). \] \end{theorem} \begin{proof} For uniform signs \(\sigma\), fix \(a\in\Int K\), \(\eta>0\), and set \(f(t)=H(\eta a+\sum_i t_i v_i)\). It is separately convex, with \(f(\one)>0\) and \(f(\rho t)\ge\rho^\theta f(t)\) for \(0<\rho<1\). As in~\cite[Lemma~18]{RRL1}, the Boolean noise operator satisfies \(T_\rho f(\sigma)\ge f(\rho\sigma)\). For \(p=1+\rho^2\) and \(b=\Prb[f(\sigma)>0]\), hypercontractivity and H\"older give \[ \rho^\theta\|f\|_2\le\|T_\rho f\|_2 \le\|f\|_p\le b^{1/p-1/2}\|f\|_2 . \] Let \(\rho\uparrow1\) to get \(b\ge e^{-2\theta}\). Then let \(\eta\downarrow0\), using closedness of \(K\) and the finite sign space. For general \(X_i\), condition on the magnitudes and apply the sign bound to \(|X_i|v_i\). \end{proof} \section{Support reduction in a subspace} For a list \(v_i\) of length \(m\) and \(e=\sum_i v_i\), set \[ Q_\delta=\left\{x\in[-1,1]^m: -\delta e\preceq_K\sum_i x_i v_i\preceq_K\delta e\right\}. \] Let \(\gamma_m\) be standard Gaussian measure on \(\R^m\). \begin{lemma}\label{lem:gaussian} There are absolute constants \(c_0,c_1>0\) such that, if \(0<\delta\le 1/2\) and \(m\ge c_0\theta/\delta^2\), then \(\gamma_m(Q_\delta)\ge e^{-c_1 m}\). \end{lemma} \begin{proof} Let \(B=\{x\in[-1,1]^m:\delta e+\sum_i x_i v_i\in K\}\). It contains \([-\delta,\delta]^m\). By Theorem~\ref{thm:positivity} and \(\delta e\in K\), every coordinate section occupies at least a fraction \(p=e^{-2\theta}\) of its cube. Reis and Rothvoss's symmetrization~\cite[Theorem~22]{RRL1} gives \(\vol(Q_\delta)=\vol(B\cap(-B))\ge 2^{-5m}\) when \(m\ge\log_2(1/p)/\delta^2\). The Gaussian density on the cube is at least \((2\pi)^{-m/2}e^{-m/2}\). \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] Start at \(w=\one\) and put \(\beta=\eta/(1+\eta)\). While \(S=\supp w\) has size \(b>(1+\eta)r+C_\eta\theta/\varepsilon^2\), form \(Q_\delta\) for \((w_i v_i)_{i\in S}\) with \(\delta=\sqrt{c_0\theta/b}\le1/2\). The subspace \(L=\ker(A_S\diag(w_S))\) has dimension at least \(\beta b\). Lemma~\ref{lem:gaussian} and subspace partial coloring~\cite[Theorem~6]{RRBal} give \[ x\in s_\eta Q_\delta\cap L\cap[-1,1]^S \] with at least \(\beta b/2\) saturated coordinates and constant \(s_\eta\). Choose the sign so that at least \(\beta b/4\) equal \(-1\). The update \(w_i\gets w_i(1+x_i)\) preserves \(Aw\), reduces the support by a factor at most \(1-\beta/4\), and multiplies the order bounds by \(1\pm s_\eta\delta\). Read backwards, the errors sum to at most \(\varepsilon/2\) for large enough \(C_\eta\), by the ratio \(\sqrt{1-\beta/4}\). The lower factors multiply to at least \(1-\varepsilon/2\), the upper to at most \(e^{\varepsilon/2}\le1+\varepsilon\). Conic Carath\'eodory on \((v_i,A_i)\) gives the dimension cap. Each \(Q_\delta\) separation uses a box check and two cone separation calls. Geometric support reduction gives the coloring count. \end{proof} \section{Transfer under lifts and limits} A closed \(K\)-lift of \(C\) is \(C=\overline{\pi(K\cap L)}\) for a subspace \(L\) and linear map \(\pi\). In a common ambient space, \(K_j\to K\) means each point in \(K\) is a limit of points \(x_j\in K_j\) and every subsequential limit from \(K_j\) lies in \(K\). \begin{theorem}\label{thm:transfer} The bound \(\spars_K(\varepsilon,r)\) holds for all finite sums in a closed convex cone \(K\). For a closed \(K\)-lift, \[ \spars_C(\varepsilon,r)\le\spars_K(\varepsilon,r),\qquad \spars_{C^*}(\varepsilon,r)\le\spars_{K^*}(\varepsilon,r). \] In particular, the primal bound transfers to every nonempty face. If \(K_j\to K\) and \(\varepsilon_j\to\varepsilon\in(0,1)\), then \[ \spars_K(\varepsilon,r)\le\liminf_j\spars_{K_j}(\varepsilon_j,r). \] \end{theorem} \begin{proof} Let \(C_j\to C\) and \(\varepsilon_j\to\varepsilon\). In the target list, replace summands in \(C\cap(-C)\) by zero, preserving the order inequalities. Choose \(v_i^{(j)}\in C_j\) tending to \(v_i\), with zero summands fixed. For \(\ell\in\ri C^*\) orthogonal projection and compactness give \[ \operatorname{dist}(\ell,C_j^*)= \max_{x\in C_j,\,\|x\|_2\le1}(-\langle\ell,x\rangle)\longrightarrow0 \] Choose \(\ell_j\in C_j^*\) converging to \(\ell\). For sparsifiers of size at most \(s\), pass to a subsequence of common support \(S\). For \(v_i\ne0\), the inequality \[ w_i^{(j)}\ell_j(v_i^{(j)})\le(1+\varepsilon_j)\ell_j\!\left(\sum_h v_h^{(j)}\right) \] and \(\ell(v_i)>0\) bound those weights. Take limits of the weights on nonzero terms and of both residuals. The remaining right-hand side of \(Aw=A\one\) is a limit in the finitely generated cone of columns \(A_i\) with \(i\in S\) and \(v_i=0\). That cone is closed, so the limiting weights can be completed on \(S\). For a boundary sum, perturb a nonzero summand by a vanishing multiple of a point in \(\ri K\). An all-zero list needs at most \(r\) weights by Carath\'eodory, and fixing \(r\) appended zero weights gives \(\spars_K(\varepsilon,r)\ge r+\spars_K(\varepsilon)\). For varying cones, use a subsequence realizing the lower limit. For a closed lift, choose approximants in \(\pi(K\cap L)\), using zero lifts for zero terms. Sparsify preimages in \(K\), project the two residuals in \(K\cap L\), and pass to the limit. A nonempty face is the section \(F=K\cap\spn F\). By bipolarity, \(C^*=(\pi^*)^{-1}D\) for \(D=\overline{K^*+L^\perp}\). The cone \(D\) is a closed lift of \(K^*\times L^\perp\), whose order is determined by \(K^*\). Sparsify in \(D\) and pull back via \(\pi^*\). \end{proof} The primal bound extends Saunderson's proper-lift transfer and gives his proposed face monotonicity~\cite[Proposition~1.8 and Section~9]{Saunderson}. Left limits in \(\varepsilon\) give the lift inequalities in his convention. \subsection{Hyperbolic lifts} For a positive integer \(d\) define \[ s_d(\varepsilon)= \left\lceil d\,\frac{(1+\sqrt{1-\varepsilon^2})^2}{\varepsilon^2}\right\rceil . \] \begin{theorem}\label{thm:hyper} A degree-\(d\) hyperbolicity cone has \(\spars_K(\varepsilon)\le s_d(\varepsilon)\). For interior sums, a deterministic construction uses \(O(m)\) vector additions and \(O(s_d(\varepsilon)\log(m+1))\) barrier derivative evaluations of orders one and two. \end{theorem} \begin{proof} Use the interior sum \(e\) as hyperbolicity direction, with \(p(e)>0\). For \(\phi=-\log p\), \(\Phi(z)=-D\phi(z)[e]\) sums the inverse root gaps. We use BSS barrier shifts~\cite{BSS} in Saunderson's cone formulation~\cite[Section~5]{Saunderson} with exact potential changes. Write \(x\prec_K y\) if \(y-x\in\Int K\). Set \(T=s_d(\varepsilon)\), \(\tau=\sqrt{d/T}\), and \(\Delta=(1+\tau)/(1-\tau)\). Start at \(x=0\) with \((\ell,u)=(-d/\tau,d\Delta/\tau)\). Maintain \(\ell e\prec_K x\prec_K u e\) and potentials \(\Phi(x-\ell e)\le\tau\), \(\Phi(ue-x)\le\tau/\Delta\). Shift \(\ell\) by \(1\) and \(u\) by \(\Delta\). The lower shift stays interior since each old root gap is at least \(1/\tau>1\). Set \(z_u=(u+\Delta)e-x\), \(z_\ell=x-(\ell+1)e\). Let \(D_u,D_\ell>0\) be the upper potential decrease and lower potential increase due to the shifts. Use the linear scores \[ U(v)=D^2\phi(z_u)[e,v]/D_u-D\phi(z_u)[v],\qquad L(v)=D^2\phi(z_\ell)[e,v]/D_\ell+D\phi(z_\ell)[v]. \] For \(v\in K\) outside lineality, \(U(v)\le1/\alpha\le L(v)\) makes \(x+\alpha v\) a valid update. At either slack \(z\), Helton--Vinnikov gives \(p(z+s e+t v)=p(z)\det(I+sE+tV)\) with \(E\succ0\), \(V\succeq0\)~\cite[Theorem~6.3]{Saunderson}. Testing \(z+\R v\) gives \(V=0\) exactly on lineality. Here \(\Phi(z)=\tr E\), \(D^2\phi(z)[e,v]=\tr(EV)\), and \(-D\phi(z)[v]=\tr V\). The upper score ensures \(\alpha\tr V<1\). Diagonalizing \(V\) bounds the potential increase at \(z-\alpha v\) by \(\alpha\tr(EV)/(1-\alpha\tr V)\) and the decrease at \(z+\alpha v\) below by \(\alpha\tr(EV)/(1+\alpha\tr V)\). The scores make these at most \(D_u\) and at least \(D_\ell\), respectively. The upper shift gives \(D_u\ge\Delta D^2\phi(z_u)[e,e]\) by comparing old and new inverse root gaps, so \(U(e)\le\Delta^{-1}+\tau/\Delta=1-\tau\). For the lower shift the old and new inverse gaps \(a_j,b_j\) satisfy \(b_j-a_j=a_jb_j\). Thus \[ \sum_j b_j^2-D_\ell =\sum_j a_jb_j^2 \ge \frac{D_\ell^2}{\sum_j a_j}\ge D_\ell^2 . \] Here \(D_\ell=\sum_j a_jb_j\) and \(\sum_j a_j\le\tau\), so \(L(e)\ge1+D_\ell-\sum_j b_j\ge1-\tau\). Store summand sums in a balanced binary tree. Since \(U(e)>0\) and \(L(e)\ge U(e)\), the pair \((L-U,U)\) is lexicographically positive at the root. Evaluate one child at each branch and take it if positive, or take the other child otherwise, by linearity. At the selected leaf, \(L(v_i)\ge U(v_i)>0\) since both scores vanish on lineality. Use \(\alpha=1/U(v_i)\). After \(T\) steps, \((\ell,u)=(T(1-\tau),\Delta T(1+\tau))\). Scale the weights by \(2/(\ell+u)\) for error \(2\tau/(1+\tau^2)\le\varepsilon\). Theorem~\ref{thm:transfer} covers boundary sums. \end{proof} \begin{corollary}\label{cor:dual} For a closed lift \(C\) of a degree-\(d\) hyperbolicity cone, \(\spars_C(\varepsilon)\le s_d(\varepsilon)\). Both \(\spars_C(\varepsilon,r)\) and \(\spars_{C^*}(\varepsilon,r)\) are \(O(d/\varepsilon^2+r)\). \end{corollary} \begin{proof} Theorems~\ref{thm:hyper} and~\ref{thm:transfer} give the first bound. On a complement of lineality, \(-\log p\) is a \(d\)-logarithmically homogeneous barrier~\cite[Theorem~2.4]{Saunderson}. The section preserves the order modulo lineality and its dual identifies with the original dual. Apply parameter-preserving barrier duality~\cite[Theorem~2.4.4]{NN} and Theorems~\ref{thm:main} and~\ref{thm:transfer}. \end{proof} Saunderson's corresponding support bound is \(\lceil4d/\varepsilon^2\rceil\) for hyperbolicity cones and their exact lifts~\cite[Corollaries~1.6 and~1.9]{Saunderson}. \begin{lemma}[Domination coefficients]\label{lem:domination} In a cone \(K\) with a \(\theta\)-self-concordant barrier, every list \(v_i\in K\) with sum \(e\) admits coefficients \(\lambda_i\in[0,1]\) satisfying \[ v_i\preceq_K\lambda_i e,\qquad \sum_i\lambda_i\le\theta . \] The same bound holds in the closure of any linear image of a section. \end{lemma} \begin{proof} For interior \(e\), take \(\lambda_i=\min\{1,-D\phi(e)[v_i]\}\). The Dikin ellipsoid~\cite[Theorem~5.1.5]{Nesterov}, \eqref{eq:barrier-slopes}, and \(v_i\preceq_K e\) give the domination. The coefficients sum to at most \(-D\phi(e)[e]\le\theta\). For boundary sums append a vanishing interior summand and use compactness. The inequalities restrict to sections, project linearly, and pass to closures by compactness of \([0,1]^m\). \end{proof} \section{Sharpness in positive semidefinite cones} When \(\lvert\sum_i w_i-m\rvert\le\varepsilon m\) and \(\varepsilon\le1/2\), Cauchy--Schwarz gives the support estimate \begin{equation}\label{eq:count} |\supp w|\ge \frac{(\sum_i w_i)^2}{\sum_i w_i^2} \ge\frac{m}{4(2+\|w-\one\|_2^2/m)} . \end{equation} \begin{proposition}\label{prop:psd} For \(k\ge1\), \(r\ge0\), and \(0<\varepsilon<1\), \[ \spars_{\PSD^k}(\varepsilon,r)= \Theta\bigl(r+\min\{k^2,k/\varepsilon^2\}\bigr). \] \end{proposition} \begin{proof} The determinant barrier and Theorem~\ref{thm:main} give the upper bound. For the lower bound take \(r=0\) and \(N=k+1\). Restrict the \(M=\binom N2\) complete-graph edge Laplacians to \(\one^\perp\), where they sum to \(NI\). The trace gives \(\lvert\sum_e w_e-M\rvert\le\varepsilon M\). Off-diagonal entries of the full Laplacians give \[ 2\sum_e(w_e-1)^2\le\|L_w-L_{\rm complete}\|_F^2 \le k N^2\varepsilon^2 . \] For \(\varepsilon\le1/2\), \eqref{eq:count} gives \(\Omega(k^2/(1+k\varepsilon^2))\). Otherwise the rank bound forces \(k\) summands. Fixed weights contribute the additive \(r\). \end{proof} \begin{theorem}[Sharp positivity exponent]\label{thm:sharp} Finite lists of rank-one matrices in \(\PSD^n\) attain positivity probability \(\exp(-(2+o(1))n)\) with independent standard Gaussian coefficients, and with independent uniform signs. \end{theorem} \begin{proof} Choose \(u\) uniformly in \(\{\pm1/\sqrt n\}^n\) with probability \(n/(n+2)\), and otherwise uniformly among the coordinate vectors. Then \[ \E[u_i u_j u_a u_b]= \frac{\delta_{ij}\delta_{ab}+\delta_{ia}\delta_{jb} +\delta_{ib}\delta_{ja}}{n(n+2)} . \] Assign each atom of mass \(p_u\) the matrix \(\sqrt{p_u}\,uu^{\mathsf T}\). With Gaussian coefficients, matching covariances gives law \((G+ZI)/\sqrt{n(n+2)}\) for the sum. Here \(G\) is from the Gaussian orthogonal ensemble with off-diagonal variance \(1\) and diagonal variance \(2\), and \(Z\) is independent standard Gaussian. Choose \(0<\eta<1\) and a nonnegative Lipschitz function \(f\) supported in \((-2,-2+\eta)\) with positive semicircle integral. The normalized trace \(n^{-1}\tr f(G/\sqrt n)\) has mean bounded away from zero by the semicircle law and is \(O(1/n)\)-Lipschitz by Hoffman--Wielandt. The trace vanishes when \(\lambda_{\min}(G)\ge-(2-\eta)\sqrt n\). Gaussian concentration~\cite{AGZ} bounds this event by \(e^{-c_\eta n^2}\), so \[ \Prb[G+ZI\succeq0]\le e^{-(2-\eta)^2n/2}+e^{-c_\eta n^2}. \] Let \(\eta\downarrow0\). Theorem~\ref{thm:positivity} for the determinant barrier gives the matching lower bound. For signs, replace each atom by \(t\) copies scaled by \(t^{-1/2}\). The central limit theorem gives convergence to the Gaussian sum. The Gaussian sum has a density and the boundary has measure zero, so a finite \(t\) achieves its probability within a factor of two. \end{proof} \section{Nuclear norm and quantum relative entropy} \subsection{Matrix-fractional cones and the nuclear norm} Let \(N_{n,k}=\{(X,t)\in\R^{n\times k}\times\R:\|X\|_*\le t\}\) be the nuclear-norm epigraph, where \(n\ge k\ge1\). \begin{theorem}\label{thm:nuclear} The minimum degree of a closed hyperbolic lift of \(N_{n,k}\) is \(k+1\). For \(0<\varepsilon<1\) and \(r\ge0\), \[ \spars_{N_{n,k}}(\varepsilon,r)= \Theta\bigl(r+\min\{nk,k/\varepsilon^2\}\bigr). \] For \(r=0\), let \(b\) be the dimension of the span of all matrix rows. A deterministic construction uses at most \(s_{b+1}(\varepsilon)\) summands. It requires exact spectral decomposition, \(O(s_{b+1}(\varepsilon)\log(m+1))\) directional barrier derivative evaluations, and polynomially many additional arithmetic operations. \end{theorem} For \(q\ge0\), the matrix-fractional cone \(M_{q,k}\) consists of \((a,P,X)\) with \(P\in\PSD^k\), \(X\in\R^{q\times k}\), and \begin{equation}\label{eq:fractional} a\ge \sup_{Y\in\R^{q\times k}} \{2\langle X,Y\rangle-\tr(PY^{\mathsf T}Y)\}. \end{equation} Completing the square gives \(\tr(XP^\dagger X^{\mathsf T})\) if \(X\ker P=0\), and \(+\infty\) otherwise. For \(Z\ker P=0\), the factorization \(Z=(ZP^{\dagger/2})P^{1/2}\) gives \begin{equation}\label{eq:nuclear-variational} 2\|Z\|_*\le \tr P+\tr(ZP^\dagger Z^{\mathsf T}). \end{equation} \begin{proof}[Lift and upper bounds] The polynomial \(p(a,P,X)=a\det P-\tr(X\operatorname{adj}(P)X^{\mathsf T})\) has degree \(k+1\). If \(P=U\diag(\lambda)U^{\mathsf T}\) and \(z_j=\|Xu_j\|_2\) for the columns \(u_j\) of \(U\), then \[ p(a+s,P+sI,X)= \det\begin{pmatrix}a+s&z^{\mathsf T}\\z&\diag(\lambda)+sI\end{pmatrix}. \] The roots are real and, by the Schur complement, nonpositive precisely on \(M_{q,k}\). This gives the hyperbolicity cone in direction \((1,I,0)\). By~\eqref{eq:nuclear-variational}, \((a,P,X)\mapsto(X,(a+\tr P)/2)\) maps \(M_{n,k}\) into \(N_{n,k}\). It is onto using \(P=(X^{\mathsf T}X)^{1/2}\), \(a=2t-\tr P\), for which \(\tr(XP^\dagger X^{\mathsf T})=\|X\|_*\). Corollary~\ref{cor:dual} and Carath\'eodory give the support bounds. \end{proof} \begin{proof}[Minimum lift degree] Take \(k\) summands \((u_j e_j^{\mathsf T},1)\) with coordinate vectors \(u_j\in\R^n\), \(e_j\in\R^k\), and \((0,\tau)\) for \(\tau>0\). They sum to \(([I_k;0],k+\tau)\). The scalar term needs coefficient \(1\). A matrix term needs \(\lambda(k+\tau)-1\ge 1-\lambda+(k-1)\lambda\), or \(\lambda\ge2/(2+\tau)\). Apply Lemma~\ref{lem:domination} to the source barrier modulo lineality. The degree is at least \(1+2k/(2+\tau)\), hence \(k+1\) as \(\tau\downarrow0\). This also proves optimality of the barrier parameter in~\cite[Section~7.3]{Saunderson}. \end{proof} \begin{proof}[Support lower bound] Put \(q=n-k\). For \(h>0\), let \(K_h\) be the preimage of \(N_{n,k}\) under the injective linear map \[ (a,P,X)\longmapsto \left(\begin{bmatrix}P\\hX\end{bmatrix},\,\tr P+h^2a/2\right). \] By~\eqref{eq:nuclear-variational}, \(M_{q,k}\subseteq K_h\). For convergent \((a_h,P_h,X_h)\in K_h\) as \(h\downarrow0\), the limit satisfies \(\|P\|_*\le\tr P\), hence \(P\succeq0\). Pair \([P_h;hX_h]\) with the isometry \([I;hY](I+h^2Y^{\mathsf T}Y)^{-1/2}\) for fixed \(Y\). This lower-bounds the nuclear norm by \[ \tr P_h+h^2\bigl(\langle X_h,Y\rangle -\tfrac12\tr(P_hY^{\mathsf T}Y)\bigr)+O(h^4). \] Thus \eqref{eq:fractional} holds in the limit. Theorem~\ref{thm:transfer} gives \(\spars_{M_{q,k}}(\varepsilon,r)\le\spars_{N_{n,k}}(\varepsilon,r)\). The section \(a=0,X=0\) gives the bound from Proposition~\ref{prop:psd}, which suffices when \(n<2k\) or \(\varepsilon>1/2\). Otherwise use \(kq\) summands \((1,e_je_j^{\mathsf T},e_a e_j^{\mathsf T})\) in \(M_{q,k}\), indexed by \(a\in[q]\), \(j\in[k]\). For weights \(W=(w_{aj})\) and all-ones \(J\), define \[ Z_\pm=\varepsilon J\pm(W-J),\qquad d_j^\pm=\sum_a (Z_\pm)_{aj}. \] The residuals \((\sum_j d_j^\pm,\diag(d_j^\pm),Z_\pm)\) give \(d_j^\pm\ge0\) and, by~\eqref{eq:fractional}, \(\sum_j\|(Z_\pm)_j\|_2^2/d_j^\pm\le\sum_j d_j^\pm\). A zero denominator forces a zero column and contributes zero. Since \(d_j^++d_j^-=2\varepsilon q\), weighted Cauchy--Schwarz gives \[ \frac{4\|W-J\|_F^2}{2\varepsilon q} \le\sum_{j,\pm}\frac{\|(Z_\pm)_j\|_2^2}{d_j^\pm} \le 2\varepsilon kq . \] The scalar residuals give \(\lvert\sum_{a,j}w_{aj}-kq\rvert\le\varepsilon kq\). Thus \eqref{eq:count} gives support at least \(kq/[4(2+\varepsilon^2q)]\). Fixed weights add \(r\). \end{proof} \begin{proof}[Deterministic construction] Let \((a,P,X)\) sum the square-root lifts. Restrict \(P_i\) and the domain of \(X_i\) to \(\operatorname{im}P\), of dimension \(b\). They annihilate \(\ker P\) since \(P_i\succeq0\) and \(X_i\ker P_i=0\). For \(b=0\), the scalar sum uses at most one summand. For \(a>\tr(XP^{-1}X^{\mathsf T})\), use Theorem~\ref{thm:hyper}. For equality, the nonnegative slacks in~\eqref{eq:fractional} sum to zero at \(Y=XP^{-1}\), so \(X_i=YP_i\) and \(a_i=\tr(YP_i Y^{\mathsf T})\). Sparsify \(P_i\) with the determinant barrier and apply this linear map. Project the result to \(N_{n,k}\). Polynomial interpolation and polarization give the directional evaluations by arithmetic. \end{proof} Saunderson's direct dual-barrier estimate for \(N_{n,k}\) is \(\lceil(4(k+1)/\varepsilon)^2\rceil\)~\cite[Section~7.3]{Saunderson}. \pagebreak \subsection{Quantum relative entropy} Let \(Q_n\) be the closure of the epigraph of \(\tr(X(\log X-\log Y))\) on positive definite symmetric \(n\times n\) matrices \(X,Y\). \begin{corollary}\label{cor:qre} The nonsemialgebraic cones \(Q_n,Q_n^*\) satisfy \(\spars_{Q_n}(\varepsilon,r),\spars_{Q_n^*}(\varepsilon,r) =\Theta(r+\min\{n^2,n/\varepsilon^2\})\) for \(0<\varepsilon<1\), \(r\ge0\). \end{corollary} \begin{proof} Positive semidefinite matrix coordinates and Klein's inequality \(t\ge\tr(X-Y)\) give pointedness. Fawzi and Saunderson's barrier~\cite[Corollary~1.7]{FS} restricts to a \((2n+1)\)-logarithmically homogeneous barrier. Theorem~\ref{thm:main} and barrier duality give the upper bounds. The section \((P,P,0)\) of \(Q_n\) is \(\PSD^n\) by closure. The section of \(Q_n^*\) at scalar coordinate zero is \(\PSD^n\times\PSD^n\), since \(Q_n\) contains all positive definite matrix pairs with suitable scalar coordinates. Proposition~\ref{prop:psd} and Theorem~\ref{thm:transfer} give the lower bounds. In the slice \(X=xI,Y=I,x>0\), the boundary is \(t=nx\log x\). A semialgebraic graph satisfies a nonzero polynomial equation, here \(\sum_d x^d q_d(\log x)=0\). Dividing by the lowest power with \(q_d\ne0\) and letting \(x\downarrow0\) gives a contradiction. Root signs and Tarski--Seidenberg give semialgebraicity for closed hyperbolic lifts and preserve it under duality. Bipolarity gives nonsemialgebraicity of \(Q_n^*\). \end{proof} \par\medskip\noindent\textbf{Acknowledgment.}\enspace The author used OpenAI models to formulate results, develop and review proofs, draft the manuscript, and implement finite checks. The source manuscript~\cite{AF} was prepared with GPT-6 Astra Pro. \begin{thebibliography}{12}\small\raggedright\setlength{\itemsep}{1pt} \bibitem{AGZ} G. W. Anderson, A. Guionnet and O. Zeitouni. \href{https://doi.org/10.1017/CBO9780511801334}{An introduction to random matrices}. Cambridge University Press, 2010. \bibitem{Basu} A. Basu, J. Brakensiek, Y. Chen, A. Putterman, V. Reis and Z. Zhang. \href{https://eccc.weizmann.ac.il/report/2026/132/}{Optimal sparsifiers for Minkowski sums and sums of seminorms}. ECCC TR26-132 (2026). \bibitem{BSS} J. Batson, D. A. Spielman and N. Srivastava. \href{https://doi.org/10.1137/090772873}{Twice-Ramanujan sparsifiers}. \emph{SIAM Journal on Computing} 41(6) (2012), 1704--1721. \bibitem{FS} H. Fawzi and J. Saunderson. \href{https://doi.org/10.1137/22M1500216}{Optimal self-concordant barriers for quantum relative entropies}. \emph{SIAM Journal on Optimization} 33(4) (2023), 2858--2884. \bibitem{JRT} A. Jambulapati, V. Reis and K. Tian. \href{https://doi.org/10.1137/1.9781611977912.186}{Linear-sized sparsifiers via near-linear time discrepancy theory}. \emph{SODA} (2024). \bibitem{LWZ} L. C. Lau, R. Wang and H. Zhou. \href{https://doi.org/10.1137/1.9781611978315.24}{Spectral sparsification by deterministic discrepancy walk}. \emph{SOSA} (2025). \bibitem{AF} Yilin Liu and GPT-6 Astra Pro. \href{https://github.com/icekylinx/algorithm-frontier/tree/77140c264e7cc9e7d2853a7cc86c76f4a7ad7d28/problems/conic-barrier-sparsification} {Sparsification from self-concordant barriers}. \emph{Algorithm Frontier}, source snapshot \texttt{77140c2} (2026). \bibitem{Nesterov} Y. Nesterov. \href{https://doi.org/10.1007/978-3-319-91578-4}{Lectures on convex optimization}. Springer, 2018. \bibitem{NN} Y. Nesterov and A. Nemirovskii. \href{https://doi.org/10.1137/1.9781611970791}{Interior-point polynomial algorithms in convex programming}. SIAM, 1994. \bibitem{RRBal} V. Reis and T. Rothvoss. \href{https://doi.org/10.1002/rsa.21113}{Vector balancing in Lebesgue spaces}. \emph{Random Structures \& Algorithms} 62(3) (2023), 667--688. \bibitem{RRL1} V. Reis and T. Rothvoss. \href{https://arxiv.org/abs/2606.28147v2}{Linear-size \(\ell_1\) sparsifiers}. arXiv:2606.28147v2 (2026). \bibitem{Saunderson} J. Saunderson. \href{https://arxiv.org/abs/2512.21812v1}{Sparsification of sums with respect to convex cones}. arXiv:2512.21812v1 (2025). \end{thebibliography} \end{document}