Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Introduction

Rounding is a crucial step in the design of many approximation algorithms. Given a fractional vector satisfying some constraints, a rounding method produces an integer vector that satisfies those constraints, either exactly or approximately. Randomized rounding [57, Chapter 5], in which the coordinates of the fractional vector are rounded randomly and independently, produces good integer vectors for many applications. Dependent rounding methods, in which the resulting integer vector does not have independent coordinates, are important in many scenarios where naive randomized rounding does poorly. Various techniques exist for designing dependent rounding methods (see, e.g., the surveys ).

It is common for a rounding scenario to involve two types of constraints: hard constraints, which must be satisfied exactly by the integer solution, and soft constraints, which must be approximately satisfied by the integer solution. Low-congestion multi-path routing , max cut with given sizes of parts , thin spanning trees , and submodular maximization under a matroid constraint are examples of problems whose solutions involve such a rounding scenario. The hard constraint is often membership in an integer polytope that is defined using combinatorial objects (e.g., matchings or matroids). The soft constraints are usually simple linear inequalities.

With randomized rounding, the independent choices lead to concentration of measure phenomena that are useful for handling soft constraints. For example, Chernoff bounds are commonly used to show that linear inequalities are approximately satisfied . The past decade has seen various uses of matrix concentration bounds (e.g., ) to show that linear matrix inequalities are approximately satisfied by random sampling or rounding. Such uses have occurred in many diverse areas: graph sparsification , compressed sensing , statistics , machine learning and numerical linear algebra .

With dependent rounding, concentration phenomena can also occur. Pipage rounding, swap rounding and maximum entropy sampling are dependent rounding techniques that have seen many important uses over the past decade . An important feature in some scenarios is that any Chernoff bound that is valid under independent randomized rounding remains valid under these dependent rounding techniques. This fact is proven by showing that the rounded solution has a negatively correlated distribution, then appealing to the fact that Chernoff bounds remain valid under such distributions . Unfortunately, commutativity plays a key role in proving that fact, and these arguments do not seem to extend to matrix concentration bounds, e.g., . Consequently, these matrix inequalities have so far not been combined with dependent rounding.

We prove the first result showing that matrix concentration bounds are usable in a dependent rounding scenario. Our technique is not based on negative correlation, but rather the fortuitous interaction between pipage rounding and various pessimistic estimators. In particular, we show that Tropp’s matrix Chernoff bound has a pessimistic estimator that decreases monotonically under pipage rounding. As a consequence, we can extend the reach of pipage rounding from soft constraints that are linear inequalities to soft constraints that are linear matrix inequalities. Our proof uses non-trivial techniques from matrix analysis and complex analysis; in particular, we prove a new variant of Lieb’s concavity theorem.

One key area where our techniques yield new results is for thin spanning trees. These are intriguing objects in graph theory that relate to foundational topics, such as nowhere-zero flows , and the asymmetric traveling salesman problem . Given a graph $G$ on $n$ nodes, a spanning tree $T$ of $G$ is $\alpha$-thin if, for every cut, the number of edges of $T$ crossing the cut is at most $\alpha$ times the number of edges of $G$ crossing the cut. It has been conjectured that any graph with connectivity $k$ has an $f(k)$-thin spanning tree where $f(k)=O(1/k)$. This would imply a constant factor approximation algorithm for the asymmetric traveling salesman problem . Asadpour et al. give a randomized algorithm to find a spanning tree that is $O(\frac{\log n}{k\log\log n})$-thin. Later Chekuri et al. gave a simpler algorithm using randomized pipage rounding or swap rounding.

A spectrally-thin spanning tree is a stronger notion that is naturally motivated by work on spectral sparsification . A spanning tree $T$ is $\alpha$-spectrally-thin if $L_{T}\preceq\alpha L_{G}$, where $L_{G}$ refers to the Laplacian of $G$, and $\preceq$ to the Löwner ordering of Hermitian matrices. In

thin

, we show a result on spectrally thin trees that strongly mirrors the result of Asadpour et al.

There is a deterministic, polynomial-time algorithm that given any graph on $n$ nodes where every edge has effective conductance at least $\kappa$, constructs a $O(\frac{\log n}{\kappa\log\log n})$-spectrally-thin spanning subtree.

This spectral notion of thinness seems to be an important one, as the recent breakthrough of Marcus et al. implies that $O(1/\kappa)$-spectrally-thin trees exist. Details of this connection are given in Appendix G. It is unknown if similar techniques can show that $O(1/k)$-thin trees exist. The best known algorithmic construction of spectrally-thin trees is still Theorem 2.1.

isotropic

, we show how to find in polynomial time a basis $V_{B}\subseteq V$ for which the maximum eigenvalue of $\sum_{i\in B}v_{i}v_{i}^{\mathsf{T}}$ is $O(\log n/\log\log n)$. Previous constructive techniques only provide a bound of $O(\log n)$.

Our geometric result also relates to the column subset selection problem in numerical linear algebra which seeks to “approximate” a matrix $A$ by a small subset of its columns, under various notions of approximation. Define the stable rank of $A$ to be the Frobenius norm divided by the spectral norm, all squared; this roughly captures the rank of $A$, ignoring negligibly small singular values. In numerical linear algebra , the number of columns chosen is typically much larger than the stable rank. The operator theory community considers similar questions , although the number of columns selected is typically much smaller than the stable rank. In

CSS

, we show that one can efficiently select a linearly independent set of columns of size equal to the stable rank, while carefully controlling the maximum singular value.

