# A Hyperbolic Extension of Kadison-Singer Type Results

Ruizhe Zhang<EMAIL_ADDRESS>The University of Texas at Austin. Research
supported by the University Graduate Continuing Fellowship. Xinzhi Zhang
<EMAIL_ADDRESS>University of Washington. Research supported by
NSF grant CCF-1813135.

In 2013, Marcus, Spielman, and Srivastava resolved the famous Kadison-Singer
conjecture. It states that for $n$ independent random vectors
$v_{1},\cdots,v_{n}$ that have expected squared norm bounded by $\epsilon$ and
are in the isotropic position in expectation, there is a positive probability
that the determinant polynomial $\det(xI-\sum_{i=1}^{n}v_{i}v_{i}^{\top})$ has
roots bounded by $(1+\sqrt{\epsilon})^{2}$. An interpretation of the Kadison-
Singer theorem is that we can always find a partition of the vectors
$v_{1},\cdots,v_{n}$ into two sets with a low discrepancy in terms of the
spectral norm (in other words, rely on the determinant polynomial).

In this paper, we provide two results for a broader class of polynomials, the
hyperbolic polynomials. Furthermore, our results are in two generalized
settings:

  * •

The first one shows that the Kadison-Singer result requires a weaker
assumption that the vectors have a bounded sum of hyperbolic norms.

  * •

The second one relaxes the Kadison-Singer result’s distribution assumption to
the Strongly Rayleigh distribution.

To the best of our knowledge, the previous results only support determinant
polynomials [Anari and Oveis Gharan’14, Kyng, Luh and Song’20]. It is unclear
whether they can be generalized to a broader class of polynomials. In
addition, we also provide a sub-exponential time algorithm for constructing
our results.

##  1 Introduction

Introduced by [KS59], the Kadison-Singer problem was a long-standing open
problem in mathematics. It was resolved by Marcus, Spielman, and Srivastrava
in their seminal work [MSS15b]: For any set of independent random vectors
$u_{1},\cdots,u_{n}$ such that each $u_{i}$ has finite support, and
$u_{1},\cdots,u_{n}$ are in isotropic positions in expectation, there is
positive probability that $\sum_{i=1}^{n}u_{i}u_{i}^{*}$ has spectral norm
bounded by $1+O(\max_{i\in[n]}\|u_{i}\|)$. The main result of [MSS15b] is as
follows:

######  Theorem 1.1 (Main result of [MSS15b]).

Let $\epsilon>0$ and let $v_{1},\cdots,v_{n}\in\operatorname*{\mathbb{C}}^{m}$
be $n$ independent random vectors with finite support, such that
$\operatorname*{{\mathbb{E}}}[\sum_{i=1}^{n}v_{i}v_{i}^{*}]=I$, and
$\operatorname*{{\mathbb{E}}}[\|v_{i}\|^{2}]\leq\epsilon$, $\forall i\in[n]$.
Then

$\displaystyle\Pr\left[\Big{\|}\sum_{i\in[n]}v_{i}v_{i}^{*}\Big{\|}\leq(1+\sqrt{\epsilon})^{2}\right]>0.$

The Kadison-Singer problem is closely related to discrepancy theory, which is
an essential area in mathematics and theoretical computer science. A classical
discrepancy problem is as follows: given $n$ sets over $n$ elements, can we
color each element in red or blue such that each set has roughly the same
number of elements in each color? More formally, for vectors
$a_{1},\dots,a_{n}\in\mathbb{R}^{n}$ with $\|a_{i}\|_{\infty}\leq 1$ and a
coloring $s\in\\{\pm 1\\}^{n}$, the discrepancy is defined by
$\mathrm{Disc}(a_{1},\dots,a_{n};s):=\|\sum_{i\in[n]}s_{i}a_{i}\|_{\infty}$.
The famous Spencer’s Six Standard Deviations Suffice Theorem [Spe85] shows
that there exists a coloring with discrepancy at most $6\sqrt{n}$, which beats
the standard Chernoff bound showing that a random coloring has discrepancy
$\sqrt{n\log n}$. More generally, we can consider the “matrix version” of
discrepancy: for matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{d\times d}$ and a
coloring $s\in\\{\pm 1\\}^{n}$,

$\displaystyle\mathrm{Disc}(A_{1},\dots,A_{n};s):=\Big{\|}\sum_{i\in[n]}s_{i}A_{i}\Big{\|}.$

Theorem 1.1 is equivalent to the following discrepancy result for rank-1
matrices:

######  Theorem 1.2 ([MSS15b]).

Let $u_{1},\dots,u_{n}\in\operatorname*{\mathbb{C}}^{m}$ and suppose
$\max_{i\in[n]}\|u_{i}u_{i}^{*}\|\leq\epsilon$ and
$\sum_{i=1}^{n}u_{i}u_{i}^{*}=I$. Then,

$\displaystyle\min_{s\in\\{\pm 1\\}^{n}}\leavevmode\nobreak\
\mathrm{Disc}(u_{1}u_{1}^{*},\dots,u_{n}u_{n}^{*};s)\leq O(\sqrt{\epsilon}).$

In other words, the minimum discrepancy of rank-1 isotropic matrices is
bounded by $O(\sqrt{\epsilon})$, where $\epsilon$ is the maximum spectral
norm. This result also beats the matrix Chernoff bound [Tro15], which shows
that a random coloring for matrices has discrepancy $O(\sqrt{\epsilon\log
d})$. The main techniques in [MSS15b] are the method of interlacing
polynomials and the barrier methods developed in [MSS15a].

Several generalizations of the Kadison-Singer-type results, which have
interesting applications in theoretical computer science, have been
established using the same technical framework as described in [MSS15b]. In
particular, Kyng, Luh, and Song [KLS20] provided a “four derivations suffice”
version of Kadison-Singer conjecture: Instead of assuming every independent
random vector has a bounded norm, the main result in [KLS20] only requires
that the sum of the squared spectral norm is bounded by $\sigma^{2}$, and
showed a discrepancy bound of $4\sigma$:

######  Theorem 1.3 ([KLS20]).

Let $u_{1},\dots,u_{n}\in\operatorname*{\mathbb{C}}^{m}$ and
$\sigma^{2}=\|\sum_{i=1}^{n}(u_{i}u_{i}^{*})^{2}\|$. Then, we have

$\displaystyle\Pr_{\xi\sim\\{\pm
1\\}^{n}}\left[\Big{\|}\sum_{i=1}^{n}\xi_{i}u_{i}u_{i}^{*}\Big{\|}\leq
4\sigma\right]>0.$

This result was recently applied by [LZ20] to approximate solutions of
generalized network design problems.

Moreover, Anari and Oveis-Gharan [AO14] generalized the Kadison-Singer
conjecture into the setting of real-stable polynomials. Instead of assuming
the random vectors are independent, [AO14] assumes that the vectors are
sampled from any homogeneous strongly Rayleigh distribution with bounded
marginal probability, have bounded norm, and are in an isotropic position:

######  Theorem 1.4 ([AO14]).

Let $\mu$ be a homogeneous strongly Rayleigh probability distribution on $[n]$
such that the marginal probability of each element is at most $\epsilon_{1}$,
and let $u_{1},\cdots,u_{n}\in\mathbb{R}^{m}$ be vectors in an isotropic
position, $\sum_{i=1}^{n}u_{i}u_{i}^{*}=I$, such that
$\max_{i\in[n]}\|u_{i}\|^{2}\leq\epsilon_{2}$. Then

$\displaystyle\Pr_{S\sim\mu}\left[\Big{\|}\sum_{i\in
S}u_{i}u_{i}^{*}\Big{\|}\leq
4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}\right]>0.$

Theorem 1.4 has a direct analog in spectral graph theory: Given any (weighted)
connected graph $G=(V,E)$ with Laplacian $L_{G}$. For any edge $e=(u,v)\in E$,
define the vector corresponding to $e$ as
$v_{e}=L_{G}^{\dagger/2}(\mathbf{1}_{u}-\mathbf{1}_{v})$ (here
$L_{G}^{\dagger}$ is the Moore-Penrose inverse). Then the set of
$\\{v_{e}:e\in E\\}$ are in isotropic position, and $\|v_{e}\|^{2}$ equals to
the graph effective resistance with respect to $e$. Also, any spanning tree
distribution of the edges in $E$ is homogeneous strongly Rayleigh. It follows
from Theorem 1.4 that any graph with bounded maximum effective resistance has
a spectrally-thin spanning tree [AO14]. Moreover, [AO15] provided an exciting
application to the asymmetric traveling salesman problem and obtained an
$O(\log\log n)$-approximation.

Another perspective of generalizing the Kadison-Singer theorem is to study the
discrepancy with respect to a more general norm than the spectral norm, which
is the largest root of a determinant polynomial. A recent work by Bränden
[Brä18] proved a high-rank version of Theorem 1.2 for _hyperbolic_ polynomial,
which is a larger class of polynomials including the determinant polynomial.
Moreover, the hyperbolic norm on vectors is a natural generalization of the
matrix spectral norm. (We will introduce hyperbolic polynomials in Section
1.1.) From this perspective, it is very natural to ask:

_Can we also extend Theorem 1.3 and Theorem 1.4 to a more general class of
polynomials, e.g., hyperbolic polynomials?_

###  1.1 Our results

In this work, we provide an affirmative answer by generalizing both Theorem
1.3 and Theorem 1.4 into the setting of hyperbolic polynomials. Before stating
our main results, we first introduce some basic notation of hyperbolic
polynomials below.

Hyperbolic polynomials form a broader class of polynomials that encompasses
determinant polynomials and homogeneous real-stable polynomials. An
$m$-variate, degree-$d$ homogeneous polynomial
$h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ is _hyperbolic_ with respect to a
direction $e\in\mathbb{R}^{m}$ if the univariate polynomial $t\mapsto h(te-x)$
has only real roots for all $x\in\mathbb{R}^{m}$. (See Appendix E for some
examples of hyperbolic/real-stable polynomials.) The set of
$x\in\mathbb{R}^{m}$ such that all roots of $h(t\mathrm{e}-x)$ are non-
negative (or strictly positive) is referred to as the hyperbolicity cone
$\Gamma^{h}_{+}(e)$ (or $\Gamma^{h}_{++}(e)$). It is a widely recognized
result [Brä10] that any vector $x$ in the open hyperbolicity cone
$\Gamma^{h}_{++}(e)$ is itself hyperbolic with respect to the polynomial $h$
and have the same hyperbolicity cone as $e$, meaning that
$\Gamma^{h}_{++}(e)=\Gamma^{h}_{++}(x)$. Therefore, the unique hyperbolicity
cone of $h$ can simply be expressed as $\Gamma^{h}_{+}$.

The hyperbolic polynomials have similarities to determinant polynomials of
matrices, as they both can be used to define trace, norm, and eigenvalues.
Given a hyperbolic polynomial $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ and any
vector $e\in\Gamma^{h}_{++}$, we can define a norm with respect to $h(x)$ and
$e$ as follows: for any $x\in\mathbb{R}^{m}$, its _hyperbolic norm_
$\|x\|_{h}$ is equal to the largest root (in absolute value) of the linear
restriction polynomial $h(te-x)\in\mathbb{R}[t]$. Similar to the eigenvalues
of matrices, we define the _hyperbolic eigenvalues_ of $x$ to be the $d$ roots
of $h(te-x)$, denoted by $\lambda_{1}(x)\geq\cdots\geq\lambda_{d}(x)$. We can
also define the _hyperbolic trace_ and the _hyperbolic rank_ :

$\displaystyle\operatorname{tr}_{h}[x]:=\sum_{i=1}^{d}\lambda_{i}(x),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ \leavevmode\nobreak\
\operatorname{rank}(x)_{h}:=|\\{i\in[d]:\lambda_{i}(x)\neq 0\\}|.$

Recall that both Theorem 1.3 and Theorem 1.4 upper-bound the spectral norm of
the sum $\|\sum_{i=1}^{n}\xi_{i}v_{i}v_{i}^{\top}\|$. In the setting of
hyperbolic polynomials, we should upper bound the hyperbolic norm
$\|\sum_{i=1}^{n}\xi_{i}v_{i}\|_{h}$ for vectors $v_{1},\dots,v_{n}$ in the
hyperbolicity cone, which is the set of vectors with all non-negative
hyperbolic eigenvalues.

Our main results are as follows:

######  Theorem 1.5 (Main Result I, informal statement of Theorem B.1,
hyperbolic version of Theorem 1.4, [KLS20]).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a hyperbolic polynomial in
direction $e\in\mathbb{R}^{m}$. Let $v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be
$n$ vectors in the closed hyperbolicity cone. Let $\xi_{1},\dots,\xi_{n}$ be
$n$ independent random variables with finite supports and
$\operatorname*{{\mathbb{E}}}[\xi_{i}]=\mu_{i}$ and
$\operatorname*{{\bf{Var}}}[\xi_{i}]=\tau_{i}^{2}$. Suppose
$\sigma:=\|\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\|_{h}$.
Then there exists an assignment $(s_{1},\dots,s_{n})$ with $s_{i}$ in the
support of $\xi_{i}$ for all $i\in[n]$, such that

$\displaystyle\Big{\|}\sum_{i=1}^{n}(s_{i}-\mu_{i})v_{i}\Big{\|}_{h}\leq
4\sigma.$

We remark that Theorem 1.5 does not require the isotropic position condition
of $v_{1},\cdots,v_{n}$ as in [Brä18]. In addition, we only need the sum of
$\operatorname{tr}_{h}[v_{i}]v_{i}$’s hyperbolic norm to be bounded, while
[Brä18]’s result requires each vector’s trace to be bounded individually.

We would also like to note that the class of hyperbolic polynomials is much
broader than that of determinant polynomials, which were used in the original
Kadison-Singer-type theorems. Lax conjectured in [Lax57] that every 3-variate
hyperbolic/real-stable polynomial could be represented as a determinant
polynomial, this was later resolved in [HV07, LPR05]. However, the Lax
conjecture is false when the number of variables exceeds $3$, as demonstrated
in [Brä11, BVY14] with counterexamples of hyperbolic/real-stable polynomials
$h(x)$ for which even $(h(x))^{k}$ cannot be represented by determinant
polynomials for any $k>0$.

Our second main result considers the setting where the random vectors are not
independent, but instead, sampled from a strongly Rayleigh distribution. We
say a distribution $\mu$ over the subsets of $[n]$ is _strongly Rayleigh_ if
its generating polynomial
$g_{\mu}(z):=\sum_{S\subseteq[n]}\mu(S)z^{S}\in\mathbb{R}[z_{1},\dots,z_{n}]$
is a _real-stable polynomial_ , which means $g_{\mu}(z)$ does not have any
root in the upper-half of the complex plane, i.e., $g_{\mu}(z)\neq 0$ for any
$z\in\operatorname*{\mathbb{C}}^{n}$ with $\Re(z)\succ 0$.

######  Theorem 1.6 (Main Result II, informal statement of Theorem C.1
hyperbolic version of Theorem 1.2, [AO14]).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote hyperbolic polynomial in
direction $e\in\mathbb{R}^{m}$. Let $\mu$ be a homogeneous strongly Rayleigh
probability distribution on $[n]$ such that the marginal probability of each
element is at most $\epsilon_{1}$.

Suppose $v_{1},\cdots,v_{n}\in\Gamma_{+}^{h}$ are in the hyperbolicity cone of
$h$ such that $\sum_{i=1}^{n}v_{i}=e$, and for all $i\in[n]$,
$\|v_{i}\|_{h}\leq\epsilon_{2}$. Then there exists $S\subseteq[n]$ in the
support of $\mu$, such that

$\displaystyle\Big{\|}\sum_{i\in S}v_{i}\Big{\|}_{h}\leq
4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}.$

It is worth mentioning that the previous paper [KLS20, AO14] focused on the
determinant polynomial, leaving the question of whether their techniques could
be extended to the hyperbolic/real-stable setting unresolved. In our paper, we
address this gap by developing new techniques specifically tailored to
hyperbolic polynomials.

In addition, we follow the results from [AOSS18] and give an algorithm that
can find the approximate solutions of both Theorem 1.5 and Theorem 1.6 in time
sub-exponential to $m$:

######  Proposition 1.7 (Sub-exponential algorithm for Theorem 1.5, informal
statement of Corollary D.10 ).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a hyperbolic polynomial with
direction $e\in\mathbb{R}^{m}$. Let $v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be
$n$ vectors in the hyperbolicity cone $\Gamma_{+}^{h}$ of $h$. Suppose
$\sigma=\|\sum_{i=1}^{n}\operatorname{tr}_{h}[v_{i}]v_{i}\|_{h}$.

Let $\mathcal{P}$ be the interlacing family used in the proof of Theorem 1.6.
Then there exists an sub-exponential time algorithm
$\mathrm{KadisonSinger}(\delta,\mathcal{P})$, such that for any $\delta>0$, it
returns a sign assignment $(s_{1},\cdots,s_{n})\in\\{\pm 1\\}^{n}$ satisfying

$\displaystyle\Big{\|}\sum_{i=1}^{n}s_{i}u_{i}\Big{\|}_{h}\leq
4(1+\delta)\sigma.$

######  Proposition 1.8 (Sub-Exponential algorithm for Theorem 1.6, informal
statement of Corollary D.14 ).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a hyperbolic polynomial in
direction $e\in\mathbb{R}^{m}$. Let $\mu$ be a homogeneous strongly Rayleigh
probability distribution on $[n]$ such that the marginal probability of each
element is at most $\epsilon_{1}$, and let
$v_{1},\cdots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors such that
$\sum_{i=1}^{n}v_{i}=e$, and for all $i\in[n]$,
$\|v_{i}\|_{h}\leq\epsilon_{2}$.

Let $\mathcal{Q}$ be the interlacing family used in the proof of Theorem 1.6.
Then there exists an sub-exponential time algorithm
$\mathrm{KadisonSinger}(\delta,\mathcal{Q})$, such that for any $\delta>0$, it
returns a set $S$ in the support of $\mu$ satisfying

$\displaystyle\Big{\|}\sum_{i\in
S}u_{i}\Big{\|}_{h}\leq(1+\delta)\cdot\left(4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}\right).$

##  2 Related work

#### Real-Stable Polynomials

Real-stability is an important property for multivariate polynomials. In
[BB09], the authors used the real-stability to give a unified framework for
Lee-Yang type problems in statistical mechanics and combinatorics. Real-stable
polynomials are also related to the permanent. Gurvits [Gur07] proved the Van
der Waerden conjecture, which conjectures that the permanent of $n$-by-$n$
doubly stochastic matrices are lower-bounded by $n!/n^{n}$, via the capacity
of real-stable polynomials. Recently, [GL21] improved the capacity lower bound
for real-stable polynomials, which has applications in matrix scaling and
metric TSP. In addition, real-stable polynomials are an important tool in
solving many counting and sampling problems [NS16, AOR16, AO17, SV17, AOSS16,
AMOV18, AOV18, ALOV19, ALO+21].

#### Hyperbolic Polynomials

