June 26, 2026
We prove that for any matrix \(A \in \mathbb{R}^{m \times n}\) and any \(\varepsilon\in (0, 1/2]\) there is a diagonal matrix \(D \in \mathbb{R}_{\geq 0}^{m \times m}\) with at most \(O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) nonzero entries so that \[(1-\varepsilon) \|Ax\|_1 \leq \|DAx\|_1 \leq (1+\varepsilon)\|Ax\|_1 \quad \forall x \in \mathbb{R}^n.\] In particular, for any zonotope \(Z \subseteq \mathbb{R}^{n}\) there exists a zonotope \(Z' \subseteq \mathbb{R}^{n}\) generated by at most \(O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) segments so that \((1-\varepsilon) Z \subseteq Z' \subseteq (1+\varepsilon) Z\). Previously, the best known bound was \(O(\frac{n}{\varepsilon^2} \log n)\) due to Talagrand (1990).
A classical problem in the intersection of convex geometry and the design of fast algorithms is the following: given a matrix \(A \in \mathbb{R}^{m \times n}\) and parameters \(p \geq 1\) and \(\varepsilon > 0\), can one replace \(A\) by a matrix \(\widetilde{A}\) with few rows so that \[\label{eq:LpApproximation} (1-\varepsilon) \|Ax\|_p \leq \|\widetilde{A}x\|_p \leq (1+\varepsilon) \|Ax\|_p \quad \forall x \in \mathbb{R}^n.\tag{1}\] All existing methods produce the matrix \(\widetilde{A}\) by selecting and rescaling existing rows of \(A\), i.e. \(\widetilde{A} = DA\) where \(D \in \mathbb{R}_{\geq 0}^{m \times m}\) is a diagonal matrix with few nonzero entries. This may be preferred in the underlying applications, and we also restrict to this choice.
The setting of \(p=1\) — which is the focus of this manuscript — has a natural geometric interpretation. For a compact convex set \(K \subseteq \mathbb{R}^n\), its support function is the function \(h_K : \mathbb{R}^n \to \mathbb{R}\) with \[h_K(x) = \max_{y \in K} \left<y,x\right>.\] A matrix \(A \in \mathbb{R}^{m \times n}\) generates a zonotope \(Z = \{ y^\top A : y \in [-1,1]^m \}\) which is a bounded centrally symmetric polyhedron. In other words, \(Z\) is the Minkowski sum of the \(m\) segments \([-a_i,a_i]\) where \(a_1,\ldots,a_m\) are the rows of \(A\). The support function of \(Z\) is simply \[h_Z(x) = \max_{y \in [-1,1]^m} \sum_{i=1}^m \left<y_ia_i,x\right> = \|Ax\|_1.\] Then our sparsification question 1 for \(p = 1\) is equivalent to asking whether for any zonotope \(Z \subseteq \mathbb{R}^n\), there exists a zonotope \(Z'\) with few segments so that \((1-\varepsilon) Z \subseteq Z' \subseteq (1+\varepsilon)Z\). Schechtman [1] proved that \(O(\frac{n^2}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) segments suffice. This was later improved by Bourgain, Lindenstrauss and Milman [2] to \(O(\frac{n}{\varepsilon^2} \log(\frac{n}{\varepsilon}) \cdot (\log n)^2)\) and then by Talagrand [3] to \(O(\frac{n}{\varepsilon^2} \log n)\) which remained the best known bound prior to this work. For the special case where \(Z = B^n_2\) (which is a zonoid), Figiel, Lindenstrauss and Milman [4] proved that \(O(\frac{n}{\varepsilon^2} \log(\tfrac{1}{\varepsilon}))\) segments suffice, and Gordon [5] improved this bound to \(O(\frac{n}{\varepsilon^2})\) segments. More work has been done in the regime where \(n\) is fixed and \(\varepsilon \to 0\), see also the extensive discussion in [2].
A related question that has been studied extensively in the theoretical computer science community is how to replace an undirected graph \(G = (V,E)\) on \(n\) vertices by a weighted graph \(G' = (V,E',w)\) with few edges that is a \((1+\varepsilon)\)-cut sparsifier, i.e. for every set \(S \subseteq V\), the weight of the cut is approximately preserved: \((1-\varepsilon) |\delta(S)| \leq w(\delta_{E'}(S)) \leq (1+\varepsilon) |\delta(S)|\). Motivated by designing faster algorithms for minimum \(s\)-\(t\) cuts, Benczúr and Karger [6] proved that \(O(\frac{n}{\varepsilon^2} \log n)\) edges suffice. The later works of Spielman and Teng [7] and Spielman and Srivastava [8] strengthened the notion of sparsification by showing that even the graph Laplacian can be approximately preserved using \(O(\frac{n}{\varepsilon^2} (\log n)^7)\) and \(O(\frac{n}{\varepsilon^2} \log n)\) edges, respectively. The breakthrough of Batson, Spielman and Srivastava [9], [10] finally provided a bound that is linear in \(n\). In fact, [9], [10] prove the more general statement that for any \(A \in \mathbb{R}^{m \times n}\) there is a diagonal matrix \(D \in \mathbb{R}_{\geq 0}^{m \times m}\) with support size \(O(\frac{n}{\varepsilon^2})\) so that \[(1-\varepsilon) \|Ax\|_2 \leq \|DAx\|_2 \leq (1+\varepsilon) \|Ax\|_2 \quad \forall x \in \mathbb{R}^n.\] This has a wide range of applications, such as an approximate John decomposition with only linearly many contact points, see Naor [11]. Most of the above results randomly sample rows (or edges) while fixing those that are deemed too important to be left to the randomness. Here the importance is determined for example using Lewis weights (as in [3], [12]) or using effective resistances (as in [8]). Crucially, the work of Batson, Spielman and Srivastava [9], [10] uses a deterministic polynomial-time procedure using a potential function instead. Now, let \(G = (V,E)\) be a graph with \(n = |V|\) vertices and \(|E| = m\) edges. Create a matrix \(A \in \{ -1,0,1\}^{m \times n}\) which for any edge \(e = \{ i,j\} \in E\) has a row \(e_i - e_j\) (with an arbitrary orientation of the sign); this is a signed node-edge incidence matrix of the graph. Then for any weight vector \(w \in \mathbb{R}_{\geq 0}^m\) and \(S \subseteq [n]\), one has \[\|\textrm{diag}(w) A \boldsymbol{1}_S\|_1 = w(\delta(S)).\] In other words, any \(L_1\)-sparsifier of the signed node-edge incidence matrix also gives a cut sparsifier. Andoni, Krauthgamer and Woodruff [13] prove that for any \(n\) and \(\varepsilon > \frac{1}{\sqrt{n}}\) there is an \(n\)-vertex graph \(G\) so that any \((1+\varepsilon)\)-approximate cut sparsifier has at least \(\Omega(\frac{n}{\varepsilon^2})\) edges. This also gives the same lower bound for the size of \(L_1\)-sparsifiers, at least when restricted to rescaling of existing rows.
We also mention a different type of sparsification that preserves the norm for pairs of points in a given discrete point set instead of all points in a subspace. The by now classical result by Johnson and Lindenstrauss [14] shows that for any finite set \(X \subseteq \mathbb{R}^d\) there is a matrix \(B\) with \(O(\frac{1}{\varepsilon^2}\log(|X|))\) rows so that \[(1-\varepsilon) \|x-y\|_2 \leq \|Bx - By\|_2 \leq (1+\varepsilon) \|x-y\|_2 \quad \forall x,y \in X.\] Much of the more recent work on this topic has focused on producing a matrix \(B\) that is particularly sparse [15], [16].
More recently, there has been renewed interest in sparsification for functions beyond \(\ell_p\) norms [17], [18].
Our main result is as follows:
Theorem 1. For any matrix \(A \in \mathbb{R}^{m \times n}\) and any \(\varepsilon \in (0, 1/2]\), there is a diagonal matrix \(D \in \mathbb{R}_{\geq 0}^{m \times m}\) with at most \(O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) nonzero entries so that \[(1-\varepsilon) \|Ax\|_1 \leq \|DAx\|_1 \leq (1+\varepsilon)\|Ax\|_1 \quad \forall x \in \mathbb{R}^n.\]
As discussed above, this theorem has a geometric interpretation:
Theorem 2. For any zonotope \(Z \subseteq \mathbb{R}^{n}\) and any \(\varepsilon \in (0, 1/2]\), there exists a zonotope \(Z'\) generated by at most \(O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) segments so that \({(1-\varepsilon) Z \subseteq Z' \subseteq (1+\varepsilon) Z}\).
In fact, there is a third interpretation. Let \(\ell_1\) be the infinite-dimensional Banach space of all sequences \((x_k)_{k \in \mathbb{N}}\) with \(\|x\|_1 < \infty\), equipped with the \(\| \cdot \|_1\)-norm. Moreover, let \(\ell_1^N = (\mathbb{R}^N,\| \cdot \|_1)\) which is a Banach space of dimension \(N\).
Theorem 3. Let \(\varepsilon \in (0,1/2]\) and let \(X\) be an \(n\)-dimensional subspace of \(\ell_1\). Then there exists an \(n\)-dimensional subspace \(Y\) of \(\ell_1^N\) with \(N \leq O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) so that \(d_{BM}(X,Y) \leq 1+\varepsilon\).
Here \(d_{BM}(X,Y)\) denotes the Banach-Mazur distance between \(X\) and \(Y\). These results affirmatively answer a 1986 question of Schechtman [1]; see also [19]. We should also point out that our results do not come with a polynomial-time construction. This might be somewhat natural, as given two zonotopes \(Z_1\) and \(Z_2\), both specified by their generators, it is \({\boldsymbol{c}oNP}\)-complete to decide if \(Z_1 \subseteq Z_2\) [20]. However, the matrix \(D\) in Theorem 1 can be computed in time \(2^m\) times a polynomial in the encoding length of \(A\). The same holds true for the zonotope \(Z'\) in Theorem 2 where \(A\) is the matrix whose rows generate \(Z\).
Our framework also yields an alternative proof for the existence of linear-size spectral sparsifiers:
Theorem 4. For any matrix \(A \in \mathbb{R}^{m \times n}\) and \(\varepsilon \in (0, 1/2]\), there is a diagonal matrix \(D \in \mathbb{R}_{\geq 0}^{m \times m}\) with at most \(O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) nonzero entries so that \[(1-\varepsilon) \|Ax\|_2 \leq \|DAx\|_2 \leq (1+\varepsilon)\|Ax\|_2 \quad \forall x \in \mathbb{R}^n.\] The weights can be computed in polynomial time.
We recall that \(O(\frac{n}{\varepsilon^2})\) is known [9], [10]; see also [21] and [22].
In order to prove our results, we switch to the zonotope view and work towards a proof of Theorem 2; the equivalent statements of Theorem 1 and Theorem 3 then follow. We fix a matrix \(A \in \mathbb{R}^{m \times n}\) with rows \(a_1,\ldots,a_m\) and the corresponding zonotope \(Z = \{ \sum_{i=1}^m y_ia_i : |y_i| \leq 1\; \forall i \in [m]\}\). For a vector \(t \in \mathbb{R}_{\geq 0}^m\) we also write \(Z_t := \{ \sum_{i=1}^m y_ia_i : |y_i| \leq t_i \; \forall i \in [m] \}\) as the zonotope where the \(i\)th segment is scaled by \(t_i\).
The first crucial part of our proof strategy is to show that for a uniformly random vector \(x \sim [-1,1]^m\) one has \[\label{eq:Overview1} \mathbb{P}[Z_{\boldsymbol{1}+x} \subseteq (1+\varepsilon) Z] \geq \frac{\mathrm{Vol}_n(\varepsilon Z)}{\mathrm{Vol}_n((1+\varepsilon) Z)} \geq (\varepsilon/2)^n\tag{2}\] if, say, \(0<\varepsilon \leq \frac{1}{2}\). This argument — which we present in Section 3 — is based on the insight that the volume is convex when subtracting a single segment. The bound from 2 implies that the convex set \[K := \{ x \in [-1,1]^m : Z_{\boldsymbol{1}+x} \subseteq (1+\varepsilon) Z \}\] of sign changes that would respect the upper inclusion is sufficiently large. But in order to also guarantee lower bounds in the form \((1-\varepsilon) Z \subseteq Z_{\boldsymbol{1}+x}\) we need to prove that the symmetrizer \(K \cap -K\) is still sufficiently large. While \(K\) is highly asymmetric, all coordinate sections of \(K\) are still sufficiently large. With a careful convex geometric argument we prove in Section 4 that this property suffices to derive that \(\mathrm{Vol}_m(K \cap -K) \geq 2^{-\Theta(m)}\) as long as \(m \geq \Omega(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\).
The remainder of the argument is mostly standard. As \(K \cap -K\) is large enough, we obtain that for some constant \(s>0\), there is a vector \(x \in s(K \cap -K)\) with \(x_i = -1\) for at least a quarter of the coordinates. Then replacing \(Z\) by \(Z' := Z_{\boldsymbol{1}+x}\) reduces the number of segments by at least a quarter while \((1-s\varepsilon) Z \subseteq Z' \subseteq (1+s\varepsilon) Z\). We repeat the process until the target number of segments is reached; here the admissible value of \(\varepsilon\) that makes the argument work increases geometrically.
For a convex body \(K \subseteq \mathbb{R}^m\), the barycenter is the point \(\mathop{\mathbb{E}}_{x \sim K}[x]\). We recall the following seminal result:
Theorem 5 (Milman, Pajor [23]). For any convex body \(K \subseteq \mathbb{R}^m\) with barycenter \(z\) one has \(\mathrm{Vol}_m((K-z) \cap (-(K-z))) \geq 2^{-m}\mathrm{Vol}_m(K)\).
The following is a variant of Brunn’s concavity principle which can be derived either via the Brunn-Minkowski Theorem or via Steiner symmetrization, see [24] or [25]:
Theorem 6 (Brunn’s concavity principle). Let \(K,L \subseteq \mathbb{R}^m\) be convex sets. Then the function \(F(x) := \mathrm{Vol}_m(K \cap (x+L))^{1/m}\) is concave on its support.
The following is a minor modification of [26]:
Theorem 7. For any \(c > 0\) there is a \(s := s(c) > 0\) so that the following holds: for any symmetric convex body \(K \subseteq [-1,1]^m\) with \(\mathrm{Vol}_m(K) \geq c^m\), there is an \(x \in sK \cap [-1,1]^m\) and \(|\{ j \in [m] : |x_j| = 1\}| \geq \frac{m}{2}\). Moreover, \(x\) can be found in randomized polynomial time, given a separation oracle for \(K\).
To be exact, [26] uses Gaussian measure instead of volume. But for any set \(K \subseteq [-1,1]^m\) we have \(\gamma_m(K)/\mathrm{Vol}_m(K) \in [(2\pi e)^{-m/2}, (2\pi)^{-m/2}]\) which only results in a change of the constant \(c\).
We use the following variant of Hoeffding’s inequality. For the sake of completeness, its short proof can be found in Appendix 8.
Lemma 1. Let \(v \in \mathbb{R}^m\) and \(x \sim [-1,1]^m\) uniformly. Then \(\mathbb{P}[\langle v, x \rangle > \sqrt{\lambda} \|v\|_2] \le 2^{-2\lambda}\) for any \(\lambda \ge 0\).
Let \(\Omega \subseteq \mathbb{R}\) be a convex set. We say that a function \(f : \Omega^m \to \mathbb{R}\) is separately convex if for any \(t \in \Omega^m\) and \(j \in [m]\), the function \(s \mapsto f(t + se_j)\) is convex. We note that this does not imply that \(f\) is convex. For example, all multilinear functions such as \(f(x) = -x_1\cdot x_2\) are separately convex but not necessarily convex. But separate convexity is still helpful:
Lemma 2 (Jensen’s Inequality). Let \(f : \Omega^m \to \mathbb{R}\) be a separately convex function and let \(X \in \Omega^m\) be a random vector with independent coordinates. Then \[\mathop{\mathbb{E}}[f(X)] \geq f(\mathop{\mathbb{E}}[X])\]
Proof. We prove this by induction over \(m\). For \(m = 1\) this is just convexity, so assume it holds for \(m-1\) for some \(m > 1\) and write \(X = (X_1,\bar{X})\). Then \[\mathop{\mathbb{E}}[f(X)] = \mathop{\mathbb{E}}_{\bar{X}}[\mathop{\mathbb{E}}_{X_1}[f(X_1,\bar{X})]] \stackrel{\textrm{sep.}}{\geq} \mathop{\mathbb{E}}_{\bar{X}}[f(\mathop{\mathbb{E}}[X_1],\bar{X})] \stackrel{\textrm{induction}}{\geq} f(\mathop{\mathbb{E}}[X_1],\mathop{\mathbb{E}}[\bar{X}]) = f(\mathop{\mathbb{E}}[X])\] using independence and the fact that restrictions of \(f\) are still separately convex. ◻
The goal of this section is to derive a lower bound on the probability that a random zonotope \(Z_{X}\) is contained in a given convex body \(K\) where \(X\) is any non-negative random vector with independent coordinates.
For two sets \(K,L \subseteq \mathbb{R}^n\), their Minkowski addition is \(K + L = \{ x + y \mid x \in K, y \in L\}\). This operation has a conceptual inverse, first introduced by Hadwiger [27] and independently by Pontryagin [28].
Definition 1. For compact convex sets \(K,L \subseteq \mathbb{R}^n\) with \(L\) nonempty, the Minkowski subtraction is the set \[K \ominus L := \{ x \in \mathbb{R}^n : x + L \subseteq K \}.\]
We summarize a few of its properties, most of which can be found in the contemporary book of Schneider [29].
Proposition 8. Consider compact convex sets \(K,L,M \subseteq \mathbb{R}^n\) with \(L,M\) nonempty.
One has \(K \ominus L = \bigcap_{y \in L} (K-y)\).
\(K \ominus L\) is convex.
\(K \ominus L \neq \emptyset \iff L \subseteq K\) for symmetric \(K, L\).
\((K \ominus L) \ominus M = K \ominus (L + M)\) (associativity).
\(K \ominus \lambda K = (1-\lambda)K\) for \(0 \leq \lambda \leq 1\).
Proof. One has \(x \in K \ominus L\) if and only if \(x + y \in K\) for every \(y \in L\), so \(K \ominus L = \bigcap_{y \in L} (K-y)\), and any intersection of convex sets must be convex itself. This proves (A) and (B). For (C) we use that if \(L \subseteq K\) then \(\boldsymbol{0} \in K \ominus L\) and conversely for symmetric \(K,L\), \(K \ominus L\) is also symmetric, so \(\boldsymbol{0} \in K \ominus L\) if it is nonempty, which implies \(L \subseteq K\). For (D) we can write \[\begin{align} (K \ominus L) \ominus M &=& \{x \in \mathbb{R}^n : (x + M) + L \subseteq K\} \\ &=& \{x \in \mathbb{R}^n : x + (M+L) \subseteq K\} = K \ominus (L + M). \end{align}\] Finally we prove (E). If \(x \in (1-\lambda)K\), then \(x + \lambda K \subseteq K\) by convexity, so \((1 - \lambda) K \subseteq K \ominus \lambda K\). If \(K = \emptyset\) then clearly \(K \ominus \lambda K = \emptyset\). Otherwise, suppose that \(x \in K \ominus \lambda K\), so that \(x + \lambda K \subseteq K\), and choose a point \(x_0 \in K\). Define a sequence of points \(x_{k+1} := x + \lambda x_k\) for \(k \ge 0\) so that by induction \(x_k \in K\) for all \(k \in \mathbb{N}\). If \(\lambda = 1\), then since \(x_k = x_0 + kx \in K\) for all \(k \in \mathbb{N}\) and \(K\) is bounded, \(x = 0\). Otherwise, \((1-\lambda)^{-1} x = \lim_{k \to \infty} x_k \in K\) since \(K\) is closed, so \(x \in (1-\lambda) K\). ◻
Here is a crucial property:
Lemma 3. Let \(K \subseteq \mathbb{R}^n\) be a compact convex set and let \(v \in \mathbb{R}^n\). Let \(f(s) := \mathrm{Vol}_n(K \ominus s[-v,v])\). Then the function \(f\) is convex on \(\mathbb{R}_{\ge 0}\).
Proof. If \(v=\boldsymbol{0}\), \(f\) is constant. Otherwise, consider a vector \(z \in v^{\perp}\) and consider the line \(z + \mathbb{R}v\). Say that the length of the intersection with \(K\) is \(\ell(z)\). The same line intersected with \(K \ominus s [-v,v]\) has length \((\ell(z) - 2s\|v\|_2)_+\) where \((t)_+ = \max\{ t,0\}\), and for each fixed \(z\), the function \(s \mapsto (\ell(z)-2s\|v\|_2)_+\) is convex on \(\mathbb{R}_{\ge 0}\). Then \[f(s) = \mathrm{Vol}_n(K \ominus s[-v,v]) = \int_{v^{\perp}} (\ell(z)-2s\|v\|_2)_+ dz\] is an average of convex functions which is again convex on \([0,\infty)\). ◻
As before, for a matrix \(A \in \mathbb{R}^{m \times n}\) with rows \(a_1, \dots, a_m\) and \(t \in \mathbb{R}_{\geq 0}^m\) we abbreviate the zonotope \(Z_t = \{ \sum_{i=1}^m y_ia_i : |y_i| \leq t_i \; \forall i \in [m]\}\).
Lemma 4. Let \(K \subseteq \mathbb{R}^n\) be a convex body and \(Z = \sum_{j \in [m]} [-a_j, a_j]\subseteq \mathbb{R}^n\) be a zonotope. Then \(f : \mathbb{R}_{\ge 0}^m \to \mathbb{R}_{\geq 0}\) with \(f(t) := \mathrm{Vol}_n(K \ominus Z_t)\) is separately convex.
Proof. For any \(k \in [m]\), we have \[K \ominus Z_t = \Big(K \ominus \sum_{j \in [m]\setminus \{k\}} t_j [-a_j, a_j]\Big) \ominus t_k [-a_k,a_k]\] by Proposition 8(D), so the claim follows from Lemma 3. ◻
Now we have everything in place to conclude the main result of this section:
Theorem 9. Let \(K \subseteq \mathbb{R}^n\) be a symmetric convex body and \(Z \subseteq \mathbb{R}^n\) be a zonotope generated by \(m\) segments. Let \(X \in \mathbb{R}_{\ge 0}^m\) be a random vector with independent coordinates. Then \[\mathbb{P}[Z_X \subseteq K] \geq \frac{\mathrm{Vol}_n(K \ominus Z_{\mathop{\mathbb{E}}[X]})}{\mathrm{Vol}_n(K)}\]
Proof. We abbreviate \(f(t) := \mathrm{Vol}_n(K \ominus Z_t)\) for \(t \in \mathbb{R}_{\geq 0}^m\) which is a separately convex function by Lemma 4. Then \[\begin{align} \mathbb{P}[Z_X \subseteq K] \cdot \mathrm{Vol}_n(K) &\geq& \mathbb{P}[\mathrm{Vol}_n(K \ominus Z_X)>0] \cdot \mathrm{Vol}_n(K) \\ &\geq& \mathop{\mathbb{E}}_X[\mathrm{Vol}_n(K \ominus Z_X)] \\ &\geq& \mathrm{Vol}_n(K \ominus Z_{\mathop{\mathbb{E}}[X]}), \end{align}\] using Lemma 2. Moreover \(\mathrm{Vol}_n(K \ominus Z_X)>0\) implies that \(K \ominus Z_X \neq \emptyset \iff Z_X \subseteq K\). Rearranging finishes the proof. ◻
Consider a set \(K \subseteq \mathbb{R}^m\) and a subset \(S \subseteq [m]\) of coordinates. We denote by \(K_S := \{ x' \in \mathbb{R}^S : (x',\mathbf{0}) \in K\}\) the intersection of \(K\) with the coordinate subspace corresponding to \(S\), where \(\mathbf{0} \in \mathbb{R}^{[m] \setminus S}\).
Theorem 10. Let \(Z \subseteq \mathbb{R}^n\) be a zonotope generated by the rows of \(A \in \mathbb{R}^{m \times n}\) and let \(\varepsilon\in (0,1/2]\). Then the set \[K := \{x \in [-1,1]^m : Z_{\mathbf{1}+x} \subseteq (1+\varepsilon)Z\}\] contains \([-\varepsilon,\varepsilon]^m\), is convex and \(\mathrm{Vol}_S (K_S) \ge (\varepsilon/2)^n 2^{|S|}\) for every \(S \subseteq [m]\).
Proof. We may equivalently write \[\label{eq:KinInequalityForm} K = \Big\{x \in [-1,1]^m : \sum_{i=1}^m x_i \cdot |\langle a_i, y \rangle| \le \varepsilon\sum_{i =1}^m |\langle a_i, y \rangle| \;\forall y \in \mathbb{R}^n\Big\},\tag{3}\] which means that \(K \supseteq [-\varepsilon,\varepsilon]^m\) is the intersection of halfspaces and therefore convex. Next, we may assume that \(Z\) is full-dimensional (for example by adding \([-\delta,\delta]^n\) as \(\delta \to 0\)). We fix \(S \subseteq [m]\), draw \(X_i \sim [0,2]\) uniformly for \(i \in S\) and deterministically set \(X_i = 1\) otherwise. Then by Theorem 9 and Proposition 8(E), \[\frac{\mathrm{Vol}_S(K_S)}{2^{|S|}} = \mathbb{P}[Z_X \subseteq (1+\varepsilon) Z] \ge \frac{\mathrm{Vol}_n(\varepsilon Z)}{\mathrm{Vol}_n ((1+\varepsilon) Z)} = \Big(\frac{\varepsilon}{1+\varepsilon}\Big)^n \ge (\varepsilon/2)^n.\qedhere\] ◻
For our overall proof strategy we need to prove that \(K \cap -K\) is still sufficiently large. In fact, this turns out to be true using exactly the properties that we obtained in Theorem 10. This is what we will prove in the next section.
The goal of this section is to prove the following lower bound on the volume of the symmetrizer \(K \cap -K\) assuming all coordinate sections of \(K\) are large:
Theorem 11. Let \(p, \varepsilon\in (0, 1/2]\) and \(m\) be a positive integer so that \(m \ge \frac{\log_2 (1/p)}{\varepsilon^2}\). Let \(K \subseteq [-1,1]^m\) be a convex body so that \([-\varepsilon,\varepsilon]^m \subseteq K\) and, for every \(S \subseteq [m]\), \(\mathrm{Vol}_S (K_S) \ge p2^{|S|}\). Then \(\mathrm{Vol}_m (K \cap -K) \ge 2^{-5m}\).
The following will be helpful to certify that the symmetrizer is large:
Proposition 12. Let \(K \subseteq \mathbb{R}^m\) be a convex body. Let \(f_K(z) := \mathrm{Vol}_m(K \cap (2z-K))\) denote the volume of the intersection of \(K\) with its reflection around \(z\), supported on \(z \in K\).
There exists \(z^* \in K\) so that \(f_K(z^*) \ge 2^{-m} \mathrm{Vol}_m (K)\). In fact, the barycenter of \(K\) is a valid choice for \(z^*\).
For any \(z \in K \cap -K\) one has \(\mathrm{Vol}_m (K \cap -K) \ge 2^{-m} f_K(z)\).
For any \(t > 0\), the set \(\{z \in K: f_K(z) \ge t\}\) is convex.
Proof. (A). From the Milman-Pajor Theorem (Theorem 5) we immediately know that \(f_K(\mathop{\mathbb{E}}_{z \sim K}[z]) \geq 2^{-m}\mathrm{Vol}_m(K)\). But there is a direct proof as well, which we include: Sample \(x \sim K\) uniformly at random. Note that \(\mathbb{P}_{x \sim K} [x \in 2z-K] = \frac{f_K(z)}{\mathrm{Vol}_m(K)}\) for any \(z \in K\). In particular, sampling \(z \sim K\) uniformly at random independently, \[\frac{\mathop{\mathbb{E}}_{z \sim K} [f_K(z)]}{\mathrm{Vol}_m (K)} = \mathop{\mathbb{E}}_{z \sim K} \mathbb{P}_{x \sim K} [x \in 2z-K] = \mathop{\mathbb{E}}_{z \sim K} \mathop{\mathbb{E}}_{x \sim K} [\mathbf{1}_{\{x \in 2z-K\}}] = \mathop{\mathbb{E}}_{x \sim K} \mathbb{P}_{z\sim K} [x \in 2z-K].\] Since \(\mathbb{P}_{z\sim K} [x \in 2z-K] = \mathbb{P}_{z\sim K} [z \in (x+K)/2] = \frac{\mathrm{Vol}_m((x+K)/2)}{\mathrm{Vol}_m(K)} = 2^{-m}\), it follows that \(\mathop{\mathbb{E}}_{z \sim K} [f_K(z)] = 2^{-m} \mathrm{Vol}_m (K)\) and some \(z^* \in K\) satisfies \(f_K(z^*) \ge 2^{-m} \mathrm{Vol}_m (K)\).
(B). Let \(Q = \frac{1}{2} (K \cap (2z-K) - z)\) and note that \(\mathrm{Vol}_m (Q) = 2^{-m} f_K(z)\). It remains to check that \(Q \subseteq K \cap -K\). Indeed, any \(y \in Q\) may be written as \((x-z)/2\) for some \(x \in K \cap (2z-K)\); we have \((x-z)/2 \in K\) by convexity since \(x, -z \in K\), and also \((x-z)/2 = (x-2z+z)/2 \in -K\) by convexity since \(z, x-2z \in -K\).
(C). By Theorem 6, the function \(f_K(z)^{1/m}\) is concave on its support. Hence the superlevel sets of \(f_K(z)^{1/m}\) are convex. Then the same holds true for the superlevel sets of \(f_K(z)\). ◻
In order to reach a contradiction from a separating hyperplane, we need the following key technical lemma:
Lemma 5. Let \(p \in (0,1/2]\) and \(\lambda = \sqrt{\log_2 (1/p)} \ge 1\). Let \(K \subseteq [-1,1]^m\) be a convex body so that \(\mathbf{0} \in K\) and for every \(S \subseteq [m]\), \(\mathrm{Vol}_S (K_S) \ge p 2^{|S|}\). Then for every \(a \in \mathbb{R}^m\), \[K_a := K \cap \Big\{x \in [-1,1]^m : \langle a, x \rangle \le \lambda/\sqrt{m} \cdot \|a\|_1 \Big\}\] has volume \(\mathrm{Vol}_m (K_a) \ge p 2^{-2m}\).
Proof. If \(m \le 4\lambda^2\) then \(\tfrac{1}{2} K \subseteq K_a\) as \(\langle a,x \rangle \le \tfrac{1}{2} \|a\|_1 \le \lambda/\sqrt{m} \cdot \|a\|_1\) for all \(x \in \tfrac{1}{2} [-1,1]^m\), so that \(\mathrm{Vol}_m (K_a) \ge 2^{-m} \mathrm{Vol}_m(K) \ge p > p 2^{-2m}\). Assume \(m > 4 \lambda^2\) and reorder coordinates so that \(|a_1| \ge |a_2| \ge \cdots \ge |a_m|\). Define a sequence of indices by \(m_1=m\) and \(m_{k+1}=\lfloor m_k/2\rfloor\) for \(k \ge 1\), and let \(\ell\) be the first index such that \(m_\ell\le 4\lambda^2\); in particular \(m_k > 4\lambda^2 \ge 4\) for \(k < \ell\). Partition \([m]=I_\ell \sqcup I_{\ell-1}\sqcup\cdots\sqcup I_1\) where for \(1\le k<\ell\), \(I_k:=[m_k]\setminus [m_{k+1}]\), and \(I_\ell := [m_\ell]\). For each \(1\le k<\ell\), let \[Q_k:=\Big\{x_{I_k} \in K_{I_k}:\langle a_{I_k},x_{I_k}\rangle \le \lambda\,\|a_{I_k}\|_2\Big\}.\] By Lemma 1, we have \(\mathrm{Vol}_{I_k}(Q_k) \ge \mathrm{Vol}_{I_k}(K_{I_k}) - p^2 2^{|I_k|} \ge p2^{|I_k|}-p^2 2^{|I_k|} \ge \tfrac{p}{2} 2^{|I_k|}.\)
For \(I_\ell\) we set \(Q_\ell := \Big\{ x_{I_\ell} \in K_{I_\ell}: \langle a_{I_\ell},x_{I_\ell} \rangle \le \lambda/\sqrt{m_\ell}\cdot \|a_{I_\ell}\|_1 \Big\}\) which has volume at least \(p\) as \(|I_\ell| \le 4\lambda^2\), so that \(\tfrac{1}{2} K_{I_\ell} \subseteq Q_\ell\) as above.
Now define the Cartesian product \[P := \Big\{x \in \mathbb{R}^m : x_{I_\ell} \in 2^{-(\ell - 1)} Q_\ell \;\text{ and } \;x_{I_k}\in 2^{-k} Q_k\;\text{ for } k\in [1,\ell)\Big\}.\] It remains to show the following:
Claim 1. \(P \subseteq K_a\) and \(\mathrm{Vol}_m (P) \ge p 2^{-2m}.\)
The chosen coefficients satisfy \(2^{-(\ell-1)}+\sum_{k\in [1,\ell)}2^{-k}=1\) so \(P\subseteq K\) by convexity. For each \(1\le k<\ell\), every coordinate \(a_i\) with \(i \in I_k = [m_k] \setminus [m_{k+1}]\) has absolute value at most \(\frac{\|a_{[m_{k+1}]}\|_1}{m_{k+1}}\), so that \(\|a_{I_k}\|_2^2 \le \|a_{I_k}\|_\infty\|a_{I_k}\|_1 \le \frac{\|a_{[m_{k+1}]}\|_1\|a_{I_k}\|_1}{m_{k+1}}\). We may bound \[\begin{align} 2^{-k} \lambda \|a_{I_k}\|_2 &\le \frac{2^{-k}\lambda}{\sqrt{m_{k+1}}} \sqrt{\|a_{[m_{k+1}]}\|_1\|a_{I_k}\|_1} \\ &\le \frac{2^{-(k-1)}\lambda}{\sqrt{m_k}}\|a_{[m_k]}\|_1 - \frac{2^{-k}\lambda}{\sqrt{m_{k+1}}} \|a_{[m_{k+1}]}\|_1, \end{align}\] where we use \(2\sqrt{m_{k+1}/m_k} \ge 2 \sqrt{\tfrac{2}{5}} > \frac{5}{4}\) and \(\sqrt{uv} \le \frac{5}{4} (u+v) - u\) for \(u,v \ge 0\).
Thus \(P \subseteq K_a\), as for any \(x\in P\) we indeed have, by telescoping, \[\begin{align} \left<a,x\right> &=& \sum_{k=1}^{\ell-1} \left<a_{I_k},x_{I_k}\right> + \left<a_{I_{\ell}},x_{I_{\ell}}\right> \\ &\leq& \sum_{k=1}^{\ell-1} 2^{-k} \lambda \|a_{I_k}\|_2 + \frac{2^{-(\ell-1)} \lambda}{\sqrt{m_\ell}}\|a_{I_{\ell}}\|_1 \\ &\leq& \frac{\lambda}{\sqrt{m_1}} \|a_{[m_1]}\|_1 =\lambda/\sqrt{m} \cdot \|a\|_1. \end{align}\] It remains to lower bound \(\mathrm{Vol}_m (P)\). The set \(P\) arises from the sets \(Q_k\) by scaling, so \[\begin{align} \mathrm{Vol}_m(P) &= \mathrm{Vol}_{I_\ell}(2^{-(\ell-1)} Q_\ell) \prod_{k=1}^{\ell-1}\mathrm{Vol}_{I_k}( 2^{-k} Q_k) \\ & \ge 2^{-(\ell-1) m_\ell} \cdot p \cdot \prod_{k=1}^{\ell-1} 2^{-k |I_k|} \cdot \tfrac{p}{2} 2^{|I_k|} \\ &= 2^{-\sum_{k=1}^{\ell-1} m_k}\cdot p \cdot 2^{m-m_\ell} \cdot (p/2)^{\ell-1} \\ &= p \cdot 2^{m-\sum_{k=1}^{\ell} m_k} \cdot (p/2)^{\ell-1} \\ & \ge p 2^{-m} \cdot 2^{-m} = p 2^{-2m}, \end{align}\] where we use \(\sum_{k=1}^\ell m_k < 2m\) as \(m_{k+1} \le m_k /2\) for \(k \ge 1\), and \((p/2)^{\ell-1} \ge 2^{-m}\) as \(\ell-1 \le \lceil \log_2 (m/(4\lambda^2)) \rceil \le m/(2\lambda^2)\) and so \((2/p)^{\ell-1} = 2^{(\ell-1)(\lambda^2+1)} \le 2^{m \cdot \frac{\lambda^2+1}{2\lambda^2}} \le 2^m\). ◻
Now we have all the ingredients to show the main theorem of this section.
Proof of Theorem 11. Let \(K\) be a convex body with \(\varepsilon B_{\infty}^m \subseteq K \subseteq B_{\infty}^m\) so that all coordinate sections of \(K\) have relative volume of at least \(p\). Our goal is to
prove that \(\mathrm{Vol}_m(K \cap -K)\) is large. We abbreviate \(r := \sqrt{\frac{\log_2(1/p)}{m}}\) and prove the following:
Claim I. There is a \(z^* \in K\) with \(f_K(z^*) \geq p2^{-3m}\) and \(\|z^*\|_{\infty} \leq r\).
Proof of Claim I. Let \(S := \{ z \in K \mid f_K(z) \geq p2^{-3m}\}\) which by Prop 12(C) is a convex
set. Suppose for the sake of contradiction that there is no such \(z^*\). That means the two convex sets \(S\) and \(r B_{\infty}^m\) are disjoint. Then by
the separating hyperplane theorem, there is a hyperplane with normal vector \(a \in \mathbb{R}^m\) that separates the two sets. After choosing an orientation for \(a\) we have \[\forall z \in S: \;\; \left<a,z\right> > \max_{x \in rB_{\infty}^m} \left<a,x\right> = r \|a\|_{1}.\] Now, let \(z^*\) be the barycenter of \(K_a = K
\cap \{ x \in [-1,1]^m : \left<a,x\right> \leq r\|a\|_1\}\). Then \[f_K(z^*) \geq f_{K_a}(z^*) \stackrel{\textrm{Prop~\ref{prop:reflectionVolume}}(A)}{\geq} 2^{-m}\mathrm{Vol}_m(K_a) \stackrel{(*)}{\geq} 2^{-m} \cdot
p 2^{-2m} = p2^{-3m}.\] Here we apply Lemma 5 in \((*)\). Thus \(z^* \in S\) while
\(\langle a, z^*\rangle \le r\|a\|_1\) which is a contradiction. 0◻
Now we conclude the main proof. By the assumption \(m \ge \frac{\log_2(1/p)}{\varepsilon^2}\) we have \(\|z^*\|_\infty \le r \le \varepsilon\). Since \([-\varepsilon,\varepsilon]^m \subseteq K\), we obtain \(z^* \in K \cap -K\) and Prop 12(B) yields \[\mathrm{Vol}_m (K \cap -K) \ge 2^{-m} f_K (z^*) \ge p 2^{-4m} > 2^{-5m},\] as \(p \ge 2^{-m\varepsilon^2} \ge 2^{-m/4}\). ◻
We finally prove Theorem 2 which also implies the statements of Theorem 1 and Theorem 3. First we summarize what we learned from Section 3 and Section 4.
Corollary 1. Let \(Z \subseteq \mathbb{R}^n\) be a zonotope generated by the rows of \(A \in \mathbb{R}^{m \times n}\). For \(\varepsilon\in (0,1/2]\) and \(m \ge \frac{2n \log_2(1/\varepsilon)}{\varepsilon^2}\) the set \[Q = \{ x \in [-1,1]^m \mid (1-\varepsilon) Z \subseteq Z_{\boldsymbol{1}+x} \subseteq (1+\varepsilon) Z \}\] is convex and symmetric, and has volume \(\mathrm{Vol}_m (Q) \ge 2^{-5m}\).
Proof. As in 3 , we can write \(Q\) in inequality form as \[Q = \Big\{x \in [-1,1]^m : \Big|\sum_{i=1}^m x_i \cdot |\langle a_i, y \rangle|\Big| \le \varepsilon\sum_{i =1}^m |\langle a_i, y \rangle| \;\forall y \in \mathbb{R}^n\Big\},\] from which symmetry and convexity are immediate. Note that \(Q\) is precisely \(K \cap -K\) for the convex set \(K\) defined in Theorem 10, which by that theorem satisfies \([-\varepsilon,\varepsilon]^m \subseteq K\) and \(\mathrm{Vol}_S (K_S) \ge p 2^{|S|}\) for every \(S \subseteq [m]\) for \(p = (\varepsilon/2)^n\). We have \(m \ge \frac{2 n \log_2(1/\varepsilon)}{\varepsilon^2} \ge \frac{n \log_2(2/\varepsilon)}{\varepsilon^2} = \frac{\log_2(1/p)}{\varepsilon^2}\) and thus by Theorem 11 we have \(\mathrm{Vol}_m(Q) = \mathrm{Vol}_m(K \cap -K) \geq 2^{-5m}\). ◻
Now we prove Theorem 2 which we restate in a slightly expanded form:
Theorem 13. Let \(Z \subseteq \mathbb{R}^{n}\) be a zonotope generated by the rows of \(A \in \mathbb{R}^{m \times n}\) and let \(0<\varepsilon \leq \frac{1}{2}\). Then there exists a weight vector \(w \in \mathbb{R}_{\geq 0}^m\) with \(|\textrm{supp}(w)| \leq O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))\) so that \((1-\varepsilon) Z \subseteq Z_w \subseteq (1+\varepsilon) Z\). Moreover, the weight vector \(w\) can be computed in randomized time \(2^m\) times a polynomial in the encoding length of \(A\).
Proof. The proof strategy is to iteratively reduce the number of used segments via Theorem 7 until it reaches a target of \(M := C\frac{2n \log_2 (1/\varepsilon)}{\varepsilon^2}\) where \(C>0\) is a large enough constant. Starting with \(w^{(0)} := \boldsymbol{1}\), we construct a sequence of vectors \(w^{(t)} \in \mathbb{R}^{m}_{\geq 0}\) for \(t \in \{0, \dots, T\}\) supported on \(S_t := \textrm{supp}(w^{(t)})\) with \(m_t := |S_t|\) so that \(m_t \le \tfrac{3}{4} m_{t-1}\) for each \(t \in [T]\) and \(T\) is the first index with \(m_T \le M\). Set \(\varepsilon_t\) so that \(m_t = \frac{2n \log_2 (1/\varepsilon_t)}{\varepsilon_t^2}\). For vectors \(a,b \in \mathbb{R}^m\) we denote by \(a \odot b \in \mathbb{R}^m\) the coordinate-wise product, i.e. \((a \odot b)_i := a_i \cdot b_i\). Consider the set \[Q_{\varepsilon_t} := \Big\{x \in [-1,1]^{S_t} : (1-\varepsilon_t) Z_{w^{(t)}} \subseteq Z_{(\boldsymbol{1}+x) \odot w^{(t)}} \subseteq (1+\varepsilon_t) Z_{w^{(t)}} \Big\},\] which by Corollary 1 is a symmetric convex body of volume at least \(2^{-5m_t}\). Then applying Theorem 7 to \(Q_{\varepsilon_t}\) with \(c := 2^{-5}\) yields a vector \(x^{(t)} \in sQ_{\varepsilon_t} \cap [-1,1]^{S_t}\) with \(|\{ i : |x^{(t)}_i| = 1\}| \ge \tfrac{1}{2} m_t\) where \(s>0\) is some constant. After possibly flipping the signs of \(x^{(t)}\) we may assume that \(|\{i \in S_t \mid x^{(t)}_i = -1\}| \geq \frac{m_t}{4}\). We update \(w^{(t+1)}_i := (1+x^{(t)}_i) \cdot w^{(t)}_i\) (filling \(x^{(t)}\) with zeros outside of \(S_t\)) so that the support \(S_{t+1} = \textrm{supp}(w^{(t+1)})\) has size \(|S_{t+1}| \leq \frac{3}{4} m_t\). Moreover, we have \[(1-s \varepsilon_t) Z_{w^{(t)}} \subseteq Z_{w^{(t+1)}} \subseteq (1+s\varepsilon_t) Z_{w^{(t)}}.\] Then iterating over \(t=0,\ldots,T-1\) we have \[\prod_{t=0}^{T-1} (1-s \varepsilon_t) Z \subseteq Z_{w^{(T)}} \subseteq \prod_{t=0}^{T-1} (1+s \varepsilon_t) Z.\] It remains to prove that \(\prod_{t=0}^{T-1} (1-s \varepsilon_t) \geq 1-\varepsilon\) and \(\prod_{t=0}^{T-1} (1+s \varepsilon_t) \leq 1+\varepsilon\).
Let \(\phi(z) := \frac{\log_2 (1/z)}{z^2}\). In order to bound \(\varepsilon_t\), we use the following inequality:
Claim. \(\phi(\varepsilon)z \ge \phi(\varepsilon z^{-1/4})\) for all \(z \ge 1\).
Indeed, \(\frac{\phi(\varepsilon z^{-1/4})}{\phi(\varepsilon)} = z^{1/2} \Big(1 + \frac{\log_2 (z)}{4\log_2(1/\varepsilon)}\Big) \le z^{1/2} \Big(1 + \frac{\log_2 (z)}{4}\Big) \le z\) as \(\varepsilon\le 1/2\).
By definition, \(\phi(\varepsilon_t) = \frac{m_t}{2n} \ge \phi(\varepsilon) \cdot C \cdot (\tfrac{4}{3})^{T-1-t}\). By the claim and the fact that \(\phi\) is decreasing, it follows that \(\varepsilon_t \le \varepsilon\cdot C^{-1/4} \cdot (\tfrac{3}{4})^{(T-1-t)/4}\), so choosing \(C = \Theta(s^4)\) we obtain \(\sum_{t = 0}^{T-1} s \varepsilon_t \le \varepsilon/2\). In particular, as \(\prod_{t=0}^{T-1} (1-s\varepsilon_t) \ge 1- \sum_{t=0}^{T-1} s\varepsilon_t \ge 1-\varepsilon\) and \(\prod_{t=0}^{T-1} (1+s\varepsilon_t) \le \prod_{t=0}^{T-1} \exp(s\varepsilon_t) \le \exp(\varepsilon/2) \le 1+\varepsilon\), we conclude \[(1-\varepsilon) Z \subseteq Z_{w^{(T)}} \subseteq (1+\varepsilon) Z,\] as claimed.
Finally, we discuss the running time aspect. All ingredients used in our argument can be implemented in polynomial time — except the separation oracle for \(Q_{\varepsilon_t}\) as required by Theorem 7. As \(Q_{\varepsilon_t}\) is a symmetric convex body, separation is polynomial-time equivalent to testing membership, see [30]. That means we need to test the inclusion \(Z_1 \subseteq Z_2\) polynomially many times, where \(Z_1,Z_2 \subseteq \mathbb{R}^n\) are zonotopes generated by at most \(m\) segments each. While such a test is \(\mathbf{coNP}\)-complete in general [20], \(Z_1\) has at most \(2^m\) vertices that can be enumerated explicitly. Then for each vertex \(x \in \textrm{vert}(Z_1)\) one can test whether \(x \in Z_2\). Here we use that for a single zonotope, the separation problem is solvable in polynomial time by reducing it to the optimization problem. ◻
We may also summarize the algorithm behind Theorem 13 as follows:
The goal of this section is to give an alternative proof of the spectral sparsification result of Batson, Spielman and Srivastava [9], [10] as stated in Theorem 4. Given matrices \(A_1,\dots,A_m\in\mathbb{R}^{n\times n}\) and a vector \(t \in \mathbb{R}^m\), we denote \(A(t) :=\sum_{j=1}^m t_j A_j\).
The analogue of \(f(t) = \mathrm{Vol}_n (K \ominus Z_t)\) that we had earlier is the following:
Lemma 6.
Let \(A_1, \dots, A_m \succeq 0\) and \(B \succ 0\). Define a function \(\Phi : \mathbb{R}_{\ge 0}^m \to \mathbb{R}_{\ge 0}\) by \[\Phi(t):= \begin{cases} \det(B-A(t)) &\text{if } A(t)\preceq B\\ 0,&\text{otherwise}. \end{cases}\] Then \(\Phi\) is separately convex.
Proof. We prove the univariate case first:
Claim I. Let \(A,B \in \mathbb{R}^{n \times n}\) symmetric matrices with \(A \succeq 0\). Then the function \(f : \mathbb{R}_{\ge 0} \to
\mathbb{R}_{\ge 0}\) with \[f(s):= \begin{cases} \det(B-sA)&\text{if } sA\preceq B,\\ 0&\text{otherwise}. \end{cases}\] is convex.
Proof of Claim I. If \(B\) is not positive definite then \(f\equiv0\), so assume \(B \succ 0\) and let \(\lambda_1
\ge \dots \ge \lambda_n\geq0\) be the eigenvalues of \(B^{-1/2}AB^{-1/2}\). Then \[\begin{align} f(s) &=& \boldsymbol{1}_{B - sA \succeq 0} \cdot \det(B-sA) \\ &=&
\boldsymbol{1}_{s B^{-1/2}AB^{-1/2} \preceq I_n} \cdot \det(B) \cdot \det(I_n - s B^{-1/2}AB^{-1/2}) \\ &=& \mathbf{1}_{\{s \lambda_1 \leq 1\}} \cdot \det(B) \cdot \prod_{j=1}^n(1-s\lambda_j).
\end{align}\] For \(s\lambda_1 \le 1\) we have \(f''(s) =\det(B) \cdot \sum_{i\ne j}\lambda_i\lambda_j \prod_{\ell\ne i, j}(1-s\lambda_\ell)\ge 0\). Moreover, \(f(s)\) is nonincreasing and vanishes when \(s\lambda_1 =1\). Therefore \(f\) is convex, as needed. 0◻
Now back to the main proof. Let \(t \in \mathbb{R}_{\geq 0}^m\) and \(k \in [m]\). Then apply Claim I with \(B' :=B-\sum_{j\neq k}t_jA_j\) and \(A' := A_k\) and the claim follows. ◻
Now we prove an analogue of Theorem 9:
Lemma 7. Let \(A_1,\dots,A_m\in\mathbb{R}^{n\times n}\) be positive semidefinite matrices, and let \(B\succ0\). Let \(X_1,\dots,X_m\geq0\) be independent random variables, and suppose \(A(\mathop{\mathbb{E}}[X])\preceq B\). Then \[\mathbb{P}[A(X)\preceq B] \ge \frac{\det(B-A(\mathop{\mathbb{E}}[X]))}{\det(B)}.\]
Proof. If \(A(X)\preceq B\) then \(0\preceq B-A(X)\preceq B\) and \(\det(B-A(X))\leq\det(B)\), so that we may bound \(\Phi(X) \le \det(B)\cdot \mathbf{1}_{\{A(X)\preceq B\}}\). Therefore, by Lemmas 2 and 6, \[\det(B)\cdot \mathbb{P}[A(X)\preceq B] \ge \mathop{\mathbb{E}}[\Phi(X)] \ge \Phi(\mathop{\mathbb{E}}[X]) = \det(B-A(\mathop{\mathbb{E}}[X])). \qedhere\] ◻
Corollary 2. For any positive semidefinite matrices \(A_1, \dots, A_m \in \mathbb{R}^{n \times n}\) and \(\varepsilon\in (0, 1/2]\) with \(m \ge \frac{2n \log_2 (1/\varepsilon)}{\varepsilon^2}\), the set \[Q = \Big\{w \in [-1,1]^m : -\varepsilon A(\mathbf{1}) \preceq A(w) \preceq \varepsilon A(\mathbf{1})\Big\}\] has volume \(\mathrm{Vol}_m (Q) \ge 2^{-5m}\).
Proof. Let \(K := \Big\{w \in [-1,1]^m : A(w) \preceq \varepsilon A(\mathbf{1})\Big\}\) so that \(Q = K \cap -K\) and note that \([-\varepsilon, \varepsilon]^m \subseteq K\) as \(A_k \succeq 0\) and \(K\) is convex. We may also assume without loss of generality that \(A(\mathbf{1}) \succ 0\) (for example by adding \(\delta I_n\) as \(\delta \to 0\)) so that for any \(S \subseteq [m]\), Lemma 7 with \(X_k \sim [0,2]\) for \(k \in S\) and \(X_k = 1\) otherwise yields \[\frac{\mathrm{Vol}_S (K_S)}{2^{|S|}} = \mathbb{P}[A(X) \preceq A((1+\varepsilon) \cdot \mathbf{1})] \ge \frac{\det(A(\varepsilon\cdot \mathbf{1}) )}{\det(A((1+\varepsilon) \cdot \mathbf{1}))} = \Big(\frac{\varepsilon}{1+\varepsilon}\Big)^n \ge (\varepsilon/2)^n =: p.\] Thus by Theorem 11, \(\mathrm{Vol}_m(Q) \ge 2^{-5m}\) as \(m \ge \frac{2 n \log_2 (1/\varepsilon)}{\varepsilon^2} \ge \frac{n \log_2 (2/\varepsilon)}{\varepsilon^2} = \frac{\log_2 (1/p)}{\varepsilon^2}\). ◻
Now we can derive the following result which is the arbitrary-rank analogue of [9], [10] due to De Carli, Harvey and Sato [31]:
Theorem 14. For any positive semidefinite matrices \(A_1, \dots, A_m \in \mathbb{R}^{n \times n}\) with \(M = \sum_{i=1}^m A_i\) and any \(\varepsilon\in (0, 1/2]\) there exist weights \(w_1, \dots, w_m \ge 0\) with \(|\{k \in [m] : w_k \ne 0\}| \le O\Big(\frac{n \log_2(1/\varepsilon)}{\varepsilon^2}\Big)\) so that \[(1-\varepsilon) M \preceq \sum_{i=1}^m w_iA_i \preceq (1+\varepsilon) M\] Moreover, the weights can be found in polynomial time.
Proof. The proof is completely analogous to that of Theorem 1, except here the membership test for the set \(Q\) in Cor 2 boils down to the following: given symmetric matrices \(A,B \in \mathbb{R}^{n \times n}\), test if \(A \preceq B\). This can be done in polynomial time. ◻
Proof of Theorem 4. Let \(A\) have rows \(a_1, \dots, a_m\) and take \(A_k = a_k a_k^\top\) in Theorem 14. The matrix \(D\) is formed by entries \(D_{k,k} = \sqrt{w_k}\). ◻
The authors used GPT-5.5 Pro during the development of this work to explore proof strategies, search for related literature, and assist with verification. GPT was not used in any part of the exposition.
Proof of Lemma 1. Draw \(z_k \sim \{-1,1\}\) independently for \(k \in \mathbb{N}\), so \(\mathbb{E}[e^{t z_k}] =\frac{e^t+e^{-t}}{2} \le e^{t^2/2}\). Let \(z=\sum_{k \ge 1} 2^{-k} z_k\). Then \(z \sim [-1,1]\) and, by independence, \[\mathop{\mathbb{E}}[e^{tz}] =\prod_{k=1}^\infty \mathop{\mathbb{E}}[e^{t 2^{-k}z_k}] \le \prod_{k=1}^\infty \exp\Big(\frac{t^2 2^{-2k}}{2}\Big) =\exp\Big(\frac{t^2}{2}\sum_{k=1}^\infty 4^{-k}\Big)=e^{t^2/6}.\]
Since \(x \sim [-1,1]^m\), this gives \(\displaystyle \mathop{\mathbb{E}}[e^{t \langle v, x \rangle}] = \prod_{k=1}^m \mathop{\mathbb{E}}[e^{tv_k x_k}] \le \exp\Big(\frac{t^2\|v\|_2^2}{6}\Big).\) If \(v = \mathbf{0}\) or \(\lambda = 0\) there is nothing to prove; otherwise, taking \(t = 3 \sqrt{\lambda}/\|v\|_2\),
\[\begin{align} \mathbb{P}\Big[\langle v,x\rangle > \sqrt{\lambda}\,\|v\|_2\Big] &= \mathbb{P}\Big[e^{t\langle v,x\rangle} > e^{t\sqrt{\lambda}\|v\|_2}\Big] \\ &\le e^{-t\sqrt{\lambda}\|v\|_2} \mathop{\mathbb{E}}\Big[e^{t\langle v,x\rangle}\Big] \\ &\le \exp\Big( -t\sqrt{\lambda}\|v\|_2 + \frac{t^2\|v\|_2^2}{6} \Big) \\ &\le e^{-3\lambda/2}\\ & \le 2^{-2\lambda}. \qedhere \end{align}\] ◻