Our results are based on the pipage rounding technique , which has had several interesting uses in the recent literature. Deterministic and randomized forms of pipage rounding exist; our result applies to both of those, as well as to swap rounding. Typical uses of pipage rounding involve some of the following ideas.

There are processes that iteratively move a point in a matroid base polytope towards an extreme point, while modifying only two coordinates at a time. The exchange properties of matroid bases ensure that this is possible.

One can define a “potential function” on the matroid base polytope (e.g., the ad hoc functions defined in , or the multilinear extension of a submodular function ) such that the function is concave or convex in directions that increase one coordinate and decrease another.

The randomized form of pipage rounding outputs a matroid base whose elements are negatively correlated (more precisely, negative cylinder dependent). This ensures that linear functions of that base satisfy the same Chernoff-type concentration bounds that are satisfied under independent rounding.

Our aim is to show that, for various concentration bounds, the final extreme point satisfies the same bounds that would be achieved by independent randomized rounding. For Chernoff bounds this follows from negative correlation, but for other bounds such a result was not previously known.

Let $f$ be a monotone submodular function defined on the ground set of the matroid. When using randomized pipage rounding, does the value of $f$ at the final extreme point satisfy the same lower tail bound as when using independent rounding? Chekuri et al. conjectured this to be true, and they proved such a result when using swap rounding.

Let $f$ be a linear function mapping points in the matroid base polytope to symmetric matrices. When using pipage rounding, can the value of $f$ at the final extreme point be guaranteed to satisfy the same eigenvalue bounds as when using independent rounding?

It does not seem easy to answer these questions using negative correlation properties.

We present a new approach that leads to a positive answer to both of these questions. In both cases, we can define a pessimistic estimator that bounds the probability that randomized rounding fails to achieve the desired concentration. We show that these pessimistic estimators are concave when one element’s sampling probability is increased and another’s is decreased by the same amount. Due to that concavity property, the base output by randomized pipage rounding satisfies the same concentration bounds that would be satisfied under independent randomized rounding. For the second question (matrix concentration), the pessimistic estimator can be efficiently evaluated, so deterministic pipage rounding can also be used.

The concavity property of our pessimistic estimator for matrix concentration is a non-trivial fact. We establish that fact by proving a new variant of Lieb’s concavity theorem , which is a “masterpiece of matrix analysis” with deep applications in mathematical physics and quantum information theory . Although there is much interest in the mathematical physics community on extensions and variants of Lieb’s theorem, our particular variant does not seem to appear in the literature.

Preliminaries

If $\mathcal{D}$ is a distribution, $X\sim\mathcal{D}$ means that the random variable $X$ has distribution $\mathcal{D}$.

Concavity of Pessimistic Estimators

In this section we state the known results on pipage rounding and our concavity of pessimistic estimators technique. We then apply this technique in three scenarios, of increasing difficulty: (1) Chernoff bounds, (2) submodular functions, and (3) matrix concentration. The latter two results are new, and in particular are not known to follow using negative correlation. This pessimistic estimator for matrix concentration underlies all applications in

applications

Pipage rounding is a dependent rounding process originating in works of Ageev, Srinivasan and Sviridenko . Calinescu et al. generalized it to a matroid setting. We now state the main results of randomized and deterministic pipage rounding; a proof sketch is given in Appendix A.

There is a deterministic, polynomial-time algorithm that, given $x\in P$ and a value oracle for a function $g$ that is concave under swaps, outputs an extreme point $\hat{x}$ of $P$ with $g(\hat{x})\leq g(x)$.

The swap rounding procedure of Chekuri et al. also proves Theorem 7.1 and Theorem 7.2.

For uses of pessimistic estimators in derandomization, the function $g$ is also required to be efficiently computable. That is not required with their use in randomized pipage rounding as $g$ is not even provided as input to the algorithm.

Let $\mathcal{E}\subseteq\left\{0,1\right\}^{m}$ and let $g$ be a function that satisfies (2) and is concave under swaps.

Suppose randomized pipage rounding is started at an initial point $x_{0}\in P$, and let $\hat{x}$ be the (random) extreme point of $P$ that is output. If $g(x_{0})\leq\epsilon$ then .

Suppose deterministic pipage rounding is given oracle access to $g$ and an initial point $x_{0}\in P$ with $g(x_{0})<1$. Then the extreme point $\hat{x}$ of $P$ that is output satisfies $\hat{x}\not\in\mathcal{E}$.

We omit the proof of Claim 1 as it is an easy consequence of Theorem 7.1 and Theorem 7.2.

2 Chernoff bound

Let $\mu=w^{\mathsf{T}}x$ and $\delta\geq 0$. Then

The following claim is proven in Appendix B.

Consequently, Claim 1 implies the following result.

If randomized pipage rounding starts at $x_{0}\in P$ and outputs the extreme point $\hat{x}$ of $P$ then, $\forall w\in^{m},\,\delta\geq 0$,

where $\mu=w^{\mathsf{T}}x_{0}$. Furthermore, if this right-hand side is strictly less than $1$, then deterministic pipage rounding outputs an extreme point $\hat{x}$ of $P$ with $w^{\mathsf{T}}\hat{x}<(1+\delta)\mu$.

The key point is that the right-hand sides of (3) and (4) are the same. Chekuri et al. proved this fact using negative correlation of $\hat{x}$, generalizing a result of Srinivasan .

3 Submodular functions