Hyperbolic polynomial was originally defined to study the stability of partial
differential equations [Går51, Hor83, Kry95]. In theoretical computer science,
Güler [Gül97] first introduced hyperbolic polynomial for optimization
(hyperbolic programming), which is a generalization of LP and SDP. Later, a
few algorithms [Ren06, MT14, RS14, Ren16, NP18, Ren19] were designed for
hyperbolic programming. On the other hand, a significant effort has been put
into the equivalence between hyperbolic programming and SDP, which is closely
related to the “Generalized Lax Conjecture” (which conjectures that every
hyperbolicity cone is spectrahedral) and its variants [HV07, LPR05, Brä14,
KPV15, Sau18, Ami19, RRSW19].

#### Strongly Rayleigh Distribution

The strongly Rayleigh distribution was introduced by [BBL09]. The authors also
proved numerous basic properties of strongly Rayleigh distributions, including
negative association, and closure property under operations such as
conditioning, product, and restriction to a subset. [PP14] proved a
concentration result for Lipschitz functions of strongly Rayleigh variables.
[KS18] showed a matrix concentration for strongly Rayleigh random variables,
which implies that adding a small number of uniformly random spanning trees
gives a graph spectral sparsifier.

Strongly Rayleigh distribution also has many algorithmic applications. [AOR16]
exploited the negative dependence property of homogeneous strongly Rayleigh
distributions, and designed efficient algorithms for generating approximate
samples from Determinantal Point Process using Monte Carlo Markov Chain. The
strongly Rayleigh property of spanning tree distribution is a key component
for improving the approximation ratios of TSP [KKO20, KKO21] and $k$-edge
connected graph problem [KKOZ21].

#### Other generalizations of the Kadison-Singer-type results

The upper bound of the rank-one Kadison-Singer theorem was improved by
[BCMS19, RL20]. [AB20] further extended [RL20]’s result to prove a real-stable
version of Anderson’s paving conjecture. However, they used a different norm
for real-stable polynomials, and hence their results and ours are
incomparable. In the high-rank case, [Coh16a] also proved a Kadison-Singer
result for high-rank matrices. [SZ22] relaxed [Brä18]’s result to the vectors
in sub-isotropic position. In addition, they proved a hyperbolic Spencer
theorem for constant-rank vectors.

Another direction of generalizing the Kadison-Singer-type result is to relax
the $\\{+1,-1\\}$-coloring to $\\{0,1\\}$-coloring, which is called the one-
sided version of Kadison-Singer problem in [Wea04]. More specifically, given
$n$ isotropic vectors $v_{1},\dots,v_{n}\in\mathbb{R}^{m}$ with norm
$\frac{1}{\sqrt{N}}$, the goal is to find a subset $S\subset[n]$ of size $k$
such that $\|\sum_{i\in S}v_{i}v_{i}^{\top}\|\leq\frac{k}{n}+O(1/\sqrt{N})$.
Unlike the original Kadison-Singer problem, Weaver [Wea04] showed that this
problem can be solved in polynomial time. Very recently, Song, Xu and Zhang
[SXZ22] improved the time complexity of the algorithm via an efficient inner
product search data structure.

#### Applications of Kadison-Singer Problem

There are many interesting results developed from the Kadison-Singer theorem.
In spectral graph theory, [HO14] exploited the same proof technique of
interlacing families to show a sufficient condition of the spectrally thin
tree conjecture. [AO14] used the strongly-Rayleigh extension of Kadison-Singer
theorem to show a weaker sufficient condition. Based on this result, [AO15]
showed that any $k$-edge-connected graph has an
$O(\frac{\log\log(n)}{k})$-thin tree, and gave a
$\operatorname{poly}(\log\log(n))$-integrality gap of the asymmetric TSP.
[MSS18, Coh16b] used the Kadison-Singer theorem to construct bipartite
Ramanujan graphs of all sizes and degrees. In the network design problem,
[LZ20] exploited the result in [KLS20], and built a spectral rounding
algorithm for the general network design convex program, which has
applications in weighted experimental design, spectral network design, and
additive spectral sparsifier.

##  3 Proof Overview

###  3.1 Hyperbolic Deviations

In this section, we will sketch the proof of our hyperbolic generalization of
the Kadison-Singer theorem (Theorem 1.5). We will use the same strategy as the
original Kadison-Singer theorem (Theorem 1.1) in [MSS15a, MSS15b], following
three main technical steps.

For simplicity, we assume that the random variables
$\xi_{1},\dots,\xi_{n}\in\\{\pm 1\\}$ are independent Rademacher random
variables, i.e., $\Pr[\xi_{i}=1]=\frac{1}{2}$ and
$\Pr[\xi_{i}=-1]=\frac{1}{2}$ for all $i\in[n]$.

To generalize the Kadison-Singer statement into the hyperbolic norm, one main
obstacle is to define the variance of the hyperbolic norm of the sum of random
vectors $\sum_{i=1}^{n}\xi_{i}v_{i}$. In the determinant polynomial case, each
$v_{i}$ corresponds to a rank-1 matrix $u_{i}u_{i}^{*}$, and it is easy to see
that the variance of the spectral norm is
$\|\sum_{i=1}^{n}(u_{i}u_{i}^{*})^{2}\|$. However, there is no analog of
“matrix square” in the setting of hyperbolic/real-stable polynomials. Instead,
we define the _hyperbolic variance_ :

$\left\|\sum_{i=1}^{n}\operatorname{tr}_{h}[v_{i}]v_{i}\right\|_{h}$

in terms of the hyperbolic trace, and show that _four hyperbolic deviations
suffice_.

#### Defining interlacing family of characteristic polynomials.

In the first step, we construct a family of _characteristic polynomials_
$\\{p_{s}:s\in\\{\pm 1\\}^{t},t\in\\{0,\cdots,n\\}\\}$ as follows: For each
${\bf s}\in\\{\pm 1\\}^{n}$, define the leaf-node-polynomial:

$\displaystyle p_{{\bf s}}(x):=\left(\prod_{i=1}^{n}p_{i,s_{i}}\right)\cdot
h\left(xe+\sum_{i=1}^{n}s_{i}v_{i}\right)\cdot
h\left(xe-\sum_{i=1}^{n}s_{i}v_{i}\right),$

and for all $\ell\in\\{0,\dots,n-1\\}$, ${\bf s^{\prime}}\in\\{\pm
1\\}^{\ell}$, we construct an inner node with a polynomial that corresponds to
the bit-string $\mathbf{s}^{\prime}$:

$\displaystyle p_{{\bf s^{\prime}}}(x):=\sum_{{\bf t}\in\\{\pm
1\\}^{n-\ell}}p_{({\bf s^{\prime}},{\bf t})}(x).$

where $({\bf s^{\prime}},{\bf t})\in\\{\pm 1\\}^{n}$ is the bit-string
concatenated by ${\bf s^{\prime}}$ and ${\bf t}$.

We will then show that the above family of characteristic polynomials forms an
_interlacing family_ (see Lemma B.6 for detail) . By basic properties of
interlacing family, we can always find a leaf-root-polynomial $p_{s}$ (where
$s\in\\{\pm 1\\}^{n}$) whose largest root is upper bounded by the largest root
of the top-most polynomial.

$\displaystyle
p_{\emptyset}(x)=\operatorname*{{\mathbb{E}}}_{\xi_{1},\cdots,\xi_{n}}\left[h\Big{(}xe+\sum_{i=1}^{n}\xi_{i}v_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{n}\xi_{i}v_{i}\Big{)}\right].$

(we call $p_{\emptyset}$ to be the _mixed characteristic polynomial_). Notice
that by rewriting the largest root of $p_{s}$ to be the expected hyperbolic
norm of $\sum_{i=1}^{n}s_{i}v_{i}$, we get that

$\displaystyle\lambda_{\max}(p_{\emptyset})=\left\|\sum_{i=1}^{n}s_{i}v_{i}\right\|_{h}.$
(1)

(See Corollary B.7 for a formal statement).

Also, we will take $s\in\\{\pm 1\\}^{n}$ as the corresponding sign assignment
in the main theorem (Theorem 1.5) It then suffices to upper-bound the largest
root of the mixed characteristic polynomial.

#### From mixed characteristic polynomial to multivariate polynomial.

In the second step, we will show that the mixed characteristic polynomial that
takes the average on $n$ random variables

$\displaystyle
p_{\emptyset}(x)=\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{n}}\left[h\Big{(}xe+\sum_{i=1}^{n}\xi_{i}v_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{n}\xi_{i}v_{i}\Big{)}\right]$

is equivalent to a polynomial with $n$ extra variables $z_{1},\cdots,z_{n}$:

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\Bigg{|}_{z=0}\left(h\Big{(}xe+\sum_{i=1}^{n}z_{i}v_{i}\Big{)}\right)^{2}.$
(2)

(See Lemma B.8 for more detail.) Thus, we can reduce the upper bound of
$\chi_{\max}(p_{\emptyset})$ to an upper bound of the largest root in (2). The
latter turns out to be easier to estimate with the help of a barrier argument
[MSS15b].

To show such equivalence holds, we use induction on the random variables
$\xi_{1},\dots,\xi_{n}$. More specifically, we start from $\xi_{1}$ and are
conditioned on any fixed choice of $\xi_{2},\dots,\xi_{n}$. We prove that
taking expectation over $\xi_{1}$ is equivalent to applying the operator
$(1-\frac{\partial^{2}}{\partial z_{1}^{2}})$ to the polynomial

$\displaystyle\left(h(xe+z_{1}v_{1}+\sum_{i=2}^{n}\xi_{i}v_{i})\right)^{2}$

and setting $z_{1}=0$. Here we use the relation between expectation and the
second derivatives: for any Rademacher random variable $\xi$,

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi}[h(x_{1}-\xi v)\cdot
h(x_{2}+\xi
v)]=\left(1-\frac{1}{2}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\right)\Bigg{|}_{t=0}h(x_{1}+tv)h(x_{2}+tv).$

Repeating this process and removing one random variable at a time. After $n$
iterations, we obtain the desired multivariate polynomial.

We also need to prove the real-rootedness of the multivariate polynomial (Eqn.
(2)). We first consider an easy case where $h$ itself is a real-stable
polynomial, as in the determinant polynomial case. Then the real-rootedness
easily follows from the closure properties of the real-stable polynomial (see
Fact A.5) . More specifically, we can show that
$(h(xe+\sum_{i=1}^{n}z_{i}v_{i}))^{2}$ is also a real-stable polynomial.
Furthermore, applying the operators
$(1-\frac{1}{2}\frac{\partial^{2}}{\partial z_{i}^{2}})$ and restricting $z=0$
preserve the real-stability. Therefore, the multivariate polynomial is a
univariate real-stable polynomial, which is equivalent to being real-rooted.

Next, we show that when $h$ is a hyperbolic polynomial, the multivariate
polynomial (Eqn. (2)) is also real-rooted. our approach is to show that the
linear restriction of $h$: $h(xe+\sum_{i=1}^{n}z_{i}v_{i})$ is a real-stable
polynomial in $\mathbb{R}[x,z_{1},\dots,z_{n}]$. A well-known test for real-
stability is that if for any $a\in\mathbb{R}_{>0}^{n+1},b\in\mathbb{R}^{n+1}$,
the one-dimensional restriction $p(at+b)\in\mathbb{R}[t]$ is non-zero and
real-rooted, then $p(x)$ is real-stable. We test
$h(xe+\sum_{i=1}^{n}z_{i}v_{i})$ by restricting to $at+b$, and get the
following polynomial:

$\displaystyle
h\Big{(}(a_{1}e+\sum_{i=1}^{n}a_{i+1}v_{i})t+y\Big{)}\in\mathbb{R}[t],$

where $y$ is a fixed vector depending on $b$. Since $a_{i}>0$ for all
$i\in[n+1]$ and $e,v_{1},\dots,v_{n}$ are vectors in the hyperbolicity cone,
it implies that the vector $a_{1}e+\sum_{i=1}^{n}a_{i+1}v_{i}$ is also in the
hyperbolicity cone. Then, by the definition of hyperbolic polynomial, we
immediately see that $h((a_{1}e+\sum_{i=1}^{n}a_{i+1}v_{i})t+y)$ is real-
rooted for any $a\in\mathbb{R}_{>0}^{n+1}$ and $b\in\mathbb{R}^{n+1}$. Hence,
we can conclude that the restricted hyperbolic polynomial
$h(xe+\sum_{i=1}^{n}z_{i}v_{i})$ is real-stable and the remaining proof is the
same as the real-stable case.

#### Applying barrier argument.

Finally, we use _barrier argument_ to find an “upper barrier vector” whose
components lie above any roots of multivariate polynomial can take. In
particular, we consider the multivariate polynomial
$P(x,z)=(h(xe+\sum_{i=1}^{n}z_{i}v_{i}))^{2}$. Define the _barrier function_
of any variable $i\in[n]$ as the following:

$\displaystyle\Phi^{i}_{P}(\alpha(t),-\delta)=\frac{\partial_{z_{i}}P(x,z)}{P(x,z)}\Big{|}_{x=\alpha(t),z=-\mathbf{\delta}},$

where $\delta\in\mathbb{R}^{n}$ where
$\delta_{i}=t\operatorname{tr}_{h}[v_{i}]$ for $i\in[n]$ and $\alpha(t)>t$ is
a parameter that depends on $t$.

As a warm-up, consider the case when $\sigma=1$ and assuming
$\|\sum_{i=1}^{n}\operatorname{tr}_{h}[v_{i}]v_{i}\|_{h}\leq 1$. It is easy to
show that $(\alpha(t),-\delta)$ is an upper barrier of $P$, from the linearity
of the hyperbolic eigenvalues and the assumption. Next, we upper-bound the
barrier function’s value at $(\alpha(t),-\delta)$. When $h$ is a determinant
polynomial, this step is easy because the derivative of $\log\det$ is the
trace of the matrix. For a general hyperbolic polynomial, we will rewrite the
partial derivative $\partial_{z_{i}}$ as a directional derivative $D_{v_{i}}$
and get

$\displaystyle\Phi^{i}_{P}(\alpha(t),-\delta)=2\cdot\frac{(D_{v_{i}}h)(\alpha
e-te+t(e-\sum_{j=1}^{n}\operatorname{tr}_{h}[v_{j}]v_{j}))}{h(\alpha
e-te+t(e-\sum_{j=1}^{n}\operatorname{tr}_{h}[v_{j}]v_{j}))}.$

We observe that our assumption
$\|\sum_{i=1}^{n}\operatorname{tr}_{h}[v_{i}]v_{i}\|_{h}\leq 1$ implies that
$e-\sum_{j=1}^{n}\operatorname{tr}_{h}[v_{j}]v_{j}\in\Gamma_{+}^{h}$. By the
concavity of the function $\frac{h(x)}{D_{v_{i}}h(x)}$ in the hyperbolicity
cone, we can prove that

$\displaystyle\Phi^{i}_{P}(\alpha(t),-\delta)\leq\frac{2\operatorname{tr}_{h}[v_{i}]}{\alpha(t)-t}.$

Now, we can apply the barrier update lemma in [KLS20] (Lemma A.23) with
$\alpha(t)=2t=4$ to show that

$\displaystyle\Phi^{j}_{(1-\frac{1}{2}\partial_{z_{i}}^{2})P}(4,-\mathbf{\delta}+\delta_{i}{\bf
1}_{i})\leq\Phi_{P}^{j}(4,-\mathbf{\delta}).$

In other words, the partial differential operator
$(1-\frac{1}{2}\partial_{z_{i}}^{2})$ shifts the upper-barrier by
$(0,\cdots,0,\delta_{i},0,\cdots,0)$. Using induction for the variables
$\delta_{1},\cdots,\delta_{n}$, we can finally finally get an upper-barrier of

$\displaystyle(4,-\delta+\sum_{i=1}^{n}\delta_{i}{\bf 1}_{i})=(4,0,\dots,0),$

which implies that $(4,0,\dots,0)$ is above the roots of

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\left(h\Big{(}xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\right)^{2}$
(3)

(See Lemma B.14 for detail).

A challenge in this process is ensuring that the barrier function remains
nonnegative. To achieve this, we use the multidimensional convexity of the
hyperbolic barrier function as established in [Tao13] (Lemma A.25) . For cases
where $\sigma\neq 1$, this requirement is satisfied through a simple scaling
argument.

Combining the above three steps together, we can prove that
$\Pr_{\xi_{1},\cdots,\xi_{n}}[\|\sum_{i=1}^{n}\xi_{i}v_{i}\|_{h}\leq
4\sigma]>0$ for vectors $v_{1},\dots,v_{n}$ in the hyperbolicity cone with
$\|\sum_{i=1}^{n}\operatorname{tr}_{h}[v_{i}]v_{i}\|_{h}=\sigma^{2}$. The
complete proof can be found in Appendix B.

###  3.2 Generalization to Strongly Rayleigh Distributions

Our main technical contribution to Theorem 1.6 is a more universal and
structured method to characterize the mixed characteristic polynomial. Define
the mixed characteristic polynomial as

$\displaystyle q_{S}(x)=\mu(S)\cdot h\left(xe-\sum_{i\in S}v_{i}\right).$ (4)

we want to show that it is equivalent to the restricted multivariate
polynomial:

$\displaystyle\prod_{i=1}^{n}(1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}\in\mathbb{R}[x,z_{1},\cdots,z_{n}].$ (5)

Although Eqn. (4) and Eqn. (5) are the hyperbolic generalization of [AO14], we
are unable to apply the previous techniques. This is because [AO14] computes
the mixed characteristic polynomial explicitly, which heavily relies on the
fact that the characteristic polynomial is a determinant. It is unclear how to
generalize this method to hyperbolic/real-stable characteristic polynomials.

The key step in [AO14] is to show the following equality between mixed
characteristic polynomial and multivariate polynomial:

$\displaystyle
x^{d_{\mu}-d}\cdot\operatorname*{{\mathbb{E}}}_{S\sim\mu}\left[\det\left(x^{2}I-\sum_{i\in
S}2v_{i}v_{i}^{\top}\right)\right]$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}(1-\partial_{z_{i}}^{2})\left(g_{\mu}(x{\bf
1}+z)\cdot\det(xI+\sum_{i=1}^{n}z_{i}v_{i}v_{i}^{\top})\right)\Bigg{|}_{z={\bf
0}}$

where $d_{\mu}$ is the degree of the homogeneous strongly-Rayleigh
distribution $\mu$ (i.e. the degree of $g_{\mu}$), and $m$ is the dimension of
$v_{i}$.

Then they expand the right-hand side to get:

$\displaystyle{\rm RHS}=$ $\displaystyle\leavevmode\nobreak\
\sum_{k=0}^{m}(-1)^{k}x^{d_{\mu}+m-2k}\sum_{S\in{\binom{[n]}{k}}}\Pr_{T\sim\mu}[S\subseteq
T]\cdot\sigma_{k}(\sum_{i\in S}2v_{i}v_{i}^{\top})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
x^{d_{\mu}-m}\cdot\operatorname*{{\mathbb{E}}}_{S\sim\mu}\left[\det\left(x^{2}I-\sum_{i\in
S}2v_{i}v_{i}^{\top}\right)\right]={\rm LHS},$

where $\sigma_{k}(M)$ equals to the sum of all $k\times k$ principal minors of
$M\in\mathbb{R}^{m\times m}$. The first step comes from expanding the product
$\prod_{i=1}^{n}(1-\partial^{2}z_{i})$, and the second step comes from that

$\displaystyle\det(x^{2}I-\sum_{i=1}^{n}v_{i}v_{i}^{\top})=\sum_{k=0}^{m}(-1)^{2k}x^{2m-2k}\sum_{S\in\binom{[n]}{k}}\sigma_{k}(\sum_{i\in
S}v_{i}v_{i}^{\top}).$

The naive generalization of a technique to hyperbolic/real-stable polynomial
$h$ faces challenges. One such challenge is the absence of an explicit form
for $h$, unlike in the case of $h=\det$ where the determinant can be expressed
as a combination of minors. This lack of a well-defined minor presents
difficulty in rewriting the hyperbolic/real-stable polynomial. To tackle this
issue, we devised a new and structured proof that relies on induction,
offering a novel solution to this problem.

#### Inductive step.

We first rewrite the expectation over the Strongly-Rayleigh distribution
$T\sim\mu$ as follows:

$\displaystyle x^{d_{\mu}}\cdot
2^{-n}\cdot\operatorname*{{\mathbb{E}}}_{T\sim\mu}[h(xe-\sum_{i\in T}v_{i})]=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{2}\operatorname*{{\mathbb{E}}}_{\xi_{2},\cdots,\xi_{n}\sim\\{0,1\\}^{n-1}}\Big{[}(1-\partial_{z_{1}})h(x_{2}+z_{1}v_{1})x\partial_{z_{1}}g_{2}(x+z_{1})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+h(x_{2})(1-x\partial_{z_{1}})g_{2}(x+z_{1})\Big{|}_{z_{1}=0}\Big{]}$

where $g_{2}$ is defined as

$\displaystyle g_{2}(t):=$ $\displaystyle\leavevmode\nobreak\
x^{\sum_{i=2}^{n}\xi_{i}}\cdot$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\prod_{i=2}^{n}\Big{(}\xi_{i}\partial_{z_{i}}+(1-\xi_{i})(1-x\partial_{z_{i}})\Big{)}g_{\mu}(t,x+z_{2},x+z_{3},\cdots,x+z_{n})\Big{|}_{z_{2},\dots,z_{n}=0}$

and $x_{2}=x^{2}e-\sum_{i=2}^{n}\xi_{i}v_{i}$. The main observation is that
the marginals of a homogeneous Strongly-Rayleigh distribution can be computed
from the derivatives of its generating polynomial (Fact C.4) .

Then, we can expand the term inside the expectation as

$\displaystyle(1-\frac{x}{2}\partial^{2}_{z_{1}})\Big{(}h(x_{2}+z_{1}v_{1})g_{2}(x+z_{1})\Big{)}\Big{|}_{z_{1}=0},$

using the fact that $\operatorname{rank}(v_{1})_{h}\leq 1$ and the degree of
$g_{2}(t)$ is at most 1.

Hence, we obtain our inductive step as

$\displaystyle x^{d_{\mu}}\cdot
2^{-n}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-\sum_{i=1}^{n}\xi_{i}v_{i})\right]$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{2}(1-\frac{x}{2}\partial_{z_{1}}^{2})\left(\operatorname*{{\mathbb{E}}}_{\xi_{2},\cdots,\xi_{n}}\Big{[}h(xe-\sum_{i=2}^{n}\xi_{i}v_{i}+z_{1}v_{1})\cdot
g_{2}(x+z_{1})\Big{]}\right)\Bigg{|}_{z_{1}=0}.$

#### Applying the step inductively.

Repeating the above process for $n$ times, we finally get

$\displaystyle
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]=\sum_{T\subseteq[n]}(-\frac{x}{2})^{|T|}\partial_{z^{T}}^{2}\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}.$

Then, we rewrite the partial derivatives as directional derivatives (see
Definition A.13 for detail) . For any subset $T\subseteq[n]$ of size $k$, we
have

$\displaystyle\leavevmode\nobreak\
(-\frac{x}{2})^{k}\partial_{z^{T}}^{2}\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ (-\frac{x}{2})^{k}\cdot
2^{k}\cdot\left(\prod_{i\in T}D_{v_{i}}\right)h(x^{2}e)\cdot
g_{\mu}^{(T)}(x{\bf 1}),$

where $g_{\mu}^{(T)}(x{\bf 1})=\prod_{i\in T}\partial_{z_{i}}g_{\mu}(x{\bf
1}+z)\Big{|}_{z=0}$. And by the homogeneity of $h$, it further equals to

$\displaystyle
x^{d}\cdot(-\frac{1}{2})^{k}\partial_{z^{T}}^{2}\left(h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\right)\Bigg{|}_{z=0}.$

Therefore, we prove the following formula that relates the characteristic
polynomial under SR distribution to the multivariate polynomial:

$\displaystyle
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]=x^{d}\cdot\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}.$

The complete proof can be found in Appendix C.

#### Roadmap.

We provide preliminary definitions and facts in Appendix A. In Appendix B, we
prove our first main result (Theorem 1.5), which is a hyperbolic
generalization of Kadison-Singer result for a weaker condition (sum of squares
of vectors is bounded). In Appendix C, we prove our second main result
(Theorem 1.6), which is a hyperbolic extension of the Kadison-Singer result
for strongly-Rayleigh distributions. We put the sub-exponential algorithm for
our main results in Appendix D. In Appendix E, we provide some examples of
real-stable and hyperbolic polynomials.

## References

  * [AB20] Kasra Alishahi and Milad Barzegar.  Paving property for real stable polynomials and strongly rayleigh processes.  arXiv preprint arXiv:2006.13923, 2020.
  * [ALO+21] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong.  Log-concave polynomials iv: approximate exchange, tight mixing times, and near-optimal sampling of forests.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 408–420, 2021.
  * [ALOV19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1–12, 2019.
  * [Ami19] Nima Amini.  Spectrahedrality of hyperbolicity cones of multivariate matching polynomials.  Journal of Algebraic Combinatorics, 50(2):165–190, 2019.
  * [AMOV18] Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V Vazirani.  Nash social welfare for indivisible items under separable, piecewise-linear concave utilities.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2274–2290. SIAM, 2018.
  * [AO14] Nima Anari and Shayan Oveis Gharan.  The kadison-singer problem for strongly rayleigh measures and applications to asymmetric tsp.  In arXiv preprint. https://arxiv.org/pdf/1412.1143.pdf, 2014\.
  * [AO15] Nima Anari and Shayan Oveis Gharan.  Effective-resistance-reducing flows, spectrally thin trees, and asymmetric tsp.  In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 20–39. IEEE, 2015.
  * [AO17] Nima Anari and Shayan Oveis Gharan.  A generalization of permanent inequalities and applications in counting and optimization.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 384–396, 2017.
  * [AOR16] Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei.  Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes.  In Conference on Learning Theory, pages 103–115. PMLR, 2016.
  * [AOSS16] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh.  Nash social welfare, matrix permanent, and stable polynomials.  arXiv preprint arXiv:1609.07056, 2016.
  * [AOSS18] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Nikhil Srivastava.  Approximating the largest root and applications to interlacing families.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1015–1028. SIAM, 2018.
  * [AOV18] Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35–46. IEEE, 2018.
  * [BB08] Julius Borcea and Petter Brändén.  Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized fischer products.  Duke Mathematical Journal, 143(2):205–223, 2008.
  * [BB09] Julius Borcea and Petter Brändén.  The lee-yang and pólya-schur programs. ii. theory of stable polynomials and applications.  Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1595–1631, 2009.
  * [BBL09] Julius Borcea, Petter Brändén, and Thomas Liggett.  Negative dependence and the geometry of polynomials.  Journal of the American Mathematical Society, 22(2):521–567, 2009\.
  * [BCMS19] Marcin Bownik, Pete Casazza, Adam W Marcus, and Darrin Speegle.  Improved bounds in weaver and feichtinger conjectures.  Journal für die reine und angewandte Mathematik (Crelles Journal), 2019(749):267–293, 2019.
  * [BGLS01] Heinz H Bauschke, Osman Güler, Adrian S Lewis, and Hristo S Sendov.  Hyperbolic polynomials and convex analysis.  Canadian Journal of Mathematics, 53(3):470–488, 2001.
  * [Brä10] Petter Brändén.  Notes on hyperbolicity cones.  Verfügbar unter https://math. berkeley. edu/~ bernd/branden. pdf, 2010.
  * [Brä11] Petter Brändén.  Obstructions to determinantal representability.  Advances in Mathematics, 226(2):1202–1212, 2011.
  * [Brä14] Petter Brändén.  Hyperbolicity cones of elementary symmetric polynomials are spectrahedral.  Optimization Letters, 8(5):1773–1782, 2014.
  * [Brä18] Petter Brändén.  Hyperbolic polynomials and the kadison-singer problem.  arXiv preprint arXiv:1809.03255, 2018.
  * [BVY14] Sam Burton, Cynthia Vinzant, and Yewon Youm.  A real stable extension of the vamos matroid polynomial.  arXiv preprint arXiv:1411.2038, 2014.
  * [Coh16a] Michael Cohen.  Improved spectral sparsification and Kadison-Singer for sums of higher-rank matrices.  In Banff International Research Station for Mathematical Innovation and Discovery. https://open.library.ubc.ca/cIRcle/collections/48630/items/1.0340957, 2016\.
  * [Coh16b] Michael B Cohen.  Ramanujan graphs in polynomial time.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 276–281. IEEE, 2016.
  * [CS07] Maria Chudnovsky and Paul Seymour.  The roots of the independence polynomial of a clawfree graph.  J. Combin. Theory Ser. B, 97(3):350–357, 2007.
  * [DG94] Jean-Pierre Dedieu and R. J. Gregorac.  Corrigendum: “Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?” [J. Pure Appl. Algebra 81 (1992), no. 3, 269–278; MR1179101 (93g:12001)] by Dedieu.  J. Pure Appl. Algebra, 93(1):111–112, 1994.
  * [Fel80] H. J. Fell.  On the zeros of convex combinations of polynomials.  Pacific J. Math., 89(1):43–50, 1980.
  * [Går51] Lars Gårding.  Linear hyperbolic partial differential equations with constant coefficients.  Acta Mathematica, 85:1–62, 1951.
  * [Går59] Lars Gårding.  An inequality for hyperbolic polynomials.  Journal of Mathematics and Mechanics, pages 957–965, 1959.
  * [GL21] Leonid Gurvits and Jonathan Leake.  Capacity lower bounds via productization.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 847–858, 2021.
  * [Gül97] Osman Güler.  Hyperbolic polynomials and interior point methods for convex programming.  Mathematics of Operations Research, 22(2):350–377, 1997.
  * [Gur07] Leonid Gurvits.  Van der waerden/schrijver-valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all.  arXiv preprint arXiv:0711.3496, 2007.
  * [HLJ09] F Reese Harvey and H Blaine Lawson Jr.  Hyperbolic polynomials and the dirichlet problem.  arXiv preprint arXiv:0912.5220, 2009.
  * [HO14] Nicholas JA Harvey and Neil Olver.  Pipage rounding, pessimistic estimators and matrix concentration.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 926–945. SIAM, 2014.
  * [Hor83] L Hormander.  The analysis of linear partial differential operators ii.  Grundlehren, 257, 1983.
  * [HV07] J William Helton and Victor Vinnikov.  Linear matrix inequality representation of sets.  Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 60(5):654–674, 2007.
  * [KKO20] Anna R Karlin, Nathan Klein, and Shayan Oveis Gharan.  An improved approximation algorithm for tsp in the half integral case.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 28–39, 2020.
  * [KKO21] Anna R Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved approximation algorithm for metric tsp.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 32–45, 2021.
  * [KKOZ21] Anna R Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang.  An improved approximation algorithm for the minimum $k$-edge connected multi-subgraph problem.  arXiv preprint arXiv:2101.05921, 2021.
  * [KLS20] Rasmus Kyng, Kyle Luh, and Zhao Song.  Four deviations suffice for rank 1 matrices.  In Advances in Mathematics. arXiv preprint arXiv:1901.06731, 2020\.
  * [KPV15] Mario Kummer, Daniel Plaumann, and Cynthia Vinzant.  Hyperbolic polynomials, interlacers, and sums of squares.  Mathematical Programming, 153(1):223–245, 2015.
  * [Kry95] N.V. Krylov.  On the general notion of fully nonlinear second-order elliptic equations.  Transactions of the American Mathematical Society, 347(3):857–895, 1995.
  * [KS59] Richard V Kadison and Isadore M Singer.  Extensions of pure states.  American journal of mathematics, 81(2):383–400, 1959.
  * [KS18] Rasmus Kyng and Zhao Song.  A matrix chernoff bound for strongly rayleigh distributions and spectral sparsifiers from a few random spanning trees.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 373–384. IEEE, 2018.
  * [Lax57] Peter D Lax.  Differential equations, difference equations and matrix theory.  Technical report, New York Univ., New York. Atomic Energy Commission Computing and Applied Mathematics Center, 1957.
  * [LPR05] Adrian Lewis, Pablo Parrilo, and Motakuri Ramana.  The lax conjecture is true.  Proceedings of the American Mathematical Society, 133(9):2495–2499, 2005.
  * [LZ20] Lap Chi Lau and Hong Zhou.  A spectral approach to network design.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 826–839, 2020.
  * [MSS15a] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava.  Interlacing families I: Bipartite Ramanujan graphs of all degrees.  Ann. of Math. (2), 182(1):307–325, 2015.
  * [MSS15b] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava.  Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem.  Ann. of Math. (2), 182(1):327–350, 2015.
  * [MSS18] A. Marcus, D. Spielman, and N. Srivastava.  Interlacing families iv: Bipartite ramanujan graphs of all sizes.  SIAM Journal on Computing, 47(6):2488–2509, 2018.
  * [MT14] Tor Myklebust and Levent Tunçel.  Interior-point algorithms for convex optimization based on primal-dual metrics.  arXiv preprint arXiv:1411.2129, 2014.
  * [NP18] Simone Naldi and Daniel Plaumann.  Symbolic computation in hyperbolic programming.  Journal of Algebra and Its Applications, 17(10):1850192, 2018.
  * [NS16] Aleksandar Nikolov and Mohit Singh.  Maximizing determinants under partition constraints.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 192–201, 2016.
  * [PP14] Robin Pemantle and Yuval Peres.  Concentration of lipschitz functionals of determinantal and other strong rayleigh measures.  Combinatorics, Probability and Computing, 23(1):140–160, 2014.
  * [Ren06] James Renegar.  Hyperbolic programs, and their derivative relaxations.  Foundations of Computational Mathematics, 6(1):59–79, 2006.
  * [Ren16] James Renegar.  “Efficient” subgradient methods for general convex optimization.  SIAM Journal on Optimization, 26(4):2649–2676, 2016.
  * [Ren19] James Renegar.  Accelerated first-order methods for hyperbolic programming.  Mathematical Programming, 173(1-2):1–35, 2019.
  * [RL20] Mohan Ravichandran and Jonathan Leake.  Mixed determinants and the kadison–singer problem.  Mathematische Annalen, 377(1):511–541, 2020.
  * [RRSW19] Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, and Benjamin Weitz.  Exponential lower bounds on spectrahedral representations of hyperbolicity cones.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2322–2332. SIAM, 2019.
  * [RS14] James Renegar and Mutiara Sondjaja.  A polynomial-time affine-scaling method for semidefinite and hyperbolic programming.  arXiv preprint arXiv:1410.6734, 2014.
  * [Sau18] James Saunderson.  A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone.  Optimization Letters, 12(7):1475–1486, 2018.
  * [Spe85] Joel Spencer.  Six standard deviations suffice.  Transactions of the American mathematical society, 289(2):679–706, 1985.
  * [SV17] Damian Straszak and Nisheeth K Vishnoi.  Real stable polynomials and matroids: Optimization and counting.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 370–383, 2017.
  * [SXZ22] Zhao Song, Zhaozhuo Xu, and Lichen Zhang.  Speeding up sparsification using inner product search data structures, 2022.
  * [SZ22] Zhao Song and Ruizhe Zhang.  Hyperbolic concentration, anti-concentration, and discrepancy.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [Tao13] Terence Tao.  Real stable polynomials and the kadison-singer problem.  https://terrytao.wordpress.com/2013/11/04/real-stable-polynomials-and-the-kadison-singer-problem/, 2013\.
  * [Tro15] Joel A. Tropp.  An introduction to matrix concentration inequalities.  Foundations and Trends® in Machine Learning, 8(1-2):1–230, 2015\.
  * [Wag11] David Wagner.  Multivariate stable polynomials: theory and applications.  Bulletin of the American Mathematical Society, 48(1):53–84, 2011\.
  * [Wea04] Nik Weaver.  The Kadison-Singer problem in discrepancy theory.  Discrete Math., 278(1-3):227–239, 2004.

##  Appendix A Preliminaries

We gather several basic linear algebraic and analytic facts in the following
subsections.

#### Notations.

For any positive integer $n$, we use $[n]$ to denote set $\\{1,2,\cdots,n\\}$.
We use $\mathbf{1}$ to denote the all-one vector and $\mathbf{1}_{i}$ to
denote the vector with one in the $i$-th coordinate and zero in other
coordinates.

###  A.1 Real-stable polynomials

######  Definition A.1.

A multivariate polynomial $p\in\operatorname*{\mathbb{C}}[x_{1},\cdots,x_{m}]$
is _stable_ if it has no zeros in the region
$\\{(x_{1},\dots,x_{m}):\operatorname{Im}(x_{i})>0\text{ for all }i\in[m]\\}$.
$p$ is _real stable_ if $p$ is stable and has real coefficients.

In the rest of this paper, we restrict our discussion into polynomials with
real coefficients.

######  Fact A.2.

We say a univariate polynomial $p\in\mathbb{R}[t]$ is real-rooted iff it is
real-stable.

######  Fact A.3 (Equivalent definition of real-stable polynomial).

A multivariate polynomial $p\in\mathbb{R}[x_{1},\cdots,x_{m}]$ is real stable
iff for any $a\in\mathbb{R}^{m}_{>0}$ and $b\in\mathbb{R}^{m}$, the univariate
polynomial $p(at+b)$ with respect to $t$ is not identically zero and is real-
rooted.

######  Lemma A.4 (Proposition 2.4, [BB08]).

If $A_{1},\dots,A_{n}$ are positive semidefinite symmetric matrices, then the
polynomial

$\displaystyle\det\left(\sum_{i=1}^{n}z_{i}A_{i}\right)$

is real stable.

We also need that real stability is preserved under product (see [BBL09]),
restricting variables to real values (see [Wag11, Lemma 2.4(d)]), and taking
$(1-\partial^{2}_{x_{i}})$ (see [AO14, Corollary 2.8]).

######  Fact A.5 (Closure operations of real-stable polynomials).

Let $p,q\in\mathbb{R}[x_{1},\dots,x_{m}]$ be two real stable polynomials. Then
the following operations preserve real-stability:

  * •

(Product) $p\cdot q$.

  * •

(Restriction to real values) For any $a\in\mathbb{R}$,
$p|_{x_{1}=a}=p(a,x_{2},\ldots,x_{m})\in\mathbb{R}[x_{2},\ldots,x_{m}]$.

  * •

(One minus second partial derivative) For any $c\in\mathbb{R}_{+},i\in[n]$,
$(1-c\cdot\partial_{x_{i}}^{2})p(x_{1},\dots,x_{n})$.

###  A.2 Hyperbolic polynomials

######  Definition A.6 (Hyperbolic polynomials).

A homogeneous polynomial $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ is hyperbolic
with respect to vector $e\in\mathbb{R}^{m}$ with $h(e)>0$, if for all
$x\in\mathbb{R}^{m}$, the univariate polynomial $t\mapsto h(te-x)$ only has
real roots.

Furthermore, if $h$ has degree $d$, fix any $x\in\mathbb{R}^{m}$ we can write

$\displaystyle h(te-x)=h(e)\prod_{i=1}^{d}(t-\lambda_{i}(x)),$

where $\lambda_{1}(x)\geq\lambda_{2}(x)\geq\cdots\geq\lambda_{d}(x)$ are the
real roots of the univariate polynomial $h(te-x)$. In particular,

$\displaystyle h(x)=h(e)\prod_{i=1}^{d}\lambda_{i}(x).$

We denote $\lambda_{i}(x)$ as the $i$-th eigenvalue of $x$.

######  Definition A.7 (hyperbolicity cone).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be a degree $d$ hyperbolic polynomial
with respect to $e\in\mathbb{R}^{m}$. For any $x\in\mathbb{R}^{m}$, let
$\lambda_{1}(x)\geq\cdots\geq\lambda_{d}(x)\in\mathbb{R}^{d}$ be the real
roots of $h(te-x)$. Define the hyperbolicity cone of $h$ as

$\displaystyle\Gamma_{++}^{h}:=\\{x\leavevmode\nobreak\ :\leavevmode\nobreak\
\lambda_{d}(x)>0\\}.$

Furthermore, define the closure of $\Gamma_{+}^{h}$ as

$\displaystyle\Gamma_{+}^{h}:=\\{x\leavevmode\nobreak\ :\leavevmode\nobreak\
\lambda_{d}(x)\geq 0\\}.$

######  Fact A.8.

For any $e\in\mathbb{R}^{m}_{>0}$ and any homogeneous real-stable polynomial
$h\in\mathbb{R}[x_{1},\cdots,x_{m}]$, we have $h$ is hyperbolic with respect
to $e$. In other words, $\mathbb{R}_{>0}^{m}\subseteq\Gamma_{+}^{h}$.

###### Proof.

For any $e\in\mathbb{R}^{m}_{>0}$ and for any $x\in\mathbb{R}^{m}$, by Fact
A.3 (with replacing $a$ by $e$ and $b$ by $x$), the uni-variate polynomial
$h(te-x)$ is real rooted. By Definition A.6 $h$ is hyperbolic with respect to
direction $e$. ∎

######  Definition A.9 (Hyperbolic trace, rank, and spectral norm).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be a degree $d$ homogeneous
hyperbolic polynomial with respect to $e\in\mathbb{R}^{m}$. For any
$x\in\mathbb{R}^{m}$, let
$\lambda_{1}(x)\geq\cdots\geq\lambda_{d}(x)\in\mathbb{R}^{d}$ be the real
roots of $h(te-x)$. Define

$\displaystyle\operatorname{tr}_{h}[x]:=\sum_{i=1}^{d}\lambda_{i}(x),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\operatorname{rank}(x)_{h}:=|\\{i\leavevmode\nobreak\ :\leavevmode\nobreak\
\lambda_{i}(x)\neq 0\\}|,$
$\displaystyle\|x\|_{h}:=\max_{i\in[d]}|\lambda_{i}(x)|=\max\\{\lambda_{1}(x),-\lambda_{d}(x)\\}.$

######  Fact A.10 (Hyperbolic norm in terms of largest root of characteristic
polynomial).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be a degree $d$ hyperbolic polynomial
with respect to $e\in\mathbb{R}^{m}$. For any $v_{1},\cdots
v_{m}\in\Gamma_{+}^{h}$ and any $s_{1},\cdots,s_{m}\in\mathbb{R}$, we have