Chekuri et al. [19, Theorem 1.3] prove an analog of the Chernoff bound for concentration of submodular functions under independent rounding. They show that the same bound remains true under swap rounding [19, Theorem 1.4] and ask whether it remains true under pipage rounding.

The left tail bound of Chekuri et al. is: with $\mu=F(x),\,\delta\in[0,1)$,

The following claim is proven in Appendix B.

Claim 1 implies the following result, answering an open question of Chekuri et al. [19, p. 3].

If randomized pipage rounding starts at $x_{0}\in P$ and outputs the extreme point $\hat{x}$ of $P$ then, letting $\mu=F(x_{0})$, we have .

Chekuri et al. [20, p. 583] state that this fact does not follow from negative correlation of $\hat{x}$.

4 Matrix Concentration

Tropp , improving on Ahlswede-Winter and Oliviera , proves a beautiful analog of the Chernoff bound for sums of independent random matrices. We state a simplified form here.

The following is our main lemma on pessimistic estimators. The proof is in Appendix B.

Consequently, Claim 1 implies the following result.

Furthermore, if this right-hand side is strictly less than $1$, then deterministic pipage rounding outputs an extreme point $\hat{x}=\chi(S)$ of $P$ with $\left\lVert\sum_{i\in S}M_{i}\right\rVert<(1+\delta)\mu$.

The inequalities in Theorem 7.5 involve non-trivial matrix analysis, such as operator concavity of $\log$ and Lieb’s celebrated concavity theorem . It seems that even those results do not suffice to prove Lemma 7.6. To prove it, we derive a new variant of Lieb’s theorem (Theorem 7.9). Lieb proved several related concavity theorems; for us, the most relevant form is:

The main technical result of this paper is:

There are several known approaches to proving Lieb’s theorem. The simplest is Tropp’s approach ; however, his proof is based on joint convexity of quantum entropy, which is itself usually proven using Lieb’s theorem. We were unable to prove Theorem 7.9 using Tropp’s approach. Lieb’s original proof , which proves concavity by directly analyzing the second derivative, involves numerous delicate steps of matrix analysis. We were able to adapt this approach to prove a weaker form of Theorem 7.9 that requires some additional commutativity assumptions; details are in Appendix F. This weaker result suffices to prove Lemma 7.6. Epstein gives an elegant approach to proving Lieb’s theorem using complex analysis, and in particular powerful results concerning Herglotz functions. Our proof of Theorem 7.9, which appears in Appendix E, is an adaptation of Epstein’s approach.

Remark. Another well-known matrix concentration inequality is the Ahlswede-Winter inequality, for which pessimistic estimators were studied by Wigderson and Xiao . It is natural to wonder whether we could have used their pessimistic estimators instead. Unfortunately they do not seem applicable for our scenario. The issue is that the Ahlswede-Winter inequality is most effective for analyzing sums of i.i.d. random matrices, due to some inequalities that arise in their analysis. In our scenario, due to the way that pipage rounding works, we require non-i.i.d. product distributions, so it is much more convenient to base our approach on Theorem 7.5.

Applications

Suppose that $A_{i}\preceq B$ for all $i$. If randomized pipage rounding starts at $x_{0}\in Q$ and outputs the extreme point $\chi(S)$ of $P$, then , for some $\alpha=O(\log n/\log\log n)$. Furthermore, if deterministic pipage rounding starts at $x_{0}\in Q$, then it outputs an extreme point $\chi(S)$ of $P$ with ${\textstyle\sum_{i\in S}}A_{i}\preceq\alpha B$.

This theorem is optimal with respect to $\alpha$, as discussed below. The hypothesis that $A_{i}\preceq B$ is a “width” condition that commonly arises in optimization and rounding.

prelim

. Let $M_{i}=B^{+/2}A_{i}B^{+/2}$. By standard arguments,

Chekuri, Vondrák and Zenklusen considered the problem of rounding a point in a matroid polytope to an extreme point, subject to additional packing constraints. Their result generalizes the low-congestion multi-path routing problem studied earlier by Srinivasan et al. , but it is itself a special case of Theorem 8.1 where the matrices $A_{i}$ and $B$ are diagonal. The factor $\alpha=O(\log n/\log\log n)$ is optimal in Theorem 8.1 because it is optimal for rounding this low-congestion multi-path routing problem, and even for the congestion minimization problem .

As is discussed in Appendix G, the recent breakthrough on the Kadison-Singer problem implies the following existential result:

Define $A_{i}=w_{i}w_{i}^{\mathsf{T}}$, $B=I$ and

Let $x=n\cdot p$. Then the following claim and the hypothesis that $\sum_{i}p_{i}w_{i}w_{i}^{\mathsf{T}}=I/n$ show that $x\in Q$.

In Appendix C.1, we show that Theorem 9.1 can be generalized from a decomposition of the identity into rank-one matrices $w_{i}w_{i}^{\mathsf{T}}$ to a decomposition into matrices of arbitrary rank. The proof of Claim 9 is analogous to the proof of Claim 12. We remark that Theorem 9.2 is not known to have a generalization to matrices of arbitrary rank.

2 Thin trees

Let $G=(V,E)$ be a graph. For convenience we assume that $V=[n]$. The cut defined by $U\subseteq V$ is

For a subgraph $T$ of $G$, let $\delta_{T}(U)$ denote all edges of $T$ with exactly one endpoint in $U$.

A subgraph $T$ of $G$ is called $\epsilon$-thin if $\lvert\delta_{T}(U)\rvert\leq\epsilon\cdot\lvert\delta_{G}(U)\rvert$ for all $U\subseteq V$.