$\displaystyle\left\|\sum_{i=1}^{m}s_{i}v_{i}\right\|_{h}=\lambda_{\max}\left(h\left(xe-\sum_{i=1}^{n}s_{i}v_{i}\right)\cdot
h\left(xe+\sum_{i=1}^{n}s_{i}v_{i}\right)\right)$

where $\lambda_{\max}(f(x))$ is the maximum root of $f(x)$.

###### Proof.

For any vector $v\in\mathbb{R}^{m}$, it is easy to see that the $i$-th largest
eigenvalue $\lambda_{i}(v)=-\lambda_{d-i+1}(-v)$. Then, we have

$\displaystyle\lambda_{\max}\left(h\left(xe-\sum_{i=1}^{n}s_{i}v_{i}\right)\cdot
h\left(xe+\sum_{i=1}^{n}s_{i}v_{i}\right)\right)=$
$\displaystyle\leavevmode\nobreak\
\max\left\\{\lambda_{1}\left(\sum_{i=1}^{m}s_{i}v_{i}\right),\lambda_{1}\left(-\sum_{i=1}^{m}s_{i}v_{i}\right)\right\\}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\max\left\\{\lambda_{1}\left(\sum_{i=1}^{m}s_{i}v_{i}\right),-\lambda_{d}\left(\sum_{i=1}^{m}s_{i}v_{i}\right)\right\\}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\left\|\sum_{i=1}^{m}s_{i}v_{i}\right\|_{h}.$

∎

######  Remark A.11.

It is useful to think of hyperbolic polynomials as generalizations of the
determinant polynomials. Let $X\in S^{n}(\mathbb{R})$ be a symmetric matrix.
Define $h:S^{n}(\mathbb{R})\mapsto\mathbb{R}$ as

$\displaystyle h(X)=\det(X).$

Then, $h$ is hyperbolic with respect to the identity matrix $I_{n}\in
S^{n}(\mathbb{R})$, since for all $X\in S^{n}(\mathbb{R})$, the roots of
$h(tI-X)$ are the eigenvalues of $X$, thus $h(tI-X)$ is real-rooted.

The basic concepts for hyperbolic polynomials in Definition A.7 and Definition
A.9 also have analogues in linear algebra. To illustrate them, let $h$ be the
determinant polynomial:

  * •

The hyperbolicity cone of $h$ is

$\displaystyle\Gamma_{+}^{h}=\\{X\in\mathbb{R}^{n\times n}\leavevmode\nobreak\
:\leavevmode\nobreak\ \lambda_{n}(X)>0\\}=\\{X\in\mathbb{R}^{n\times
n}\leavevmode\nobreak\ :\leavevmode\nobreak\ X\succ 0\\}.$

  * •

For all $X\in S^{n}(\mathbb{R})$, the hyperbolic trace of $X$ is

$\displaystyle\operatorname{tr}_{h}[X]=\sum_{i=1}^{n}\lambda_{i}(X)=\operatorname{tr}[X].$

  * •

For all $X\in S^{n}(\mathbb{R})$, the hyperbolic rank of $X$ is

$\displaystyle\operatorname{rank}_{h}(X)=|\\{i\leavevmode\nobreak\
:\leavevmode\nobreak\ \lambda_{i}(X)\neq 0\\}|=\operatorname{rank}(X).$

  * •

For all $X\in S^{n}(\mathbb{R})$, the hyperbolic spectral norm of $X$ is

$\displaystyle\|X\|_{h}=\max_{i\in[n]}|\lambda_{i}(X)|=\|X\|.$

here $\|X\|$ denotes the spectral norm of $X$.

######  Definition A.12 (Directional derivative).

Given a polynomial $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ and a vector
$v\in\mathbb{R}^{m}$, define the directional derivative of $h$ in direction
$v$ as

$\displaystyle D_{v}h:=\sum_{i=1}^{n}v_{i}\frac{\partial h}{\partial x_{i}}.$

######  Fact A.13 (Equivalent definition of directional derivative).

Given polynomial $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ and vectors
$x,v\in\mathbb{R}^{m}$,

$\displaystyle(D_{v}h)(x)=$ $\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}}{\mathrm{d}t}h(x+tv),$ (6) $\displaystyle(D_{v}^{2}h)(x)=$
$\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}h(x+tv).$ (7)

######  Fact A.14 (Directional derivative of hyperbolic polynomials).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a hyperbolic polynomial with
respect to $e\in\mathbb{R}^{m}$. Let $v_{1},\dots,v_{n}\in\mathbb{R}^{m}$ be
$n$ vectors such that $\forall i\in[n]$, $\operatorname{rank}_{h}(v_{i})\leq
1$. Then, for any $t\in\mathbb{R}$,

$\displaystyle(\prod_{i=1}^{m}D_{v_{i}}h)(te)=(\prod_{i=1}^{n}\partial_{z_{i}}h)(te+\sum_{i=1}^{n}z_{i}v_{i}).$

Moreover, for any $T\subseteq[m]$, we have

$\displaystyle(\prod_{i\in T}D_{v_{i}}h)(te)=(\prod_{i\in
T}\partial_{z_{i}}h)(te+\sum_{i=1}^{n}z_{i}v_{i})\Big{|}_{z=0}.$

######  Fact A.15 (First-order expansion of hyperbolic polynomial).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be any hyperbolic polynomial. For any
vectors $v_{1},\dots,v_{n}\in\mathbb{R}^{m}$ such that $\forall i\in[n]$,
$\operatorname{rank}_{h}(v_{i})\leq 1$, and for any real vector
$x\in\mathbb{R}^{m}$,

$\displaystyle
h(x\pm\sum_{i=1}^{n}v_{i})=\prod_{i=1}^{n}(1\pm\partial_{z_{i}})h(x+\sum_{i=1}^{n}z_{i}v_{i})\Bigg{|}_{z=0}.$

Furthermore, for any $S\subseteq[n]$,

$\displaystyle h(x\pm\sum_{i\in S}v_{i})=\prod_{i\in
S}(1\pm\partial_{z_{i}})h(x+\sum_{i=1}^{n}z_{i}v_{i})\Bigg{|}_{z=0}.$

###### Proof.

Prove by induction on $n$.

If $n=1$, we have

$\displaystyle h(x\pm v_{1})=(1\pm
D_{v_{1}})h(x)=(1\pm\partial_{z_{1}})h(x+z_{1}v_{1})\Big{|}_{z_{1}=0},$

which follows from $\operatorname{rank}_{h}(v_{1})\leq 1$.

Assume it holds for $n=k$.

When $n=k+1$, let $x^{\prime}=x\pm\sum_{i=1}^{k}v_{i}$. We have

$\displaystyle h(x\pm\sum_{i=1}^{k+1}v_{i})=$
$\displaystyle\leavevmode\nobreak\ h(x^{\prime}\pm v_{k+1})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
(1\pm\partial_{z_{k+1}})h(x^{\prime}+z_{k+1}v_{k+1})\Big{|}_{z_{k+1}=0}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
(1\pm\partial_{z_{k+1}})h(x+z_{k+1}v_{k+1}\pm\sum_{i=1}^{k}v_{i})\Big{|}_{z_{k+1}=0}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
(1\pm\partial_{z_{k+1}})\prod_{i=1}^{k}(1\pm\partial_{z_{i}})h(x+\sum_{i=1}^{k+1}z_{i}v_{i})\Big{|}_{z=0}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\prod_{i=1}^{k+1}(1\pm\partial_{z_{i}})h(x+\sum_{i=1}^{k+1}z_{i}v_{i})\Big{|}_{z=0},$

where the second step follows from $\operatorname{rank}_{h}(v_{k+1})\leq 1$,
the forth step follows from the induction hypothesis, and the last step
follows from the operators $(1\pm\partial_{z_{i}})$ and
$(1\pm\partial_{z_{j}})$ commute for $i\neq j\in[k+1]$.

Hence, the fact is proved. And for the furthermore part, it follows from the
remaining variables $z_{i}$ for $i\notin S$ will disappear when we set $z=0$.
∎

###  A.3 Interlacing families

We recall the definition and properties of interlacing families from [MSS15a].

######  Definition A.16 (Interlacing polynomials and common interlacing).

We say a real rooted polynomial $g(x)=C\prod_{i=1}^{n-1}(x-\alpha_{i})$
_interlaces_ the real rooted polynomial
$f(x)=C^{\prime}\prod_{i=1}^{n}(x-\beta_{i})$ if

$\displaystyle\beta_{1}\leq\alpha_{1}\leq\dots\leq\alpha_{n-1}\leq\beta_{n}.$

We say the polynomials $f_{1},\dots,f_{k}$ have a _common interlacing_ if
there is a polynomial $g$ that interlaces each of the $f_{i}$.

The following lemma relates the roots of a sum of polynomials to those of a
common interlacing.

######  Lemma A.17 (Lemma 4.2, [MSS15a]).

Let $f_{1},\dots,f_{k}$ be degree $d$ real rooted polynomials with positive
leading coefficients. Define

$\displaystyle f_{\emptyset}:=\sum_{i=1}^{k}f_{i}.$

If $f_{1},\dots,f_{k}$ have a common interlacing, then there exists an
$i\in[k]$ such that the largest root of $f_{i}$ is at most the largest root of
$f_{\emptyset}$.

######  Definition A.18 (Definition 4.3, [MSS15a]).

Let $S_{1},\dots,S_{n}$ be finite sets. For each choice of assignment
$(s_{1},\dots,s_{n})\in S_{1}\times\dots\times S_{n}$, let
$f_{s_{1},\dots,s_{n}}(x)$ be a real rooted degree $d$ polynomial with
positive leading coefficient. For a partial assignment $s_{1},\dots,s_{k}\in
S_{1}\times\dots\times S_{k}$ for $k<n$, we define

$f_{s_{1},\dots,s_{k}}:=\sum_{s_{k+1}\in S_{k+1},\dots,s_{n}\in
S_{n}}f_{s_{1},\dots,s_{k},s_{k+1},\dots,s_{n}}.$ (8)

Note that this is compatible with our definition of $f_{\emptyset}$ from Lemma
A.17. We say that the polynomials $\\{f_{s_{1},\dots,s_{n}}\\}$ form an
_interlacing family_ if for all $k=0,\dots,n-1$ and all
$(s_{1},\dots,s_{k})\in S_{1}\times\dots\times S_{k}$, the polynomials

$\displaystyle\Big{\\{}f_{s_{1},\cdots,s_{k},t}:\leavevmode\nobreak\ t\in
S_{k+1}\Big{\\}}$

have a common interlacing.

The following lemma relates the roots of the interlacing family to those of
$f_{\emptyset}$.

######  Lemma A.19 (Theorem 4.4, [MSS15a]).

Let $S_{1},\dots,S_{n}$ be finite sets and let $\\{f_{s_{1},\dots,s_{n}}\\}$
be an interlacing family. Then there exists some $(s_{1},\dots,s_{n})\in
S_{1}\times\dots\times S_{n}$ so that the largest root of
$f_{s_{1},\dots,s_{n}}$ is upper bounded by the largest root of
$f_{\emptyset}$.

Finally, we recall a relationship between real-rootedness and common
interlacings which has been discovered independently several times [DG94,
Fel80, CS07].

######  Lemma A.20 ([DG94, Fel80, CS07]).

Let $f_{1},\dots,f_{k}$ be univariate polynomials of the same degree with
positive leading coefficient. Then $f_{1},\dots,f_{k}$ have a common
interlacing if and only if $\sum_{i=1}^{k}\alpha_{i}f_{i}$ is real rooted for
all convex combinations $\alpha_{i}$, $\sum_{i=1}^{k}\alpha_{i}=1$.

###  A.4 Barrier method

######  Definition A.21 (Upper barrier of the roots of a polynomial).

For a multivariate polynomial $p(z_{1},\ldots,z_{n})$, we say
$z\in\mathbb{R}^{n}$ is above all roots of $p$ if for all
$t\in\mathbb{R}^{n}_{+}$,

$\displaystyle p(z+t)>0.$

We use $\mathbf{Ab}_{p}$ to denote the set of points which are above all roots
of $p$.

We use the barrier function as in [MSS15b] and [KLS20].

######  Definition A.22 (Barrier function).

For a multivariate polynomial $p$ and $z\in\mathbf{Ab}_{p}$, the barrier
function of $p$ in direction $i$ at $z$ is

$\displaystyle\Phi_{p}^{i}:=\frac{\partial_{z_{i}}p(z)}{p(z)}.$

We will make use of the following lemma that controls the deviation of the
roots after applying a second order differential operator. This lemma is a
slight variation of Lemma 5.3 in [KLS20].

######  Lemma A.23 (Lemma 5.3 of [KLS20]).

Suppose that $p(z_{1},\cdots,z_{m})$ is real stable and $z\in{\bf Ab}_{p}$.
For any $c\in[0,1]$ and $i\in[m]$, if

$\displaystyle\Phi_{p}^{i}(z)<\sqrt{1/c},$ (9)

then $z\in{\bf Ab}_{(1-c\cdot\partial_{z_{i}}^{2})p}$. If additionally for
$\delta>0$,

$\displaystyle
c\cdot\left(\frac{2}{\delta}\Phi_{p}^{i}(z)+(\Phi_{p}^{i}(z))^{2}\right)\leq
1,$ (10)

then, for all $j\in[m]$,

$\displaystyle\Phi^{j}_{(1-c\cdot\partial_{i}^{2})p}(z+\delta{\bf
1}_{i})\leq\Phi_{p}^{j}(z).$

######  Remark A.24.

We choose $c=1/2$ when we use the above lemma in Section B.4 and Section C.4.

######  Lemma A.25 (Multi-dimensional convexity, [Tao13]).

Let $p(z_{1},\ldots,z_{m})$ be a real stable polynomial of $m$ variables. For
any $i\in[m]$,

$\displaystyle(-1)^{k}\frac{\partial^{k}}{\partial
z_{j}^{k}}\Phi_{p}^{i}(x)\geq 0$

for all $k=0,1,2,\ldots$ and $x\in\mathbf{Ab}_{p}$.

##  Appendix B Hyperbolic Extension of Kadison-Singer for Standard Deviations

The goal of this section is to prove Theorem B.1:

######  Theorem B.1 (Formal statement of Theorem 1.5).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a hyperbolic polynomial with
respect to a hyperbolic direction $e\in\Gamma_{++}^{h}$, where
$\Gamma_{++}^{h}\subseteq\mathbb{R}^{m}$ is the hyperbolicity cone of $h$. Let
$\xi_{1},\cdots,\xi_{n}$ denote $n$ independent random variables with
$\operatorname*{{\mathbb{E}}}[\xi_{i}]=\mu_{i}$ and
$\operatorname*{{\bf{Var}}}[\xi]=\tau_{i}^{2}$. Let
$v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors such that $\forall
i\in[n]$, $\operatorname{rank}_{h}(v_{i})\leq 1$. Suppose

$\displaystyle\sigma^{2}:=\Big{\|}\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\Big{\|}_{h}.$

Then,

$\displaystyle\Pr_{\xi_{1},\cdots,\xi_{n}}\left[\Big{\|}\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i}\Big{\|}_{h}\leq
4\sigma\right]>0.$

We will introduce the preliminary facts in Section B.1. In Section B.2, we
define the family of hyperbolic characteristic polynomials and show that it
forms an interlacing family. Therefore, it remains to upper-bound the largest
root of the average of the interlacing polynomial family, i.e. the mixed
characteristic polynomial. We remark that we require a lemma that will be
proved later in Section B.3.

In Section B.3, we reduce the problem of upper-bounding the largest root of
the mixed characteristic polynomial to an easier task of upper-bounding the
largest root of a multivariate polynomial. In Section B.4, we upper bound the
largest root of the multivariate polynomial using multivariate barrier method.
Finally, in Section B.5, we prove Theorem B.1.

###  B.1 Preliminaries

In this section, we state several useful facts about hyperbolic polynomials.
We first introduce some important properties of the derivatives of hyperbolic
polynomial:

######  Theorem B.2 (Theorem 3.1 in [Brä18] and known in [Går59, BGLS01,
Ren06]).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be a hyperbolic polynomial and let
$v\in\Gamma_{+}$ be a vector such that $D_{v}h\not\equiv 0$. Then
1) $D_{v}h$ is hyperbolic with hyperbolicity cone containing $\Gamma_{++}$.
2) The polynomial $h(x)-y\cdot D_{v}h(x)\in\mathbb{R}[x,y]$ is hyperbolic with
hyperbolicity cone containing $\Gamma_{++}\times\\{y:y\leq 0\\}$. Further, we
have $(h(x)+y\cdot D_{v}h(x))\cdot(h(x)-y\cdot D_{v}h(x))\in\mathbb{R}[x,y]$
is hyperbolic with hyperbolicity cone containing $\Gamma_{++}\times\\{y:y\leq
0\\}$.
3) The rational function $x\rightarrow\frac{h(x)}{D_{v}h(x)}$ is concave on
$\Gamma_{++}$.

The following lemma correlates hyperbolic trace to directional derivative:

######  Fact B.3 (Correlation between hyperbolic trace and derivative).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a hyperbolic polynomial with
respect to $e\in\mathbb{R}^{m}$. For any $v\in\mathbb{R}^{m}$ and
$\alpha\in\mathbb{R}$, we have

$\displaystyle\operatorname{tr}_{h}[v]=\alpha\cdot\frac{D_{v}h(\alpha
e)}{h(\alpha e)}.$

###### Proof.

By Theorem B.2, $D_{v}h$ is hyperbolic, and thus is homogeneous. By Vieta’s
formula for the sum of roots of a polynomial, we have

$\displaystyle\operatorname{tr}_{h}[v]=\frac{D_{v}h(e)}{h(e)}$

It follows that $h$ and $D_{v}h$ are homogeneous, and the degree of $h$ is one
larger than that of $D_{v}h$. Therefore,

$\displaystyle\alpha\cdot\frac{D_{v}h(\alpha e)}{h(\alpha
e)}=\frac{D_{v}h(e)}{h(e)}=\operatorname{tr}_{h}[v].$

∎

######  Fact B.4.

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a hyperbolic polynomial with
respect to the direction $e\in\Gamma_{++}$ and let $\alpha>0$. For any
$M,v\in\Gamma_{+}$, we have

$\displaystyle\frac{D_{v}h(\alpha e+M)}{h(\alpha e+M)}\leq\frac{D_{v}h(\alpha
e)}{h(\alpha e)}.$

###### Proof.

It suffices to show

$\displaystyle\frac{h(\alpha e+M)}{D_{v}(\alpha e+M)}\geq\frac{h(\alpha
e)}{D_{v}h(\alpha e)}.$

By Theorem B.2, we know that rational function
$x\mapsto\frac{h(x)}{D_{v}h(x)}$ is concave on $\Gamma_{++}$. Then we know
that

$\displaystyle\frac{h(\alpha e+M)}{D_{v}(\alpha e+M)}\geq$
$\displaystyle\leavevmode\nobreak\ \frac{1}{2}\frac{h(2\alpha
e)}{D_{v}h(2\alpha e)}+\frac{1}{2}\frac{h(2M)}{D_{v}h(2M)}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \frac{h(\alpha e)}{D_{v}h(\alpha
e)}+\frac{h(M)}{D_{v}h(M)}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ \frac{h(\alpha e)}{D_{v}h(\alpha e)}.$

where the last step follows from $\frac{h(M)}{D_{v}h(M)}\geq 0$ (By [Ren06]).
∎

###  B.2 Defining interlacing family of characteristic polynomials

In this section, we consider the following interlacing family we will
crucially use to prove Theorem B.1.

######  Definition B.5 (Interlacing Family of Theorem B.1).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a hyperbolic polynomial with
respect to hyperbolic direction $e\in\Gamma_{++}^{h}$. Let
$\xi_{1},\dots,\xi_{n}$ denote $n$ independent random variables with finite
supports and $\operatorname*{{\mathbb{E}}}[\xi_{i}]=\mu_{i}$ for $i\in[n]$.
Let $v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors such that
$\mathrm{rank}_{h}(v_{i})\leq 1$ for all $i\in[n]$. For each
$s=(s_{1},\dots,s_{n})$ where $s_{i}\in\operatorname{supp}(\xi_{i})$, let
$p_{s}\in\mathbb{R}[x]$ define the following polynomial:

$\displaystyle p_{\bf s}(x):=\left(\prod_{i=1}^{n}p_{i,s_{i}}\right)\cdot
h\left(xe+\sum_{i=1}^{n}(s_{i}-\mu_{i})v_{i}\right)\cdot
h\left(xe-\sum_{i=1}^{n}(s_{i}-\mu_{i})v_{i}\right)$

where $p_{i,s_{i}}:=\Pr_{\xi_{i}}[\xi_{i}=s_{i}]$. Let $\mathcal{P}$ denote
the following family of polynomials:

$\displaystyle\mathcal{P}:=\left\\{p_{(s_{1},\cdots,s_{\ell})}=\sum_{\begin{subarray}{c}t_{\ell+1},\cdots,t_{n}:\\\
t_{j}\in\operatorname{supp}(\xi_{j})\leavevmode\nobreak\ \forall
j\in\\{\ell+1,\dots,n\\}\end{subarray}}p_{(s_{1},\cdots,s_{\ell},t_{\ell+1},\cdots,t_{n})}:\leavevmode\nobreak\
\ell\in[n],s_{i}\in\operatorname{supp}(\xi_{i})\leavevmode\nobreak\ \forall
i\in[\ell]\right\\}.$

######  Lemma B.6 (Interlacing Family of Theorem B.1).

The polynomial family $\mathcal{P}$ defined in Definition B.5 is an
interlacing family.

###### Proof.

Fix any $\ell\in[n-1]$, and fix $s_{1},\cdots,s_{\ell}$ as any partial
assignment of $\xi_{1},\cdots,\xi_{\ell}$, i.e. $s_{i}\in\\{\pm 1\\}$ for all
$i\in\operatorname{supp}(\xi_{i})$.

It is easy to see that the polynomial $p_{(s_{1},\dots,s_{\ell})}$ can be
written as:

$\displaystyle\left(\prod_{i=1}^{\ell}p_{i,s_{i}}\right)\operatorname*{{\mathbb{E}}}_{{\xi}_{\ell+1},\dots,\xi_{n}}\left[h\left(xe+\left(\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+\sum_{j=\ell+1}^{n}(\xi_{j}-\mu_{j})v_{j}\right)\right)\cdot\right.$
$\displaystyle\left.h\left(xe-\left(\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+\sum_{j=\ell+1}^{n}(\xi_{j}-\mu_{j})v_{j}\right)\right)\right]$

Let $\\{c_{1},\dots,c_{k}\\}$ be the support of $\xi_{\ell+1}$. Then, by Lemma
A.20, it suffices to show that for any $\alpha\in\mathbb{R}_{\geq 0}^{k}$ with
$\sum_{i=1}^{k}\alpha_{i}=1$, the polynomial

$\displaystyle\alpha_{1}p_{(s_{1},\cdots,s_{\ell},c_{1})}(x)+\cdots+\alpha_{k}p_{(s_{1},\cdots,s_{\ell},c_{k})}(x)$

is real-rooted. We interpret $\alpha$ as the probability density of the
$(\ell+1)$-th random variable, i.e. let $p_{\ell+1,c_{t}}=\alpha_{t}$ for all
$t\in[k]$. Then we can define a new random variable $\widetilde{\xi}_{\ell+1}$
with the same support as $\xi_{\ell+1}$ and
$\Pr[\widetilde{\xi}_{\ell+1}=c_{t}]=p_{\ell+1,c_{t}}$ for all $t\in[k]$.

Notice that

$\displaystyle\widetilde{p_{\bf s}}(x):=$ $\displaystyle\leavevmode\nobreak\
\left(\prod_{i=1}^{\ell}p_{i,s_{i}}\right)$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\
\times\operatorname*{{\mathbb{E}}}_{\widetilde{\xi}_{\ell+1},\xi_{\ell+2}\dots,\xi_{n}}\left[h\left(xe-\left(\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+(\widetilde{\xi}_{\ell+1}-\mu_{\ell+1})v_{\ell+1}+\sum_{j=\ell+2}^{n}(\xi_{j}-\mu_{j})v_{j}\right)\right)\right.$
$\displaystyle\leavevmode\nobreak\ \left.\hskip 102.42992pt\cdot
h\left(xe+\left(\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+(\widetilde{\xi}_{\ell+1}-\mu_{\ell+1})v_{\ell+1}+\sum_{j=\ell+2}^{n}(\xi_{j}-\mu_{j})v_{j}\right)\right)\right]$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{k}\left(\prod_{i=1}^{\ell}p_{i,s_{i}}\right)p_{\ell+1,c_{t}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\times\operatorname*{{\mathbb{E}}}_{\xi_{\ell+2},\dots,\xi_{n}}\left[h\left(xe-\Bigg{(}\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+c_{t}v_{\ell+1}+\sum_{j=\ell+2}^{n}(\xi_{j}-\mu_{j})v_{j}\Bigg{)}\right)\right.$
$\displaystyle\leavevmode\nobreak\ \left.\hskip 71.13188pt\cdot
h\left(xe+\Bigg{(}\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+c_{t}v_{\ell+1}+\sum_{j=\ell+2}^{n}(\xi_{j}-\mu_{j})v_{j}\Bigg{)}\right)\right]$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{k}\alpha_{i}p_{{\bf s},c_{i}}(x).$

By Lemma B.8 (we remark that it does not require any result in the current
section. We will prove Lemma B.8 in Section B.3), $\widetilde{p_{\bf s}}$ is
real-rooted, which completes the proof that $\mathcal{P}$ is an interlacing
family. ∎

Lemma B.6 implies the following corollary, which is a hyperbolic version of
Proposition 4.1 in [KLS20]:

######  Corollary B.7 (Upper Bound of the Largest Root of Interlacing Family).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a hyperbolic polynomial with
corresponding hyperbolic direction $e\in\Gamma_{++}^{h}$. Let
$\xi_{1},\dots,\xi_{n}$ denote $n$ independent random variables with finite
supports and $\operatorname*{{\mathbb{E}}}[\xi_{i}]=\mu_{i}$ for $i\in[n]$.
For any $v_{1},\dots v_{n}\in\Gamma^{h}_{++}$ such that
$\operatorname{rank}_{h}(v_{i})\leq 1$ for all $i\in[n]$, there exists an sign
assignment
$s=(s_{1},\dots,s_{n})\in\operatorname{supp}(\xi_{i})\times\cdots\operatorname{supp}(\xi_{n})$,
such that

$\displaystyle\left\|\sum_{i=1}^{m}(s_{i}-\mu_{i})v_{i}\right\|_{h}$

is at most the largest root of

$\displaystyle
p_{\emptyset}(x)=\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{m}}\left[h\Big{(}xe+\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\right].$

###### Proof.

Let $\mathcal{P}$ be the interlacing family defined in Definition B.5. Then by
Lemma B.6, $\mathcal{P}$ is an interlacing family.

For any fixed $\ell\in[n]$ and the first $\ell$ assignments
$(s_{1},\cdots,s_{\ell})$ such that $s_{i}\in\operatorname{supp}(\xi_{i})$ for
$i\in[\ell]$, notice that

$\displaystyle
p_{s_{1},\cdots,s_{\ell}}(x)=\left(\prod_{i=1}^{\ell}p_{i,s_{i}}\right)\operatorname*{{\mathbb{E}}}_{\xi_{\ell+1},\dots,\xi_{n}}\Bigg{[}$
$\displaystyle\leavevmode\nobreak\
h\left(xe-\left(\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+\sum_{j=\ell+1}^{n}(\xi_{j}-\mu_{j})v_{j}\right)\right)\cdot$
$\displaystyle\leavevmode\nobreak\
h\left(xe+\left(\sum_{i=1}^{\ell}(s_{i}-\mu_{i})v_{i}+\sum_{j=\ell+1}^{n}(\xi_{j}-\mu_{j})v_{j}\right)\right)\Bigg{]},$

and

$\displaystyle
p_{\emptyset}=\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{m}}\left[h\Big{(}xe+\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\right].$

Therefore, by Lemma A.19, there exists a sign assignment

$\displaystyle(s_{1},\dots,s_{n})\in\operatorname{supp}(\xi_{i})\times\cdots\operatorname{supp}(\xi_{n})$

such that the largest root of $p_{s}$ is upper bounded by the largest root of

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{m}}\left[h\Big{(}xe+\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\right].$

Then by Fact A.10, we have
$\left\|\sum_{i=1}^{m}(s_{i}-\mu_{i})v_{i}\right\|_{h}=\lambda_{\max}(p_{\bf
s})$, which is upper bounded by the maximum root of $p_{\emptyset}$.

∎

###  B.3 From mixed characteristic polynomial to multivariate polynomial

In this section, we want to show that the mixed characteristic polynomial,
i.e. the average of the interlacing family defined in Definition B.5:

$\displaystyle
p_{\emptyset}=\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{m}}\left[h\Big{(}xe+\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{m}(\xi_{i}-\mu_{i})v_{i}\Big{)}\right]$

equals to the following multivariate polynomial after taking
$z_{1}=\cdots=z_{n}=0$.

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}h\Big{(}xe-Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\cdot
h\Big{(}xe+Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\in\mathbb{R}[x,z_{1},\cdots,z_{n}]$

The largest root of this multivariate polynomial is relatively easy to upper-
bound using barrier argument. We will describe the details in Section B.4.

The main lemma of this section is as follows:

######  Lemma B.8 (Hyperbolic version of Proposition 3.3 in [KLS20]).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a hyperbolic polynomial with
respect to a hyperbolic direction $e\in\Gamma_{++}^{h}$. Let $v_{1},\dots
v_{n}\in\Gamma_{+}^{h}$ such that $\forall i\in[n]$,
$\operatorname{rank}_{h}(v_{i})\leq 1$. Let $\xi_{1},\dots,\xi_{n}$ denote $n$
independent random variables such that
$\operatorname*{{\mathbb{E}}}[\xi_{i}]=\mu_{i}$ and
$\operatorname*{{\bf{Var}}}[\xi_{i}]=\tau_{i}^{2}$. For any
$Q\in\mathbb{R}^{m}$, we have

$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{n}}\left[h\Big{(}xe-(Q+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i})\Big{)}h\Big{(}xe+(Q+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i})\Big{)}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\Big{|}_{z_{i}=0}h\Big{(}xe-Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\cdot
h\Big{(}xe+Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}.$ (11)

Moreover, this is a real-rooted polynomial in $x$.

###### Proof.

We first show Eqn. (11) by induction. Our induction hypothesis will be that
for any $0\leq k\leq n$,

$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{n}}\left[h\Big{(}xe-(Q+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i})\Big{)}h\Big{(}xe+(Q+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i})\Big{)}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\xi_{k+1},\dots,\xi_{n}}\prod_{i=1}^{k}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\Big{|}_{z_{i}=0}h\Big{(}xe-Q-\sum_{i=k+1}^{n}(\xi_{i}-\mu_{i})v_{i}+\sum_{j=1}^{k}z_{j}\tau_{j}v_{j}\Big{)}$
$\displaystyle\leavevmode\nobreak\ \times
h\Big{(}xe+Q+\sum_{i=k+1}^{n}(\xi_{i}-\mu_{i})v_{i}+\sum_{j=1}^{k}z_{j}\tau_{j}v_{j}\Big{)}$
(12)

The base case, $k=0$ trivially holds as we get the same formula on both sides.

For the inductive step, suppose the induction hypothesis holds for any
$k\leq\ell$ where $0\leq\ell<n$. Applying Claim B.9 to the right-hand-side of
Eqn. (12) when letting $k=\ell$ yields

$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{m}}\left[h\Big{(}xe-(Q+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i})\Big{)}h\Big{(}xe+(Q+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})v_{i})\Big{)}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\xi_{\ell+2},\dots,\xi_{m}}\prod_{i=1}^{\ell+1}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\Big{|}_{z_{i}=0}h\Big{(}xe-Q-\sum_{i=\ell+2}^{n}(\xi_{i}-\mu_{i})v_{i}+\sum_{j=1}^{\ell+1}z_{j}\tau_{j}v_{j}\Big{)}$
$\displaystyle\leavevmode\nobreak\ \times
h\Big{(}xe+Q+\sum_{i=\ell+2}^{n}(\xi_{i}-\mu_{i})v_{i}+\sum_{j=1}^{\ell+1}z_{j}\tau_{j}v_{j}\Big{)}$
(13)

This completes the proof of Eqn. (11).

We now show that Eqn. (11) is real-rooted in $x$. By Claim B.11, we know that