Every graph with connectivity at least $k$ has an $f(k)$-thin spanning subtree, for some function $f$ that vanishes as $k$ tends to infinity.

The crucial detail in this conjecture is that the function $f$ should not depend on the size of the graph. The best progress on this conjecture for general graphs is as follows.

Let $G$ be a graph with $n$ vertices and connectivity $k$. Then $G$ has a O\big{(}\frac{\log n}{k\log\log n}\big{)}-thin spanning subtree. Moreover, there is a randomized, polynomial time algorithm to construct such a tree.

Now we define spectrally-thin trees and prove an analog of this theorem. The Laplacian of $G$ is the symmetric matrix $L_{G}$ with rows and columns indexed by $V$ defined by

Let $T$ be a spanning subtree of $G$ and let $L_{T}$ be the Laplacian of $T$. The tree $T$ is $\epsilon$-spectrally-thin if $L_{T}\preceq\epsilon L_{G}$.

Any tree that is $\epsilon$-spectrally-thin is also $\epsilon$-thin, because

The converse is not true. Moreover, the connectivity hypothesis in Theorem 9.5 does not suffice This result was independently observed by M. de Carli Silva, N. Harvey and C. Sato, and by M. Goemans , using slightly different examples. to obtain a good spectrally-thin tree. The proof is in Appendix D.0.1.

For every $n,k\geq 1$, there exists a weighted graph with $n$ vertices and connectivity $k$ that does not have an $o(\sqrt{n}/k)$-spectrally-thin spanning subtree.

Nevertheless, if we strengthen the connectivity lower bound to a lower bound on the effective conductances, then we have the following construction of spectrally-thin trees. For an edge $e=uv\in E$, the effective resistance in $G$ between $u$ and $v$ is $R_{e}:=(e_{u}-e_{v})^{\mathsf{T}}L_{G}^{+}(e_{u}-e_{v})$. The effective conductance in $G$ between $u$ and $v$ is $C_{e}:=1/R_{e}$.

Let $G$ be a graph with $n$ vertices such that $\kappa\leq C_{e}$ for every edge $e$. Then there is a polynomial time algorithm (either randomized or deterministic) to construct a O\big{(}\frac{\log n}{\kappa\log\log n}\big{)}-spectrally-thin spanning subtree of $G$.

Theorem 9.8 follows directly from Theorem 8.1, letting $\mathbf{M}$ be the graphic matroid corresponding to $G$. It also follows from Theorem 9.1, as we show in Appendix C.2. That viewpoint is advantageous, since Theorem 9.2 then immediately implies

Let $G$ be a graph with $n$ vertices such that $\kappa\leq C_{e}$ for every edge $e$. Then $G$ has a $O(1/\kappa)$-spectrally-thin spanning subtree.

We are not aware of any formal connection between Theorem 9.9 and Conjecture 9.4 or the traveling salesman problem.

Although Theorem 9.5 and Theorem 9.8 are formally incomparable, it is worth understanding their similarities and differences. Both results have a seemingly suboptimal factor of $\log n/\log\log n$. Theorem 9.5 requires only a connectivity lower bound, which is important in applications , but the resulting tree is thin, not spectrally-thin; also, their algorithm is randomized. Theorem 9.8 requires a conductance lower bound (which is stronger than a connectivity lower bound), but the resulting tree is spectrally-thin (which is stronger than being thin); also, our algorithm can be made deterministic. The use of randomization seems quite inherent in the algorithms for Theorem 9.5, as the thinness condition involves controlling exponentially many cuts, which seems difficult to accomplish by a deterministic, polynomial-time algorithm.

The quantities $k$ and $\kappa$ can be related in certain classes of graphs. We say that a family of graphs has nearly equal resistances if there is a constant $c$ (independent of the number of vertices) such that $R_{e}\leq cR_{f}$ for all edges $e,f$. For example, any Ramanujan graph has nearly equal resistances. Edge-transitive graphs, such as hypercubes, have nearly equal (in fact, exactly equal) resistances.

Let $G$ be a graph with $n$ vertices, nearly equal resistances, and connectivity $k$. Then there is a deterministic, polynomial time algorithm to construct a O\big{(}\frac{\log n}{k\log\log n}\big{)}-spectrally-thin tree of $G$.

3 Column-subset selection

Column-subset selection is an important topic in numerical linear algebra . Similar questions are considered in operator theory . In this section we prove a non-isotropic analog of Theorem 9.1, which gives a new result on column-subset selection. For a real matrix $A$, let $\left\lVert A\right\rVert_{F}=\sqrt{\operatorname{tr}A^{\mathsf{T}}A}$ denote its Frobenius norm. The stable rank of $A$ is $\operatorname{st.rank}(A):=\left\lVert A\right\rVert_{F}^{2}/\left\lVert A\right\rVert^{2}$.

Let $A$ be a real matrix of size $n\times m$ whose columns are denoted $a_{1},\ldots,a_{m}$. Suppose that $\left\lVert a_{i}\right\rVert=1~{}\,\forall i$. Then there is a deterministic, polynomial time algorithm to compute $S\subseteq[m]$ of size $\lvert S\rvert\geq\left\lfloor\operatorname{st.rank}(A)\right\rfloor$ such that $\left\{\,a_{i}\,:\,i\in S\,\right\}$ is linearly independent, and $\left\lVert\sum_{i\in S}a_{i}a_{i}^{\mathsf{T}}\right\rVert\leq O(\log n/\log\log n)$.

This is optimal with respect to $\lvert S\rvert$ as it can happen that $\operatorname{st.rank}(A)=\operatorname{rank}(A)$, in which case $\left\{\,a_{i}\,:\,i\in S\,\right\}$ is linearly dependent whenever $\lvert S\rvert>\operatorname{st.rank}(A)$.

Then $\mathcal{B}$ is the base family of the linear matroid corresponding to $A$, truncated to rank $\left\lfloor\operatorname{st.rank}(A)\right\rfloor$. Let $\mathbf{M}$ denote that matroid and let $P$ denote its base polytope.

The proof is in Appendix D.1. Given this claim, all that remains is an easy application of Theorem 8.1. Define $A_{i}=a_{i}a_{i}^{\mathsf{T}}$, $B=I$ and

We have $p\in Q$ by Claim 10 and the fact that

Note that $A_{i}=a_{i}a_{i}^{\mathsf{T}}\preceq I=B$. Theorem 8.1 gives a deterministic algorithm to construct an extreme point $\chi(S)$ of $P$ for which $\sum_{i\in S}A_{i}\preceq\alpha\cdot B$, with $\alpha=O(\log n/\log\log n)$. Since $S$ is a base of $\mathbf{M}$, the set $\left\{\,a_{i}\,:\,i\in S\,\right\}$ has rank equal to $\lvert S\rvert=\left\lfloor\operatorname{st.rank}(A)\right\rfloor$. This completes the proof of Theorem 9.11.

N. Harvey thanks Joel Friedman and Mohit Singh for numerous enlightening discussions. We thank Isaac Fung for collaborating at a preliminary stage of this work. We also thank Christos Boutsidis, Joseph Cheriyan, Satoru Fujishige, Michel Goemans, Mary Beth Ruskai, Nikhil Srivastava, Joel Tropp, Roman Vershynin and Jan Vondrák for helpful discussions and suggestions.

References

Appendix A Pipage Rounding

Let $p$ be a point in the matroid polytope $P$ and assume that $g$ satisfies (1). Delete all coordinates of $p$ that are equal to zero and consider the residual problem. It is well-known that, for any such point $p$, there exists a chain of sets $\emptyset=C_{0}\subseteq C_{1}\subseteq\cdots C_{k}\subseteq[m]$ whose corresponding constraints of $P$ span the constraints that are tight at $p$. If $\lvert C_{i}\setminus C_{i-1}\rvert=1$ for every $i$ then these give $m$ linearly independent tight constraints, so the point $p$ is an extreme point. Otherwise there is some set $C_{i}$, $i\geq 1$, for which $\lvert C_{i}\setminus C_{i-1}\rvert>1$. In this case $p$ is not an extreme point. To see this, let $a$ and $b$ be distinct elements of $C_{i}\setminus C_{i-1}$. Note that the point $p+z(e_{a}-e_{b})$ satisfies all the constraints that are tight at $p$. So, for all $z$ in some open neighborhood of , the point $p+z(e_{a}-e_{b})$ is still feasible for $P$.

Since g\big{(}p+z(e_{a}-e_{b})\big{)} is concave, we must have either

Appendix B Proofs of concavity under swaps

Rewriting g\big{(}x+z(e_{a}-e_{b})\big{)} in this way, all factors are non-negative and only two of them depend on $z$, so for some $c\geq 0$

This is non-positive so $g$ is concave under swaps.

Since $-h$ is submodular, it follows from results of Calinescu et al. that $\frac{\partial^{2}H}{\partial x_{i}\partial x_{j}}\geq 0$ for any $i,j\in[m]$. Since $g(x)=e^{-\theta t}\cdot H(x)$, the second derivative of

is non-positive. Thus $g$ is concave under swaps.

We require the following property of convex functions. Suppose $a,b,c,d$ satisfy

Then any function $g$ that is convex on $[a,d]$ satisfies

Fix any $A\subseteq B\subseteq[m]$, and an element $x\in[m]\setminus B$. Define

Since $f$ is non-decreasing, (8) holds. Since $f$ is submodular, $e\leq d$ holds. Since $g$ is non-increasing, $g(e)\geq g(d)$. Combining that with (9) and the observation that $d-c=b-a$, we obtain

The boundary of $^{m}$ is handled by continuity. Note that

Adding $z$ (sufficiently small) to the sampling probability of coordinate $i$, the expectation becomes

Note that $C_{i}\succeq I$ and $K_{i}\succeq 0$ because $M_{i}\succeq 0$ and $\theta>0$. Furthermore, the matrices $C_{i}$ and $K_{i}$ commute since any eigenbasis for $M_{i}$ is also an eigenbasis of $C_{i}$ and $K_{i}$.

To finish the proof we must show that, for distinct $a,b\in[m]$,

is concave in a neighborhood of . This follows from Theorem 7.9.

Appendix C Proofs of Applications

Here, we give a generalization of Theorem 9.1 to a decomposition of the identity into matrices of arbitrary rank.

where $V_{J}$ is the matrix obtained by concatenating in any order all columns from the matrices $\left\{\,V_{j}\,:\,j\in J\,\right\}$. It is well-known that such a function $r$ is:

Monotone: $r(I)\leq r(J)$ whenever $I\subseteq J$, and

Submodular: $r(I)+r(J)\geq r(I\cup J)+r(I\cap J)$ for all $I,J\subseteq[m]$.