$\displaystyle
h\Big{(}xe-Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ \leavevmode\nobreak\
h\Big{(}xe+Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\in\mathbb{R}[x,z_{1},\dots,z_{n}],$

are real-stable polynomials. Then, by Fact A.5, we get that

$\displaystyle h\Big{(}xe-Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\cdot
h\Big{(}xe+Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}$

is also real-stable. And by Fact A.5 again, the operator

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\Big{|}_{z_{i}=0}$

preserves the real-stability. Hence, by Fact A.2, the RHS of Eqn. (11) is
real-rooted. ∎

The following statements are crucially used in the proof of Lemma B.8:

######  Claim B.9 (Hyperbolic version of Lemma 3.1 in [KLS20]).

Let $h$ denote a hyperbolic polynomial. Let $\xi$ denote a random variables
with $\operatorname*{{\mathbb{E}}}[\xi]=0$ and
$\operatorname*{{\bf{Var}}}[\xi]=\tau^{2}$. For any $v\in\mathbb{R}^{m}$ such
that $\operatorname{rank}_{h}(v)\leq 1$, and any
$x_{1},x_{2}\in\mathbb{R}^{m}$, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi}[h(x_{1}-\xi v)\cdot
h(x_{2}+\xi
v)]=\left(1-\frac{1}{2}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\right)\Bigg{|}_{t=0}h(x_{1}+t\tau
v)h(x_{2}+t\tau v).$

######  Remark B.10.

Claim B.9 can be easily generalized for non-centered random variable $\xi$
with $\operatorname*{{\mathbb{E}}}[\xi]=\mu$:

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi}[h(x_{1}-(\xi-\mu)v)\cdot
h(x_{2}+(\xi-\mu)v)]=\left(1-\frac{1}{2}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\right)\Bigg{|}_{t=0}h(x_{1}+t\tau
v)h(x_{2}+t\tau v).$

###### Proof.

Since $\operatorname{rank}_{h}(v)\leq 1$, for all $k\geq 2$, $D_{v}^{k}h\equiv
0$. Thus, for all $x_{1}\in\mathbb{R}^{m}$,

$\displaystyle h(x_{1}-\xi
v)=\left(\sum_{k=0}^{\infty}\frac{(-\xi)^{k}D_{v}^{k}}{k!}\right)h(x_{1})=(1-\xi
D_{v})h(x_{1}).$

where the first step follows from Taylor expansion of $h(x_{1}-\xi v)$ on
$x_{1}$.

Similarly, for all $x_{2}\in\mathbb{R}^{m}$,

$\displaystyle h(x_{2}+\xi v)=(1+\xi D_{v})h(x_{2}).$

Therefore,

$\displaystyle h(x_{1}-\xi v)\cdot h(x_{2}+\xi v)$ $\displaystyle=(1-\xi
D_{v})h(x_{1})\cdot(1+\xi D_{v})h(x_{2})$ $\displaystyle=h(x_{1})h(x_{2})-\xi
h(x_{2})D_{v}h(x_{1})+\xi
h(x_{1})D_{v}h(x_{2})-\xi^{2}D_{v}h(x_{1})D_{v}h(x_{2})$

Since $\operatorname*{{\mathbb{E}}}[\xi]=0$ and
$\operatorname*{{\bf{Var}}}[\xi]=\tau^{2}$, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi}[h(x_{1}-\xi v)\cdot
h(x_{2}+\xi v)]=$ $\displaystyle\leavevmode\nobreak\
\left(1-\frac{\operatorname*{{\mathbb{E}}}[\xi^{2}]}{2}D_{v}^{2}\right)h(x_{1})h(x_{2})+\operatorname*{{\mathbb{E}}}_{\xi}[\xi]\cdot(h(x_{1})D_{v}h(x_{2})-h(x_{2})D_{v}h(x_{1}))$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\left(1-\frac{\tau^{2}}{2}D_{v}^{2}\right)h(x_{1})h(x_{2})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\left(1-\frac{1}{2}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\right)\Bigg{|}_{t=0}h(x_{1}+t\tau
v)h(x_{2}+t\tau v).$

∎

######  Claim B.11 (Linear restriction of hyperbolic polynomial is real-
stable).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ be a hyperbolic polynomial with
respect to $e\in\mathbb{R}^{m}$. Let $v_{1},\dots,v_{n}\in\Gamma_{+}$ and
$Q\in\mathbb{R}^{m}$. Define

$\displaystyle
p(x,z):=h\Big{(}xe+\sum_{i=1}^{n}z_{i}v_{i}-Q\Big{)}\in\mathbb{R}[x,z_{1},\dots,z_{n}].$

Then, $p(x,z)$ is a real-stable polynomial.

###### Proof.

For any $a\in\mathbb{R}_{>0}^{n+1}$, $b\in\mathbb{R}^{n+1}$, we have

$\displaystyle p(at+b)=$ $\displaystyle\leavevmode\nobreak\
h\Big{(}(a_{1}t+b_{1})e-Q+\sum_{i=1}^{n}(a_{i+1}t+b_{i+1})v_{i}\Big{)}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
h\Big{(}(a_{1}e+\sum_{i=1}^{n}a_{i+1}v_{i})t+b_{1}e-Q+\sum_{i=1}^{n}b_{i+1}v_{i}\Big{)}.$

Since $e\in\Gamma_{++}$, $v_{1},\dots,v_{n}\in\Gamma_{+}$ and $a_{i}>0$ for
all $i\in[n+1]$, we have

$\displaystyle e^{\prime}:=a_{1}e+\sum_{i=1}^{n}a_{i+1}v_{i}\in\Gamma_{++},$

which follows from $\Gamma_{++}$ is a cone.

Since every vector in $\Gamma_{++}$ is a hyperbolic direction of $h$ (see
e.g., [Brä18, Theorem 1.2, item 4]), we know that $h$ is also hyperbolic with
respect to the direction $e^{\prime}$, which implies that $p(at+b)$ is real-
rooted and not identical to the zero polynomial.

Hence, by Fact A.3, $p(x,z)$ is a real-stable polynomial. ∎

###  B.4 Applying barrier argument to bound the largest root of multivariate
polynomial

In this section, we upper bound the largest root of the following multivariate
polynomial:

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}h\Big{(}xe-Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\cdot
h\Big{(}xe+Q+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}$

using the real-stable version of the barrier method in [KLS20].

######  Definition B.12.

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be a hyperbolic polynomial of degree
$d$ with respect to hyperbolic direction $e\in\mathbb{R}^{m}$. For any vectors
$u,v\in\mathbb{R}^{m}$, we say $u\preceq v$ if

$\displaystyle\lambda_{i}(u)\leq\lambda_{i}(v)\quad\forall i\in[d],$

where $\lambda(u),\lambda(v)$ are the ordered eigenvalues of $u$ and $v$,
respectively.

######  Claim B.13.

Let $h$ be a hyperbolic polynomial of degree $d$ with respect to hyperbolic
direction $e\in\mathbb{R}^{m}$. Let $u\in\mathbb{R}^{m}$ be any vector such
that $u\preceq e$. Then we have $e-u\in\Gamma^{h}_{+}$.

###### Proof.

For any $i\in[d]$, we have

$\displaystyle\lambda_{i}(e-u)=1-\lambda_{d-i}(u)\geq 0,$

where the last step follows from $\lambda_{i}(u)\leq\lambda_{i}(e)\leq 1$ for
all $i\in[d]$.

Hence, $e-u\in\Gamma^{h}_{+}$. ∎

The goal of this section is to prove the following lemma:

######  Lemma B.14.

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a hyperbolic polynomial with
corresponding hyperbolic direction $e\in\Gamma^{h}_{+}$. Let
$\xi_{1},\dots,\xi_{n}$ denote $n$ independent random variables with finite
supports and $\operatorname*{{\mathbb{E}}}[\xi_{i}]=\mu_{i}$ and
$\operatorname*{{\bf{Var}}}[\xi_{i}]=\tau_{i}^{2}$ for $i\in[n]$. Let
$v_{1},\dots,v_{n}\in\Gamma^{h}_{+}$ such that
$\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\preceq e$ and
$\forall i\in[n]$, $\operatorname{rank}_{h}(v_{i})\leq 1$.

Then all the roots of the following $(n+1)$-variate polynomial

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\left(h\Big{(}xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\right)^{2}\in\mathbb{R}[x,z_{1},\dots,z_{n}]$

lie below $(4,0,\cdots,0)\in\mathbb{R}^{n+1}$.

###### Proof.

Define $(n+1)$-variate polynomial $P(x,z)\in\mathbb{R}[x,z_{1},\dots,z_{n}]$
as

$\displaystyle
P(x,z):=\left(h\Big{(}xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\right)^{2}.$

By Claim B.11 and Fact A.5, we can show that $P(x,z)$ is real-stable. Thus, we
can apply the multivariate barrier method in [KLS20] with the barrier
functions $\Phi_{P}^{i}(x,z)=\frac{\partial_{z_{i}}P(x,z)}{P(x,z)}$ for
$i\in[n]$.

For $t>0$, let $\delta_{i}=t\tau_{i}\operatorname{tr}_{h}[v_{i}]$ and let

$\displaystyle\mathbf{\delta}=(\delta_{1},\dots,\delta_{n}).$

For some $\alpha(t)>t$ where $\alpha(t)$ is a parameter to be chosen later, we
evaluate $P$ at

$\displaystyle(\alpha,-\delta)=(\alpha(t),-\delta_{1},\dots,-\delta_{n})$

to find that

$\displaystyle P(\alpha(t),-\delta_{1},\dots,-\delta_{n})=$
$\displaystyle\leavevmode\nobreak\
\left(h\Big{(}\alpha(t)e-\sum_{i=1}^{n}\delta_{i}\tau_{i}v_{i}\Big{)}\right)^{2}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\left(h\Big{(}\alpha(t)e-t\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\Big{)}\right)^{2}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\left(h(e)\prod_{j=1}^{d}\Big{(}\alpha(t)-t\lambda_{j}\Big{(}\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\Big{)}\Big{)}\right)^{2}$

where $d$ is the degree of $h$. Here the last step follows from the
hyperbolicity of $h$, and the fact that the set of roots of

$\displaystyle
h\Big{(}\alpha(t)e-t\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\Big{)}$

are

$\displaystyle\left\\{\left(\frac{1}{\alpha(t)}\cdot\lambda_{j}\Big{(}\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\Big{)}\right)^{-1}\right\\}_{j\in[d]}$

Since $\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\preceq e$,
we have for all $j\in[d]$,
$\lambda_{j}(\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i})\leq\lambda_{j}(e)=1$.

Hence, by the assumption of $t<\alpha(t)$, we get that

$\displaystyle P(\alpha(t),-\delta_{1},\dots,-\delta_{n})\geq
h(e)^{2}(\alpha(t)-t)^{2d}>0.$

This implies that $(\alpha,-\mathbf{\delta})\in\mathbb{R}^{m+1}$ is above the
roots of $P(x,z)$, i.e. $(\alpha,-\mathbf{\delta})\in\mathbf{Ab}_{P}$.

Moreover, we can upper bound $\Phi^{i}_{P}(\alpha,-\mathbf{\delta})$ as
follows:

$\displaystyle\Phi^{i}_{P}(\alpha(t),-\delta)=$
$\displaystyle\leavevmode\nobreak\
\frac{\partial_{z_{i}}P}{P}\Big{|}_{x=\alpha(t),z=-\mathbf{\delta}}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{2h(xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i})\partial_{z_{i}}h(xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i})}{h(xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i})^{2}}\Big{|}_{x=\alpha(t),z=-\delta}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
2\cdot\frac{\partial_{z_{i}}h(xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i})}{h(xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i})}\Big{|}_{x=\alpha(t),z=-\delta}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
2\cdot\frac{(D_{\tau_{i}v_{i}}h)(\alpha
e+\sum_{j=1}^{n}\delta_{j}\tau_{j}v_{j})}{h(\alpha
e+\sum_{j=1}^{n}\delta_{j}\tau_{j}v_{j})}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ 2\cdot\frac{(D_{\tau_{i}v_{i}}h)(\alpha
e-t\sum_{j=1}^{n}\tau_{j}^{2}\operatorname{tr}_{h}[v_{j}]v_{j})}{h(\alpha
e-t\sum_{j=1}^{n}\tau_{j}^{2}\operatorname{tr}_{h}[v_{j}]v_{j})}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
2\cdot\frac{(D_{\tau_{i}v_{i}}h)(\alpha
e-te+t(e-\sum_{j=1}^{n}\tau_{j}^{2}\operatorname{tr}_{h}[v_{j}]v_{j}))}{h(\alpha
e-te+t(e-\sum_{j=1}^{n}\tau_{j}^{2}\operatorname{tr}_{h}[v_{j}]v_{j}))}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{2(D_{\tau_{i}v_{i}}h)(\alpha e-te)}{h(\alpha e-te)}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\frac{2\operatorname{tr}_{h}[\tau_{i}v_{i}]}{\alpha-t}.$

where the second last step follows from
$\sum_{i=1}^{n}\tau_{j}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\preceq e$, Claim
B.13 and Fact B.4. The last step follows from $\frac{(D_{v}h)(\beta
e)}{h(\beta e)}=\frac{\operatorname{tr}_{h}[v]}{\beta}$ by Fact B.3.

Since $\operatorname{rank}_{h}(v_{i})\leq 1$, we have
$\operatorname{tr}_{h}[v_{i}]=\|v_{i}\|_{h}$ for all $i\in[n]$. Since
$\sum_{j\neq
i}\tau_{j}^{2}\operatorname{tr}_{h}[v_{j}]v_{j}\in\Gamma^{h}_{+}$, by the
monotonicity of the hyperbolic norm (Theorem 2.15 in [HLJ09]), we have

$\displaystyle(\tau_{i}\operatorname{tr}_{h}[v_{i}])^{2}=\|\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}\|_{h}\leq\left\|\sum_{j=1}^{n}\tau_{j}^{2}\operatorname{tr}_{h}[v_{j}]v_{j}\right\|_{h}\leq\|e\|_{h}=1$

for all $i\in[n]$.

Thus, we have

$\displaystyle\max_{i\in[n]}\leavevmode\nobreak\ \leavevmode\nobreak\
(\tau_{i}\operatorname{tr}_{h}[v_{i}])^{2}\leq 1.$

Choosing $\alpha(t)=2t=4$. We get

$\displaystyle\Phi_{P}^{i}(\alpha,-\delta)\leq\frac{2\operatorname{tr}_{h}[\tau_{i}v_{i}]}{\alpha-t}=\frac{2\tau_{i}\operatorname{tr}_{h}[v_{i}]}{\alpha-t}=\frac{2\tau_{i}\operatorname{tr}_{h}[v_{i}]}{2}\leq
1<\sqrt{2}.$ (14)

This coincides with Eqn. (9) of Lemma A.23. Also from Fact A.5 we know that
$(1-\frac{1}{2}\partial_{z_{i}}^{2})P$ is real stable.

Thus by Lemma A.23, for all $i\in[n]$,

$\displaystyle(4,-\mathbf{\delta})\in\mathbf{Ab}_{(1-\frac{1}{2}\partial_{z_{i}}^{2})P}.$

In addition, $\forall i\in[n]$, since
$\delta_{i}=t\tau_{i}\operatorname{tr}_{h}[v_{i}]=2\tau_{i}\operatorname{tr}_{h}[v_{i}]>0$,

$\displaystyle\frac{1}{\delta_{i}}\Phi_{P}^{i}(4,-\mathbf{\delta})+\frac{1}{2}\Phi_{P}^{i}(4,-\mathbf{\delta})^{2}\leq$
$\displaystyle\leavevmode\nobreak\
\frac{1}{2\tau_{i}\operatorname{tr}_{h}[v_{i}]}\tau_{i}\operatorname{tr}_{h}[v_{i}]+\frac{1}{2}(\tau_{i}\operatorname{tr}_{h}[v_{i}])^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{1}{2}+\frac{1}{2}=1.$ (15)

This coincides with Eqn. (10) of Lemma A.23. Therefore for all $j\in[n]$,

$\displaystyle\Phi^{j}_{(1-\frac{1}{2}\partial_{z_{i}}^{2})P}(4,-\mathbf{\delta}+\delta_{i}{\bf
1}_{i})\leq\Phi_{P}^{j}(4,-\mathbf{\delta}).$ (16)

In particular, we have

$\displaystyle\Phi^{2}_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}(4,-\mathbf{\delta}+\delta_{1}{\bf
1}_{1})\leq\Phi_{P}^{2}(4,-\mathbf{\delta})<\sqrt{2}.$

We also have $(4,-\delta+\delta_{1}{\bf
1}_{1})\in\mathbf{Ab}_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}$, which follows
from $(4,-\delta)\in\mathbf{Ab}_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}$. By
Lemma A.25 with $k=0$, we get that

$\displaystyle\Phi^{2}_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}(4,-\mathbf{\delta}+\delta_{1}{\bf
1}_{1})\geq 0.$

Hence, we have

$\displaystyle\frac{1}{\delta_{2}}\Phi_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}^{2}(4,-\mathbf{\delta}+\delta_{1}{\bf
1}_{1})+\frac{1}{2}\Phi_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}^{2}(4,-\mathbf{\delta}+\delta_{1}{\bf
1}_{1})^{2}$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{1}{\delta_{2}}\Phi_{P}^{2}(4,-\mathbf{\delta})+\frac{1}{2}\Phi_{P}^{2}(4,-\mathbf{\delta})^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ 1,$

where the last step follows from Eqn. (B.4).

Therefore, by Lemma A.23 again, we have

$\displaystyle\Phi^{i}_{(1-\frac{1}{2}\partial_{z_{2}}^{2})(1-\frac{1}{2}\partial_{z_{1}}^{2})P}(4,-\mathbf{\delta}+\delta_{1}{\bf
1}_{1}+\delta_{2}{\bf
1}_{2})\leq\Phi^{i}_{(1-\frac{1}{2}\partial_{z_{1}}^{2})P}(4,-\mathbf{\delta}+\delta_{1}{\bf
1}_{1}).$

Repeating this argument for each $i\in[n]$ demonstrates that

$\displaystyle(4,-\mathbf{\delta}+\sum_{i=1}^{n}\delta_{i}{\bf 1}_{i})$
$\displaystyle=(4,0,0,\dots,0)$
$\displaystyle\in\mathbf{Ab}_{\prod_{i=1}^{n}(1-\partial_{z_{i}}^{2}/2)P}$

i.e. $(4,0,0,\dots,0)$ lies above the roots of

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\left(h\Big{(}xe+\sum_{i=1}^{n}z_{i}\tau_{i}v_{i}\Big{)}\right)^{2}.$

∎

###  B.5 Combining together: proof of Theorem B.1

In this section, we will combine the results from the previous section and
prove Theorem B.1:

###### Proof of Theorem B.1.

Define $u_{i}:=\frac{v_{i}}{\sigma}$. Note that $\sigma>0$ since
$v_{1},\dots,v_{n}$ are in the hyperbolicity cone of $h$.

Then, we have

$\displaystyle\left\|\sum_{i=1}^{n}\tau_{i}^{2}\operatorname{tr}_{h}[u_{i}]u_{i}\right\|_{h}=\left\|\sum_{i=1}^{n}\frac{\tau_{i}^{2}\operatorname{tr}_{h}[v_{i}]v_{i}}{\sigma^{2}}\right\|_{h}=1,$

where the first step follows from the linearity of the hyperbolic trace
$\operatorname{tr}_{h}$, and the second step follows from $\|\cdot\|_{h}$ is a
norm.

By Lemma B.14 and restricting to $z_{i}=0$ for all $i\in[n]$, we have that $4$
lies above the largest root of the univariate polynomial

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\Big{|}_{z_{i}=0}\left(h\Big{(}xe+\sum_{i=1}^{n}z_{i}\tau_{i}u_{i}\Big{)}\right)^{2}$

We then conclude by Lemma B.8 that $4$ upper bounds the largest root of

$\displaystyle
p_{\emptyset}=\operatorname*{{\mathbb{E}}}_{\xi_{1},\dots,\xi_{n}}\left[h\Big{(}xe+\sum_{i=1}^{n}(\xi_{i}-\mu_{i})u_{i}\Big{)}\cdot
h\Big{(}xe-\sum_{i=1}^{n}(\xi_{i}-\mu_{i})u_{i}\Big{)}\right].$

where $p_{\emptyset}$ is the average of the polynomials in the interlacing
family $\mathcal{P}$ in Definition B.5.

Finally, by Corollary B.7, we conclude that there exists
$s_{1},\dots,s_{n}\in\operatorname{supp}(\xi_{1})\times\cdots\times\operatorname{supp}(\xi_{n})$
such that

$\displaystyle\left\|\sum_{i=1}^{n}(s_{i}-\mu_{i})u_{i}\right\|_{h}\leq 4.$