$P:=\left\{\,x-\left\lfloor p\right\rfloor\,:\,x\in P^{\prime}\,\right\}$ is a matroid base polytope.

Claim 12 is proven below. Claim 13 is a folklore result that can be derived using reductions and contractions of submodular functions [25, §3.1(b)]; see also Fujishige’s remarks on crossing submodular functions [25, Eq. (3.97)].

Define $A_{i}=X_{i}/\operatorname{tr}X_{i}$, $B=I$ and

Setting $x=p-\left\lfloor p\right\rfloor$, we have $x\in P$ by Claim 12 and

Since $\operatorname{tr}A_{i}=1$, we have $A_{i}\preceq B$. Applying Theorem 8.1, we obtain a vector $\hat{x}\in\left\{0,1\right\}^{n}$ that is an extreme point of $P$, and for which $\sum_{i}\hat{x}_{i}A_{i}\preceq\alpha B$. Let $S$ be the support of $\hat{x}$. Note that $\hat{x}+\left\lfloor p\right\rfloor\in P^{\prime}$. So

and $\sum_{i\in S}X_{i}/\operatorname{tr}X_{i}\preceq\alpha B$ as required.

The box constraint $\left\lfloor p\right\rfloor\leq p\leq\left\lceil p\right\rceil$ is trivially satisfied. We have noted above that $\sum_{i}p_{i}=n$, so the constraint $p([m])\leq r([m])=n$ is also satisfied.

It remains to show that $\sum_{i\in I}p_{i}\leq r(I)$ for all $I$. For any positive semidefinite matrix, the average of the non-zero eigenvalues is a lower bound on the maximum eigenvalue, so

Thus $\sum_{i\in I}p_{i}=\operatorname{tr}({\textstyle\sum_{i\in I}}X_{i})\leq\operatorname{rank}({\textstyle\sum_{i\in I}}X_{i})=r(I).$ This proves that $p\in P$.

C.2 Thin trees

D prelim

. For $e=uv\in E$, define vectors $x_{e}=L_{G}^{+/2}(e_{u}-e_{v})$ and $w_{e}=x_{e}/\left\lVert x_{e}\right\rVert$. Then $R_{e}=\left\lVert x_{e}\right\rVert^{2}$; let $p_{e}=R_{e}/(n-1)$. It is well-known that the vector of effective resistances describes the edge marginals of the uniform spanning tree, and hence that $\sum_{e}p_{e}=1$. Then, following the argument of Spielman and Srivastava ,

We view the vectors $\left\{\,w_{e}\,:\,e\in E\,\right\}$ as $(n-1)$-dimensional vectors in their linear span and apply Theorem 9.1. This gives a set $T\subseteq E$ of size $n-1$ such that $\left\{\,w_{e}\,:\,e\in T\,\right\}$ is linearly independent and

The first two conditions imply that the edges in $T$ form a spanning tree on the vertex set $V$. Then since $R_{e}=\left\lVert x_{e}\right\rVert^{2}$, we have

Since we assume that $\kappa\leq C_{e}=1/R_{e}$ for every edge $e$, we obtain

So $T$ is O\big{(}\frac{\log n}{\kappa\log\log n}\big{)}-spectrally-thin.

By the nearly equal resistances assumption, $R_{e}=O(\frac{n-1}{\lvert E\rvert})$ for every edge $e$. On the other hand, the connectivity $k$ is at most the average degree, which is $2\lvert E\rvert/n$. Thus $R_{e}=O(1/k)$ for every edge $e$. The result now follows from Theorem 9.8.

Assume $n$ is a multiple of $4$. We define a graph that is related to an example of Boyd and Pulleyblank [14, p. 180]. There are two disjoint cycles, each of length $n/2$. Let us number the vertices in the first cycle as $1,\ldots,n/2$ and the vertices in the second cycle as $n/2+1,\ldots,n$. Add a matching where the $i{{}^{\textrm{th}}}$ edge connects the $i{{}^{\textrm{th}}}$ vertex in the first cycle and the $i{{}^{\textrm{th}}}$ vertex in the second cycle. The edges in the cycles each have weight $w_{c}:=k/2$ and the edges in the matching each have weight $w_{m}:=2k/n$. Obviously this weighted graph has connectivity at least $k$.

Let $T$ be any subtree of $G$, without any weights on the edges of $T$.

Suppose that $T$ uses only a single matching edge. There exists a vector $z$ such that

Without loss of generality, $\left\{n/4,3n/4\right\}$ be the matching edge used by $T$. Let $\alpha=n^{-0.5}$ and $c=1-\alpha$. Define the vector $z$ where

Numerator: The numerator is $z^{\mathsf{T}}L_{T}z=\sum_{uv\in E}(z_{u}-z_{v})^{2}\geq(z_{n/4}-z_{3n/4})^{2}=1$.

Denominator: To evaluate $z^{\mathsf{T}}L_{G}z$, we separately consider the cycle edges and matching edges. The contribution from the matching edges is

Since $\alpha=n^{-0.5}$, we get $C_{m}=O(k/\sqrt{n})$ and $C_{c}=O(k/\sqrt{n})$, so $z^{\mathsf{T}}L_{G}z=O(k/\sqrt{n})$.

Suppose that $T$ uses $m>1$ matching edges. There exists a vector $z$ such that

Let the matching edges used by $T$ be $\left\{a_{1},b_{1}\right\},\left\{a_{2},b_{2}\right\},\ldots,\left\{a_{m},b_{m}\right\}$. Define the vector $z$ by

where $d_{1}$ denotes distance in the first cycle.

Numerator: As before, every matching edge used by $T$ contributes at least $1$, so $z^{\mathsf{T}}L_{T}z\geq m$.

Denominator: Obviously $z^{\mathsf{T}}L_{G}z$ is no more than $m$ times what it would be if $T$ used only a single matching edge. That is, $z^{\mathsf{T}}L_{G}z\leq O(mk/\sqrt{n})$.

D.1 Column-subset selection

Since $\sum_{i}p_{i}=\left\lfloor\operatorname{st.rank}(A)\right\rfloor$, we have $p\in P$.

Appendix E Proof of Theorem 7.9

The outline of this proof follows a proof of Lieb’s theorem presented by Epstein . Epstein’s proof proceeds via complex analytic techniques, and in particular makes use of some powerful results involving Herglotz functions (see, e.g., ). While an effort has been made to make the treatment here accessible, a modicum of complex analysis will be assumed; a standard reference is .

A key reason that Herglotz functions will be useful is the following classical theorem (see, e.g., [6, Eq. V.42] or [30, p. 542]).

Roughly speaking, this provides a description of a Herglotz function through its boundary (the real line); since the function may diverge as it approaches the real line, the generality of a measure (which may have atoms) is needed.

The relevance of this theorem to our purposes comes from the following:

Expressing $f$ in terms of the Herglotz-Nevanlinna-Riesz representation of $g$, we have that

We will apply Lemma E.3 with $f$ as in the statement of Theorem 7.9:

In order to extend our definition of $\log$ beyond symmetric matrices, we use (again following ) the Cauchy integral description

The function $f$ is well-defined and analytic on $D$.

For convenience, we withhold the proof until the end of this section.

To deduce that $f$ is concave by Lemma E.3, we must show that $g$ defined by $g(z)=zf(1/z)$ is Herglotz. We have

We now resume the argument for the case $n>1$. Define

Much of the argument revolves around noting that $\mathcal{I}_{++}$ is closed under various operations. For example, if $C,A\in\mathcal{I}_{++}$ then clearly $A+C\in\mathcal{I}_{++}$. The following is less straightforward:

Moreover, if $A\succ 0$, then the left inequality is strict, and if $B\succ 0$, the right inequality is strict.

We first observe that the conditions imply that $A+Bz$ has no nonpositive real eigenvalues, and hence that the logarithm is well defined. It suffices to show that $A+Bz$ is nonsingular, since we can apply the same argument to $A^{\prime}+Bz$, where $A^{\prime}=A+t$ for any $t\geq 0$.

If $B\succ 0$, then $B^{1/2}$ exists and is positive definite. Thus

But $Q$ is Hermitian (as can be seen since $B^{-1/2}$ and $A$ are Hermitian) and so it has real spectrum; thus since $\Im z>0$, is not in the spectrum of $Q+z$. Hence $Q+z$ and so also $A+Bz$ are invertible.

Suppose first that $B\succ 0$. Then $A+Bz\in\mathcal{I}_{++}$, and so by Lemma E.6 (ii) we immediately have that $\Im\log(A+Bz)\succ 0$. Now if $B\succeq 0$ but is not positive definite, then $B+\epsilon\succ 0$ for any $\epsilon>0$, and so $\Im\log(A+(B+\epsilon)z)\succ 0$. Since $\log(A+Bz)$ is well defined, we have by continuity that

This completes the proof of the left inequality.

For the right inequality, suppose first that $A\succ 0$. Since $\arg z=\Im\log z$, our goal is to show that

or equivalently (using that $A+Bz$ is nonsingular)

Since $\arg(-1/z)=\pi-\arg z$, we obtain that

Applying Lemma E.3, and observing the proof of Lemma E.5 below, Theorem 7.9 has been proved.

Now suppose $z\in(-\epsilon,\epsilon)$. Then

Appendix F Weaker Proof of Theorem 7.9

In this appendix we prove Theorem 7.9, under the additional hypothesis that $C_{i}$ & $K_{i}$ commute. This suffices to prove Lemma 7.6. The argument builds on Lieb’s original proof of Theorem 7.8.

First we need some preliminary definitions. For $x,y\geq 0$, define the logarithmic mean and binomial mean as follows:

(P1): If $X$ and $Y$ commute then $T_{X}(Y)=YX^{-1}$ and $R_{X}(Y)=Y^{2}X^{-2}$.

(P2): The inverse of $T_{X}$ is the operator $T_{X}^{-1}$ where $T_{X}^{-1}(Y)=\int_{0}^{1}X^{t}YX^{1-t}\,dt$.

(P3): In a basis in which $X$ is diagonal, we have \big{(}T_{X}^{-1}(Y)\big{)}_{i,j}=Y_{i,j}\cdot\operatorname{LM}(X_{i,i},X_{j,j}).

See Lieb p. 277, and Ohya and Petz Eq. (3.7) and p. 49.

See Lieb equations (3.6) and (3.9), and Ohya and Petz [36, p. 53].

The theorem is equivalent to 0\leq\frac{d^{2}f}{dz^{2}}\big{|}_{z=0} (assuming that this derivative exists). From Claim 18 we have

From (P1) and the assumption that $C_{i}$ and $K_{i}$ commute we have $R_{C_{i}}(K_{i})=T_{C_{i}}(K_{i})^{2}$. So the assertion of the theorem is equivalent to

by Theorem F.2. We may rewrite the right-hand side as

Thus, combining (14), (15) and (16), it suffices to prove