Hence we have

$\displaystyle\left\|\sum_{i=1}^{n}(s_{i}-\mu_{i})v_{i}\right\|_{h}\leq
4\sigma.$

∎

##  Appendix C Hyperbolic Extension of Kadision-Singer for Strongly Rayleigh

In this section, we prove Theorem 1.6. We restate the theorem as follows:

######  Theorem C.1 (Formal statement of Theorem 1.6).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a hyperbolic polynomial with
respect to hyperbolic direction $e\in\Gamma_{++}^{h}$. Let $\mu$ be a
homogeneous strongly Rayleigh probability distribution on $[n]$ such that the
marginal probability of each element is at most $\epsilon_{1}$, and let
$v_{1},\cdots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors in isotropic positions,

$\displaystyle\sum_{i=1}^{n}v_{i}=e,$

such that for all $i\in[n]$,

$\displaystyle\operatorname{rank}_{h}(v_{i})\leq 1\text{, and
}\|v_{i}\|_{h}\leq\epsilon_{2}.$

Then

$\displaystyle\Pr_{S\sim\mu}\left[\Big{\|}\sum_{i\in S}v_{i}\Big{\|}_{h}\leq
4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}\right]>0.$

We will introduce the preliminary facts in Section C.1. In Section C.2, we
define the family of hyperbolic characteristic polynomials and show that it
forms an interlacing family. Therefore, it remains to upper-bound the largest
root of the average of the interlacing polynomial family, i.e. the mixed
hyperbolic characteristic polynomial. We remark that we require a lemma that
will be proved later in Section C.3.

In Section C.3, we reduce the problem of upper-bounding the largest root of
the mixed hyperbolic characteristic polynomial to an easier task of upper-
bounding the largest root of a multivariate polynomial. In Section C.4, we
upper bound the largest root of the multivariate polynomial using the
multivariate barrier method. Finally, in Section C.5, we prove Theorem C.1.

###  C.1 Preliminaries

In this section, we present some preliminary results on strongly Rayleigh
distributions.

######  Definition C.2 (Generating polynomial of probability distribution).

Let $\mu:2^{[n]}\rightarrow\mathbb{R}_{\geq 0}$ be a probability distribution.
For a random variable $X\sim\mu$, the generating polynomial of $\mu$ is
defined as follows:

$\displaystyle
g_{\mu}(z_{1},\dots,z_{n})=\operatorname*{{\mathbb{E}}}\left[z^{X}\right]=\sum_{S\subseteq[n]}\Pr[X=S]z^{S}.$

######  Definition C.3 (Strongly Rayleigh distribution).

Let $\mu:2^{[n]}\rightarrow\mathbb{R}_{\geq 0}$ be a probability distribution
and $g_{\mu}$ be its generating polynomial. We say $\mu$ is strongly Rayleigh
(SR) if $g_{\mu}$ is a real stable polynomial.

Moreover, we say $\mu$ is $d_{\mu}$-homogeneous strongly Rayleigh if $g_{\mu}$
is $d_{\mu}$-homogeneous real stable.

We provide two facts about the generating polynomials of Strongly Rayleigh
distributions.

######  Fact C.4 (Marginals of homogeneous SR distributions).

Let $\mu:2^{[n]}\rightarrow\mathbb{R}_{\geq 0}$ be a $d_{\mu}$-homogeneous SR
distribution with generating polynomial $g_{\mu}$. For $1\leq k\leq n$,
consider the marginal distribution on the first $k$ elements
$\mu_{k}:2^{[k]}\rightarrow\mathbb{R}_{\geq 0}$ such that

$\displaystyle\mu_{k}(S)=\Pr_{T\sim\mu}[T\cap[k]=S]\quad\forall
S\subseteq[k].$

Then, for all $S\subseteq[k]$,

$\displaystyle\mu_{k}(S)=x^{|S|-d_{\mu}}\cdot\prod_{i\in
S}\partial_{z_{i}}\prod_{i\in[k]\backslash
S}(1-x\partial_{z_{i}})g_{\mu}(x\mathbf{1}+z)\Bigg{|}_{z=0}.$ (17)

In particular,

$\displaystyle\mu(S)=x^{|S|-d_{\mu}}\cdot\prod_{i\in
S}\partial_{z_{i}}\prod_{i\in[n]\backslash
S}(1-x\partial_{z_{i}})g_{\mu}(x\mathbf{1}+z)\Bigg{|}_{z=0}.$

######  Remark C.5.

We note that the dummy variable $x$ will be cancelled in the RHS of Eqn. (17),
and hence both sides are numbers.

###### Proof.

Note that $g_{\mu}$ can be written as

$\displaystyle g_{\mu}(x{\bf
1}+z)=f(z_{2},\dots,z_{n})(x+z_{1})+g(z_{2},\dots,z_{n}),$

where

$\displaystyle f(z_{2},\dots,z_{n}):=$ $\displaystyle\leavevmode\nobreak\
\sum_{\begin{subarray}{c}S\subseteq[n]\backslash\\{1\\},\\\
|S|=d_{\mu}-1\end{subarray}}\mu(S\cup\\{1\\})\prod_{i\in
S}(x+z_{i}),\quad\text{and}$ $\displaystyle g(z_{2},\dots,z_{n}):=$
$\displaystyle\leavevmode\nobreak\
\sum_{\begin{subarray}{c}S\subseteq[n]\backslash\\{1\\},\\\
|S|=d_{\mu}\end{subarray}}\mu(S)\prod_{i\in S}(x+z_{i}).$

First, if $k=1$. We have

$\displaystyle\mu_{1}(\\{1\\})=$ $\displaystyle\leavevmode\nobreak\
\Pr_{T\sim\mu}[1\in T]=x^{-d_{\mu}+1}\cdot
f(z_{2},\dots,z_{n})\Big{|}_{z=0}=x^{-d_{\mu}+1}\cdot\partial_{z_{1}}g_{\mu}(x{\bf
1}+z)\Big{|}_{z=0}.$

Also,

$\displaystyle\mu_{1}(\emptyset)=$ $\displaystyle\leavevmode\nobreak\
\Pr_{T\sim\mu}[1\not\in T]=x^{-d_{\mu}}\cdot
g(z_{2},\dots,z_{n})\Big{|}_{z=0}=x^{-d_{\mu}}\cdot(1-x\partial_{z_{1}})g_{\mu}(x{\bf
1}+z)\Big{|}_{z=0}.$

So, Eqn. (17) holds for $k=1$.

For the cases where $k>1$s, we can prove by induction on $k$. Suppose (17)
holds for $1,\cdots,k-1$. Let $S\subseteq[k]$ be any subset of $[k]$. If $k\in
S$, then consider $\partial_{z_{k}}g_{\mu}(x{\bf 1}+z)$, which is the
generating polynomial of $\mu^{\prime}$ that restricts $\mu$ to the sets
$T\subseteq[n]\backslash\\{k\\}$ with $\mu(T\cup\\{k\\})>0$. Let
$S^{\prime}:=S\backslash\\{k\\}$. By the induction hypothesis, we have

$\displaystyle\mu(S)=\mu^{\prime}(S^{\prime})=$
$\displaystyle\leavevmode\nobreak\
x^{|S^{\prime}|-d_{\mu^{\prime}}}\cdot\prod_{i\in
S^{\prime}}\partial_{z_{i}}\prod_{i\in[k-1]\backslash
S^{\prime}}(1-x\partial_{z_{i}})\partial_{z_{k}}g_{\mu}(x{\bf
1}+z)\Bigg{|}_{z=0}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{|S|-d_{\mu}}\cdot\prod_{i\in S}\partial_{z_{i}}\prod_{i\in[k]\backslash
S}(1-x\partial_{z_{i}})g_{\mu}(x{\bf 1}+z)\Bigg{|}_{z=0},$

where the second line follows from $|S^{\prime}|=|S|-1$ and
$d_{\mu^{\prime}}=d_{\mu}-1$.

If $k\notin S$, then consider $(1-x\partial_{z_{k}})g_{\mu}(x{\bf
1}+z)\Big{|}_{z_{k}=0}$, which is the generating polynomial of
$\mu^{\prime\prime}$ that restricts $\mu$ to the sets
$T\subseteq[n]\backslash\\{k\\}$ with $\mu(T)>0$. Then by the induction
hypothesis, we have

$\displaystyle\mu(S)=\mu^{\prime\prime}(S)=$
$\displaystyle\leavevmode\nobreak\
x^{|S|-d_{\mu^{\prime\prime}}}\cdot\prod_{i\in
S}\partial_{z_{i}}\prod_{i\in[k-1]\backslash
S}(1-x\partial_{z_{i}})(1-x\partial_{z_{k}})g_{\mu}(x{\bf 1}+z)\Bigg{|}_{z=0}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{|S|-d_{\mu}}\cdot\prod_{i\in S}\partial_{z_{i}}\prod_{i\in[k]\backslash
S}(1-x\partial_{z_{i}})g_{\mu}(x{\bf 1}+z)\Bigg{|}_{z=0}.$

Hence, Eqn. (17) holds for all $k\in[n]$, which completes the proof of the
fact. ∎

###  C.2 Defining interlacing family of characteristic polynomials

In this section, we consider the following family of polynomials:

######  Definition C.6 (Interlacing Family of Theorem C.1).

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a degree-$d$ hyperbolic
polynomial with respect to hyperbolic direction $e\in\Gamma_{++}^{h}$. Let
$\mu:2^{[n]}\to\mathbb{R}$ be a homogeneous strongly Rayleigh probability
distribution. Let $v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors such
that $\operatorname{rank}_{h}(v_{i})\leq 1$ for all $i\in[n]$. Let
$\mathcal{F}=\\{S\subseteq[n]:\mu(S)>0\\}$ be the support of $\mu$. For any
$S\in\mathcal{F}$, let

$\displaystyle q_{S}(x)=\mu(S)\cdot h\left(xe-\sum_{i\in S}v_{i}\right).$ (18)

Let $\mathcal{Q}$ denote the following family of polynomials:

$\displaystyle\mathcal{Q}:=\Big{\\{}q_{s_{1}\cdots
s_{\ell}}(s)=\sum_{\begin{subarray}{c}t_{\ell+1},\cdots,t_{n}\\\ (s_{1}\cdots
s_{\ell},t_{\ell+1},\cdots,t_{n})\in\mathcal{F}\end{subarray}}q_{s_{1},\cdots,s_{\ell},t_{\ell+1},\cdots,t_{n}}:\forall\ell\in[n],(s_{1},\cdots,s_{\ell})\in\mathcal{F}|_{[\ell]}\Big{\\}}.$

where $\mathcal{F}|_{[\ell]}$ is $\mathcal{F}$ restricted to $[\ell]$, and a
subset is represented by a binary indicator vector.

We show that the family defined above is an interlacing family. We will
crucially use this fact to show Theorem C.1.

######  Lemma C.7 (Hyperbolic version of Theorem 3.3 in [AO14]).

Let $\mathcal{Q}$ denote the family of polynomials as in Definition C.6. Then,
if the polynomial

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

is real-rooted in $x$ for any strongly Rayleigh distribution $\mu$, then the
polynomial family $\mathcal{Q}$ forms an interlacing family.

The proof of this lemma is the same as that of Theorem 3.3 in [AO14].

From Lemma A.19 and Fact A.10, we obtain the following corollary:

######  Corollary C.8.

Let $h\in\mathbb{R}[x_{1},\dots,x_{m}]$ denote a degree-$d$ hyperbolic
polynomial with respect to hyperbolic direction $e\in\Gamma_{++}^{h}$. Let
$\mu:2^{[n]}\to\mathbb{R}$ be a homogeneous strongly Rayleigh probability
distribution. Let $v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors such
that $\operatorname{rank}_{h}(v_{i})\leq 1$ for all $i\in[n]$. Let
$\mathcal{F}=\\{S\subseteq[n]:\mu(S)>0\\}$ be the support of $\mu$. Then there
exists $S\in\mathcal{F}$, such that the hyperbolic norm $\|\sum_{i\in
S}v_{i}\|_{h}$ equals to the largest root of $q_{S}$, and is upper bounded by
the largest root of

$\displaystyle
q_{\emptyset}=\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right].$

###### Proof.

By Lemma C.9 (we remark that this lemma does not depend on the results in this
section. We will prove Lemma C.9 in Section C.3), the mixed characteristic
polynomial

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

is real-rooted. Then by Lemma C.7, the polynomial family $\mathcal{Q}$ (see
Definition C.6) is an interlacing family. Therefore, by Lemma A.17, there
exists a subset $S\in\mathcal{F}$, such that the largest root of $q_{S}$, is
upper bounded by the largest root of

$\displaystyle
q_{\emptyset}=\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right].$

The corollary then follows from Fact A.10. ∎

###  C.3 From mixed characteristic polynomial to multivariate polynomial

In this section, we want to show that the mixed characteristic polynomial

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

has roots equals to the roots of the following multivariate polynomial after
taking $z_{1}=\cdots=z_{n}=0$.

$\displaystyle\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}$

The largest root of this multivariate polynomial is relatively easy to upper-
bound using barrier argument. We will describe the details in Section C.4.

The main lemma of this section is as follows:

######  Lemma C.9 (Hyperbolic version of Theorem 3.1 in [AO14]).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ be a degree-$d$ hyperbolic polynomial
with hyperbolic direction $e\in\Gamma_{++}^{h}$. Let
$\mu:2^{[n]}\to\mathbb{R}$ be a $d_{\mu}$-homogeneous strongly Rayleigh
probability distribution with generating polynomial
$g_{\mu}\in\mathbb{R}[z_{1},\cdots,z_{n}]$. Let
$v_{1},\dots,v_{n}\in\Gamma_{+}^{h}$ be $n$ vectors such that
$\operatorname{rank}_{h}(v_{i})\leq 1$ for all $i\in[n]$. Then, we have

$\displaystyle
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]=x^{d}\cdot\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}.$ (19)

Moreover,

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

is real-rooted in $x$.

###### Proof.

First, we rewrite the left-hand-side of (19) as the expectation over
$T\sim\mu$ as an expectation over all indicator $\xi$ of the subsets of $[n]$:

$\displaystyle\leavevmode\nobreak\ x^{d_{\mu}}\cdot
2^{-n}\cdot\operatorname*{{\mathbb{E}}}_{T\sim\mu}\left[h(x^{2}e-(\sum_{i\in
T}v_{i}))\right]$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{d_{\mu}}\cdot
2^{-n}\cdot\sum_{\xi\in\\{0,1\\}^{n}}\left(h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\cdot\mu(\xi)\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\\{0,1\\}^{n}}\left[h(x^{2}e-\sum_{i=1}^{n}\xi_{i}v_{i})\cdot\mu(\xi)\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\\{0,1\\}^{n}}\left[h(x^{2}e-\sum_{i=1}^{n}\xi_{i}v_{i})\cdot
x^{\sum_{i=1}^{n}\xi_{i}-d_{\mu}}\cdot\prod_{i=1}^{n}\big{(}\xi_{i}\partial_{z_{i}}+(1-\xi_{i})(1-z_{i}\partial_{z_{i}})\big{)}g(x{\bf
1}+z)\Bigg{|}_{z=0}\right]$ (20)

where in the third step, we let $\xi\in\\{0,1\\}^{n}$ be a random bit string
uniformly sampled from $\\{0,1\\}^{n}$. In the last step we use Fact C.4 and
the fact that
$\prod_{i=1}^{n}\big{(}\xi_{i}\partial_{z_{i}}+(1-\xi_{i})(1-z_{i}\partial_{z_{i}})\big{)}=\prod_{i\in[n]:\xi_{i}=1}\partial_{z_{i}}\prod_{i\in[n]:\xi_{i}=0}(1-z_{i}\partial_{z_{i}})$.
Setting $g_{2}\in\mathbb{R}[t]$ as

$\displaystyle
g_{2}(t):=x^{\sum_{i=2}^{n}\xi_{i}}\cdot\prod_{i=2}^{n}\big{(}\xi_{i}\partial_{z_{i}}+(1-\xi_{i})(1-x\partial_{z_{i}})\big{)}g(t,x+z_{2},x+z_{3},\cdots,x+z_{n})\Big{|}_{z_{2},\dots,z_{n}=0}$

and $x_{2}=x^{2}e-\sum_{i=2}^{n}\xi_{i}v_{i}$, we can simplify the above
equation as

$\displaystyle\leavevmode\nobreak\ x^{d_{\mu}}\cdot
2^{-n}\cdot\operatorname*{{\mathbb{E}}}_{T\sim\mu}\left[h(x^{2}e-(\sum_{i\in
T}v_{i}))\right]$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{2}\operatorname*{{\mathbb{E}}}_{\xi_{2},\cdots,\xi_{n}\sim\\{0,1\\}^{n-1}}\left[h(x_{2}-v_{1})x\partial_{z_{1}}g_{2}(x+z_{1})+h(x_{2})(1-x\partial{z_{1}})g_{2}(x+z_{1})\Bigg{|}_{z_{1}=0}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{2}\operatorname*{{\mathbb{E}}}_{\xi_{2},\cdots,\xi_{n}\sim\\{0,1\\}^{n-1}}\left[(1-\partial_{z_{1}})h(x_{2}+z_{1}v_{1})x\partial_{z_{1}}g_{2}(x+z_{1})+h(x_{2})(1-x\partial_{z_{1}})g_{2}(x+z_{1})\Bigg{|}_{z_{1}=0}\right].$
(21)

Now, we can expand the term inside the expectation of Eqn. (21), and get that

$\displaystyle\leavevmode\nobreak\
(1-\partial_{z_{1}})h(x_{2}+z_{1}v_{1})x\partial_{z_{1}}g_{2}(x+z_{1})+h(x_{2})(1-x\partial_{z_{1}})g_{2}(x+z_{1})\Bigg{|}_{z_{1}=0}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
xh(x_{2}+z_{1}v_{1})(\partial_{z_{1}}g_{2}(x+z_{1}))-x(\partial_{z_{1}}h(x_{2}+z_{1}v_{1}))(\partial_{z_{1}}g_{2}(x+z_{1}))$
$\displaystyle\leavevmode\nobreak\
+h(x_{2})g_{2}(x+z_{1})-h(x_{2})(x\partial_{z_{1}}g_{2}(x+z_{1}))\Bigg{|}_{z_{1}=0}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
xh(x_{2})(Dg_{2})(x)-x(D_{v_{1}}h)(x_{2})(Dg_{2})(x)+h(x_{2})g_{2}(x)-xh(x_{2})(Dg_{2})(x)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
h(x_{2})g_{2}(x)-xD_{v_{1}}h(x_{2})(Dg_{2})(x)$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
(1-\frac{x}{2}\partial^{2}_{z_{1}})\Big{(}h(x_{2}+z_{1}v_{1})g_{2}(x+z_{1})\Big{)}\Bigg{|}_{z_{1}=0},$

where the last step follows from $\operatorname{rank}_{h}(v_{1})\leq 1$ and
$\deg(g_{2})\leq 1$.

Therefore, the left-hand-side of (19) equals to

$\displaystyle\leavevmode\nobreak\ x^{d_{\mu}}\cdot
2^{-n}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{2}\operatorname*{{\mathbb{E}}}_{\xi_{2},\dots,\xi_{n}}\left[(1-\frac{x}{2}\partial^{2}_{z_{1}})\Big{(}h(x_{2}+z_{1}v_{1})g_{2}(x+z_{1})\Big{)}\Bigg{|}_{z_{1}=0}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{2}(1-\frac{x}{2}\partial^{2}_{z_{1}})\left(\operatorname*{{\mathbb{E}}}_{\xi_{2},\dots,\xi_{n}}\left[h(xe-\sum_{i=2}^{n}\xi_{i}v_{i}+z_{1}v_{1})g_{2}(x+z_{1})\right]\right)\Bigg{|}_{z_{1}=0}.$
(22)

If we repeat this process for $n$ times, we will finally get

$\displaystyle
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]=$
$\displaystyle\leavevmode\nobreak\
\prod_{i=1}^{n}(1-\frac{x}{2}\partial^{2}_{z_{i}})\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}.$ (23)

Now we show that the right-hand-side of (23) equals to the right-hand-side of
(19). First, we expand the product of partial operator
$\prod_{i=1}^{n}(1-\frac{x}{2}\partial^{2}_{z_{i}})$ and get that

$\displaystyle\prod_{i=1}^{n}(1-\frac{x}{2}\partial^{2}_{z_{i}})\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}=$ $\displaystyle\leavevmode\nobreak\
\sum_{T\subseteq[n]}(-\frac{x}{2})^{|T|}\partial_{z^{T}}^{2}\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}.$

For any $T\subseteq[n]$ with $|T|=k$, we have

$\displaystyle(-\frac{x}{2})^{k}\partial_{z^{T}}^{2}\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}=$ $\displaystyle\leavevmode\nobreak\
(-\frac{x}{2})^{k}\cdot 2^{k}\cdot\left(\prod_{i\in
T}D_{v_{i}}\right)h(x^{2}e)\cdot g_{\mu}^{(T)}(x{\bf 1}),$

where $g_{\mu}^{(T)}(x{\bf 1})=\prod_{i\in T}\partial_{z_{i}}g_{\mu}(x{\bf
1}+z)\Big{|}_{z=0}$.

Since $h$ is $d$-homogeneous, we know that $(\prod_{i\in T}D_{v_{i}})h$ is
$(d-k)$-homogeneous. Hence, we get that

$\displaystyle(-\frac{x}{2})^{k}\partial_{z^{T}}^{2}\Big{(}h(x^{2}e+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}=$ $\displaystyle\leavevmode\nobreak\
(-\frac{x}{2})^{k}\cdot 2^{k}\cdot x^{d-k}\cdot\left(\prod_{i\in
T}D_{v_{i}}\right)h(xe)\cdot g_{\mu}^{(T)}(x{\bf 1})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ x^{d}\cdot(-1)^{k}\cdot\left(\prod_{i\in
T}D_{v_{i}}\right)h(xe)\cdot g_{\mu}^{(T)}(x{\bf 1})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
x^{d}\cdot(-\frac{1}{2})^{k}\partial_{z^{T}}^{2}\left(h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\right)\Bigg{|}_{z=0}.$

Therefore,

$\displaystyle
x^{d_{\mu}}\cdot\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]=$
$\displaystyle\leavevmode\nobreak\
\sum_{T\subseteq[n]}x^{d}\cdot(-\frac{1}{2})^{k}\partial_{z^{T}}^{2}\left(h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\right)\Bigg{|}_{z=0}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
x^{d}\cdot\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0},$

which completes the proof of Eqn. (19).

Finally, we show that Eqn. (19) is real-rooted in $x$. Since
$e\in\Gamma_{++}^{h}$ and $v_{1},\dots,v_{n}\in\Gamma^{h}_{+}$, by Claim B.11,
we get that $h(xe+\sum_{i=1}^{n}z_{i}v_{i})$ is real-stable. Furthermore,
since $g_{\mu}(x{\bf 1}+z)$ is real-stable, by Fact A.5,

$\displaystyle h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf 1}+z)$

is also real-stable. Then by Fact A.5 again, we get that

$\displaystyle\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}$

is real-stable. By Fact A.2, it implies that it is real-rooted in $x$.
Equivalently,

$\displaystyle
q_{\emptyset}(x^{2})=\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

is real-rooted in $x$. Then, it is easy to see that

$\displaystyle
q_{\emptyset}(x)=\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

is also real-rooted in $x$, since a complex root of $q_{\emptyset}(x)$ implies
a complex root of $q_{\emptyset}(x^{2})$.

The lemma is then proved. ∎

###  C.4 Applying barrier argument to bound the largest root of multivariate
polynomial

In this section, we upper bound the largest root of the following multivariate
polynomial:

$\displaystyle\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}$

using the real-stable version of the barrier method in [AO14].

######  Lemma C.10 (Hyperbolic version of Theorem 4.1 in [AO14]).

Let $h\in\mathbb{R}[x_{1},\cdots,x_{m}]$ denote a degree-$d$ hyperbolic
polynomial with hyperbolic direction $e\in\Gamma_{++}^{h}$. Let
$v_{1},\cdots,v_{n}\in\Gamma^{h}_{+}$ be $n$ vectors such that
$\sum_{i=1}^{n}v_{i}=e$ and $\operatorname{tr}_{h}[v_{i}]\leq\epsilon_{2}$ for
all $i\in[n]$. Let $\mu:2^{[n]}\rightarrow\mathbb{R}_{\geq 0}$ be a
$d_{\mu}$-homogeneous strongly Rayleigh probability distribution such that the
marginal probability of each element $i\in[n]$ is at most $\epsilon_{1}$.
Then, all the roots of

$\displaystyle\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\in\mathbb{R}[x,z_{1},\cdots,z_{n}]$

lie below $(\sqrt{4\epsilon+2\epsilon^{2}},0,\cdots,0)\in\mathbb{R}^{n+1}$,
where $\epsilon=\epsilon_{1}+\epsilon_{2}$.

###### Proof.

Let $Q\in\mathbb{R}[x,z_{1},\dots,z_{n}]$ be an $(n+1)$-variate polynomial:

$\displaystyle Q(x,z):=h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf 1}+z).$

We have already proved in Lemma C.9 that $Q(x,z)$ is real-stable.

For $0<t<\alpha$ where $\alpha=\alpha(t)$ is a parameter to be chosen later,
we have

$\displaystyle Q(\alpha,-t{\bf 1})=$ $\displaystyle\leavevmode\nobreak\
h(\alpha e-t\sum_{i=1}^{n}v_{i})g_{\mu}((\alpha-t){\bf 1})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ h((\alpha-t)e)g_{\mu}((\alpha-t){\bf 1})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
(\alpha-t)^{d+d_{\mu}}h(e)g_{\mu}({\bf 1})$ $\displaystyle>$
$\displaystyle\leavevmode\nobreak\ 0,$

where the second step follows from $\sum_{i=1}^{n}v_{i}=e$ and the last step
follows from $\alpha>t$, $h(e)>0$ and $g_{\mu}({\bf 1})=1$. This implies that
$(\alpha,-t{\bf 1})\in\mathbf{Ab}_{Q}$.

We can upper bound $\Phi_{Q}^{i}(\alpha,-t{\bf 1})$ as follows.

$\displaystyle\Phi_{Q}^{i}(\alpha,-t{\bf 1})=$
$\displaystyle\leavevmode\nobreak\
\frac{\partial_{z_{i}}Q}{Q}\Bigg{|}_{x=\alpha,z=-t{\bf 1}}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\frac{(\partial_{z_{i}}h(xe+\sum_{i=1}^{n}z_{i}v_{i}))g_{\mu}(x{\bf
1}+z)+h(xe+\sum_{i=1}^{n}z_{i}v_{i})(\partial_{z_{i}}g_{\mu}({\bf
1}+z))}{h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)}\Bigg{|}_{x=\alpha,z=-t{\bf 1}}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\frac{\partial_{z_{i}}h(xe+\sum_{i=1}^{n}z_{i}v_{i})}{h(xe+\sum_{i=1}^{n}z_{i}v_{i})}+\frac{\partial_{z_{i}}g_{\mu}(x{\bf
1}+z)}{g_{\mu}(x{\bf 1}+z)}\Bigg{|}_{x=\alpha,z=-t{\bf 1}}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\frac{D_{v_{i}}h(xe+\sum_{i=1}^{n}z_{i}v_{i})}{h(xe+\sum_{i=1}^{n}z_{i}v_{i})}+\frac{\partial_{z_{i}}g_{\mu}(x{\bf
1}+z)}{g_{\mu}(x{\bf 1}+z)}\Bigg{|}_{x=\alpha,z=-t{\bf 1}}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \frac{D_{v_{i}}h(\alpha e-te)}{h(\alpha
e-te)}+\frac{(\alpha-t)^{d_{\mu}-1}\cdot\Pr_{S\sim\mu}[i\in
S]}{(\alpha-t)^{d_{\mu}}}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\frac{\operatorname{tr}[v_{i}]}{\alpha-t}+\frac{\epsilon_{1}}{\alpha-t}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\epsilon_{1}+\epsilon_{2}}{\alpha-t},$

where the first inequality follows from Fact B.3.

Let $\epsilon:=\epsilon_{1}+\epsilon_{2}$. By choosing
$\alpha=2t=\sqrt{4\epsilon+2\epsilon^{2}}$, we get that

$\displaystyle\Phi_{Q}^{i}(\alpha,-t{\bf
1})\leq\frac{\epsilon}{\sqrt{\epsilon+\epsilon^{2}/2}}=\frac{\sqrt{2}}{\sqrt{1+2/\epsilon}}<\sqrt{2}.$

Then, by Lemma A.23, we know that $(\alpha,-t{\bf
1})\in\mathbf{Ab}_{(1-\frac{1}{2}\partial_{z_{i}}^{2})Q}$ for any $i\in[m]$.

Furthermore,

$\displaystyle\frac{1}{t}\Phi_{Q}^{i}(\alpha,-t{\bf
1})+\frac{1}{2}\Phi_{Q}^{i}(\alpha,-t{\bf 1})^{2}\leq$
$\displaystyle\leavevmode\nobreak\
\frac{\epsilon}{t^{2}}+\frac{1}{2}\frac{\epsilon^{2}}{t^{2}}=1.$

By the second part of Lemma A.23, we have for all $j\in[m]$,

$\displaystyle\Phi^{j}_{(1-\frac{1}{2}\partial_{z_{i}}^{2})Q}(\alpha,-t{\bf
1}+t{\bf 1}_{i})\leq\Phi_{Q}^{j}(\alpha,-t{\bf 1}).$

By a similar induction process like in the proof of Lemma B.14, we have

$\displaystyle(\alpha,-t{\bf 1}+\sum_{i=1}^{n}t{\bf 1}_{i})$
$\displaystyle=(\sqrt{4\epsilon+2\epsilon^{2}},0,0,\dots,0)$
$\displaystyle\in\mathbf{Ab}_{\prod_{i=1}^{n}(1-\partial_{z_{i}}^{2}/2)Q}$

i.e. $(\sqrt{4\epsilon+2\epsilon^{2}},0,0,\dots,0)$ lies above the roots of

$\displaystyle\prod_{i=1}^{n}\Big{(}1-\frac{1}{2}\frac{\partial^{2}}{\partial
z_{i}^{2}}\Big{)}\left[h\Big{(}xe+\sum_{i=1}^{n}\xi_{i}v_{i}\Big{)}\cdot
g_{\mu}(x{\bf 1}+z)\right]$

as desired. ∎

###  C.5 Combining together: proof of Theorem C.1

Now we can combine the results from the previous section and prove Theorem
C.1:

###### Proof of Theorem C.1.

Let $\mathcal{F}$ be the support of $\mu$.

By Lemma C.10 and restricting to $z_{i}=0$ for all $i\in[n]$, we have that
$\sqrt{4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}}$ lies
above the largest root of the univariate polynomial

$\displaystyle\prod_{i=1}^{n}(1-\frac{1}{2}\partial^{2}_{z_{i}})\Big{(}h(xe+\sum_{i=1}^{n}z_{i}v_{i})g_{\mu}(x{\bf
1}+z)\Big{)}\Bigg{|}_{z=0}.$

We then conclude by Lemma C.9 that
$\sqrt{4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}}$ upper
bounds the largest root of

$\displaystyle\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(x^{2}e-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right].$

Therefore, the largest root of

$\displaystyle
q_{\emptyset}=\operatorname*{{\mathbb{E}}}_{\xi\sim\mu}\left[h(xe-(\sum_{i=1}^{n}\xi_{i}v_{i}))\right]$

is upper bounded by
$4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}$, where
$q_{\emptyset}$ is the average of the polynomials in the interlacing family
$\mathcal{Q}$ in Definition C.6.

Finally, by Corollary C.8, there exists $S\subseteq[n]$ in the support of
$\mu$, such that

$\displaystyle\Big{\|}\sum_{i\in S}v_{i}\Big{\|}_{h}\leq
4(\epsilon_{1}+\epsilon_{2})+2(\epsilon_{1}+\epsilon_{2})^{2}.$

∎

##  Appendix D Sub-Exponential Algorithms

###  D.1 Definitions

######  Definition D.1 ($k$-th symmetric polynomials).

For any $n\in\operatorname*{\mathbb{Z}}_{+},k\leq n$, let
$e_{k}\in\mathbb{R}[z_{1},\cdots,z_{n}]$ denote the $k$-th elementary
symmetric polynomial defined as

$\displaystyle e_{k}(z_{1},\cdots,z_{n})=\sum_{T\in\binom{[n]}{k}}\prod_{i\in
T}z_{i}.$

######  Definition D.2 ($k$-th power sum polynomials).

For any $n,k\in\operatorname*{\mathbb{Z}}_{+}$, let
$p_{k}\in\mathbb{R}[z_{1},\cdots,z_{n}]$ denote the $k$-th power sum
polynomial defined as $p_{k}(z_{1},\cdots,z_{n})=\sum_{i=1}^{n}z_{i}^{k}$.

######  Fact D.3 (Vieta’s formulas).

Let $f\in\mathbb{R}[x]$ be any degree $n$ monic variate polynomial defined as
$f(x)=x^{n}+c_{1}x^{n-1}+\cdots+c_{n}$. Then for any $k\in[n]$,

$\displaystyle c_{k}=(-1)^{k}e_{k}(\lambda_{1},\cdots,\lambda_{n}).$

Where $\lambda_{1},\cdots,\lambda_{n}\in\operatorname*{\mathbb{C}}$ are the
roots of $f$, and $e_{k}$ is the $k$-th elementary symmetric polynomial
defined in Definition D.1.

######  Fact D.4 (Newton’s identities).

For any $n\in\operatorname*{\mathbb{Z}}_{+},k\in[n]$, let
$e_{k},p_{k}\in\mathbb{R}[z_{1},\cdots,z_{n}]$ be defined in Definition D.1
and Definition D.2 respectively. Then there exists an $O(k^{2})$-time
algorithm $\textsc{ElemToPower}(k,e_{1},\cdots,e_{k})$, such that given any
$k\in[n]$, and any $e_{1}=e_{1}(x),\cdots,e_{k}=e_{k}(x)$ for some fixed
$x\in\mathbb{R}^{n}$, outputs $p_{k}=p_{k}(x)$.

###  D.2 Algorithm to approximate the largest root

Algorithm 1 Algorithm approximating the largest root.

1:procedure
MaxRoot($n\in\operatorname*{\mathbb{Z}}_{+},k\in[n],f\in\mathbb{R}[x],c_{1},\cdots,c_{k}\in\mathbb{R}$)

2: Precondition: $k\leq n$, $c_{1},\cdots,c_{k}\in\mathbb{R}$ are the top-$k$
coefficients of a degree $n$ real-rooted monic-variate polynomial
$f\in\mathbb{R}[x]$.

3: Output: Return an approximate of the largest root of $f$.

4: for $i=1$ to $k$ do

5: $e_{k}\leftarrow c_{k}\cdot(-1)^{k}$.

6:$\triangleright$ $e_{k}=e_{k}(\lambda_{1},\cdots,\lambda_{n})$ is the $k$-th
elementary polynomial of the roots of $f$ by Fact D.3.

7: end for

8: $p_{k}\leftarrow\textsc{ElemToPower}(k,e_{1},\cdots,e_{k})$

9:$\triangleright$ $p_{k}(\lambda)=\lambda_{1}^{k}+\cdots+\lambda_{n}^{k}$ is
the power sum of the roots of $f$ by Fact D.4.

10: Return $(p_{k})^{1/k}$.

11:end procedure

######  Lemma D.5.

Let $f=x^{n}+c_{1}x^{n-1}+\cdots+c_{n}\in R[x]$ be any degree $n$ real-rooted
monic-variate polynomial. Then $\textsc{MaxRoot}(n,k,f,c_{1},\cdots,c_{k})$
(Algorithm 1) returns an $(n^{1/k})$-approximate of the largest root of $f$ in
time $O(k^{2}+k)$.

###### Proof.

Let $\lambda_{1}\geq\lambda_{2}\geq\lambda_{n}\in\mathbb{R}$ denote the roots
of $f(x)$. By Fact D.3 and Fact D.4, Algorithm 1 returns $(p_{k})^{1/k}$,
where $p_{k}=\lambda_{1}^{k}+\cdots+\lambda_{n}^{k}$. Notice that

$\displaystyle\frac{\lambda_{1}^{k}+\cdots+\lambda_{n}^{k}}{n}\leq\lambda_{1}^{k}\leq\lambda_{1}^{k}+\cdots+\lambda_{n}^{k}$

we have

$\displaystyle\lambda_{1}\leq(p_{k}/n)^{1/k}\leq n^{1/k}\lambda_{1}.$

∎

######  Remark D.6.

We remark that when $k>\log n$, the approximation factor $n^{1/k}$ is upper
bounded by $1+\frac{\log n}{k}$.

###  D.3 Reducing Kadison-Singer to finding leading coefficients of
interlacing polynomial

We define an oracle that generates the top-$k$ coefficients as follows:

######  Definition D.7.

Fix a family of degree $n$ monic-variable polynomials
$\mathcal{F}=\\{f_{s_{1},\cdots,s_{m}}\in\mathbb{R}[x]:s_{1},\cdots
s_{\ell}\in S_{1}\times\cdots\times S_{\ell}\\}$. We define oracle
$\textsc{MaxCoeff}_{\mathcal{F}}(k,\ell,s_{1},\cdots s_{\ell})$ as follows:
given any $k\in[n],\ell\in[m],s_{1},\cdots s_{\ell}\in S_{1}\times\cdots\times
S_{\ell}$ as inputs, and it outputs the top-$k$ coefficients of
$f_{s_{1}\cdots s_{\ell}}$ in $\mathcal{T}_{\mathrm{Coeff}}(\mathcal{F},k)$
time.

######  Lemma D.8 (Theorem 4.4 of [AOSS18]).

Let $S_{1},\cdots,S_{m}$ be finite sets and let $\mathcal{F}=\\{f_{s_{1}\cdots
s_{m}}(x)\in\mathbb{R}[x]:s_{1}\in S_{1},\cdots,s_{m}\in S_{m}\\}$ be an