Since that inequality is invariant under choice of orthonormal basis, and since $\operatorname{tr}M^{1/2}XM^{1/2}Y\geq 0$, it suffices to prove

Denote the diagonal entries of $D$ by $d_{i}=D_{i,i}$. Then

by the arithmetic-mean geometric-mean (AM-GM) inequality. The right-hand side of (17) is

So, to prove (17), it suffices to prove that

We will prove the more general inequality

This implies (18) by letting $Z=X\circ Y$ (the Hadamard product of $X$ and $Y$), which is positive semidefinite by the Schur product theorem [6, p. 23]. Rearranging, (19) becomes

Since $|Z_{i,j}|+Z_{i,j}\geq 0$, the AM-GM inequality implies that the left-hand side is at least

Appendix G Connections to the Kadison-Singer Problen

The Kadison-Singer problem, which dates back to 1959, is an important, and until very recently unsolved, question in operator theory. The importance of this question has become increasingly apparent in recent years as it is now known to be equivalent, or closely related, to numerous conjectures in disparate areas of mathematics . In a very recent breakthrough, Marcus, Spielman and Srivastava positively resolved the Kadison-Singer problem. More precisely, they proved the following strong form of Weaver’s conjecture [55, Conjecture $\text{KS}_{2}$ and Theorem 2]:

It is well-known that, given a strong discrepancy result such as (21), an iterative argument yields a sparse object that gives a good approximation. See, e.g., Rudelson . For the sake of completeness, we include here a detailed argument that Theorem G.1 implies the existence of $O(1/\kappa)$-spectrally-thin trees.

First, the following corollary of Theorem G.1 will be convenient for induction purposes.

Let $\alpha,\beta,\delta,v_{1},\ldots,v_{m}$ be as in the statement of Corollary G.2. Note that $\delta\leq 1$, since $m\geq n$. Letting $M=\sum_{i}v_{i}v_{i}^{\mathsf{T}}$, we see that $\left\lVert M^{-1}\right\rVert\leq\alpha^{-1}$. Define $u_{i}=M^{-1/2}v_{i}$. Then

Applying Theorem G.1 of Marcus et al. , we deduce (21), and hence (since $\epsilon\leq 2$)

by the hypotheses $\alpha\in[1/2,1]$ and $\beta\in$.

Thus taking $S=S_{1}$, we see that (22) holds with $C=16$.

We may now prove Theorem 9.2 by an application of Corollary G.2. By an argument similar to the proof of Theorem 9.8, this implies the existence of $O(1/\kappa)$-spectrally-thin trees.

Without loss of generality, we may assume $p_{i}=1/m~{}\forall i$. To see this, suppose that $p_{1},\ldots,p_{m}$ are rational numbers of the form $q_{i}/M$ where $q_{1},\ldots,q_{m},M$ are nonnegative integers. Then we may replace each $w_{i}$ with $q_{i}$ copies of itself. The uniform distribution on the resulting vectors still has covariance matrix $I/n$. Proving Theorem 9.2 for the resulting vectors establishes the theorem for the original vectors under distribution $p$. If $p_{1},\ldots,p_{m}$ are irrationals, we may approximate them by rationals while introducing vanishing error.

Define $v_{i}=\sqrt{n/m}\cdot w_{i}$, so that $\left\lVert v_{i}\right\rVert^{2}=n/m=:\delta_{0}$ for all $i$. We will iteratively construct sets $S_{t}\subseteq[m]$, with $S_{0}=[m]$. Let $C$ be as in Corollary G.2. Define $\alpha_{0}=\beta_{0}=m$, and then inductively

Let $\epsilon\in(0,1]$ be a small constant to be chosen in a moment, and let

This choice of $T$ is motivated by the following:

For all $t\leq T$, $\beta_{t}\leq m(1+\epsilon)$ and $\alpha_{t}\geq m(1-\epsilon)$.

and so since $\beta_{t}\leq m(1+\epsilon)$, $\alpha_{t}\geq m(1-\epsilon)$.

Note that since $\sum_{j=0}^{T-1}(2^{j}n/m)^{c}=\Theta((2^{T}n/m)^{1/2})$, we have that

So we may choose $\epsilon\in(0,1/3]$ to be a constant sufficiently small so that

Our first goal will be to show inductively that for all $t\leq T$, there exists a set $S_{t}\subseteq[m]$ so that

Note that this is true for $t=0$ by assumption.

It will be convenient to define $\gamma_{t}=2^{t}|S_{t}|$. Suppose (25) holds for some particular $t<T$. Define

so that $\lVert v_{i}^{(t)}\rVert^{2}=\frac{n}{|S_{t}|}=:\delta_{t}$ for all $t$. Then just by scaling,

Taking a trace yields $n\alpha_{t}/\gamma_{t}\leq n\leq n\beta_{t}/\gamma_{t}$, i.e.,

Now apply Corollary G.2 with $S_{t}$ instead of $[m]$, $v_{i}^{(t)}$ instead of $v_{i}$, $\alpha_{t}/\gamma_{t}$ instead of $\alpha$, $\beta_{t}/\gamma_{t}$ instead of $\beta$, and $\delta_{t}$ instead of $\delta$. The hypotheses of Corollary G.2 are satisfied, so it follows that there is a set $S_{t+1}\subseteq S_{t}$ with

Rewriting in terms of the original $v_{i}$’s, we obtain

From Claim 20 and (25) for $t=T$, we deduce that

hence by (23) and since $\epsilon$ is a constant,