The TQC Lemma

Sometime in late 2012 or early 2013, Joel Tropp, Martin Lotz, Dennis Amelunxen, and I were all discussing some integral-geometric problem or another, and the topic of projections of convex cones came up. One of us made the observation that taking the linear image of a subspace in general position yields one of two results:

1. Either the subspace is “small enough” for the linear map, and so remains a linear space of the same dimension; or
2. The subspace is “too large” for the linear map, and so it fills the entire space.

This elementary observation, combined with the spherical Hadwiger formula, yields a startling result: many geometric quantities related to convex cones are, on average, precisely preserved under linear maps. Based on the notation we had on the chalkboard at the time, we called this result the TQC lemma.

A slightly different proof of this theorem appears in print in a 2019 work by Amelunxen, Lotz, & Walvin¹, graciously credited to Joel and myself. A weaker form, valid only for Gaussian transformations of cones, appears in 2023 work of Götze, Kabluchko, & Zaporozhets², which contains other fascinating results relating intrinsic volumes to random walks. The more recent manuscript of Schneider³ provides a self-contained proof following Götze, Kabluchko, & Zaporozhets.

The latter two references convinced me that the lemma was interesting enough to write a blog post about the result; I find it fascinating that the result holds for such a broad class of averaging operators, and is fully independent of the condition number of the linear map. The proof below offers a third unique proof of this surprising result, and I hope it offers more intuition about why the result is true.

The TQC lemma

Let’s dive right in to the statement.

Lemma (TQC): Let $T: \mathbb{R}^d\to \mathbb{R}^d $ be a rank-$n$ linear map, and let $Q \in \mathcal{O}_d$ be a Haar-distributed orthogonal matrix. Then for any convex cone $C \subset \mathbb{R}^d$, we have

$$ \mathbb{E}[v_i(TQC)] = v_i(C) \text{ for } 0\le i < n $$

and

$$ \mathbb{E}[v_n(TQC)] = \sum_{j=n}^d v_j(C) $$

where $v_k$ is the $k$th conic intrinsic volume.

This isn’t a journal so I’ll offer some opinions about how crazy this appears. First, consider the $n=d$ case. This says that, when averaging over rotated cones, any invertible matrix leaves the intrinsic volumes of every cone in place, at least on average. In particular, the result holds no matter the condition number of the matrix; any dramatic stretching or compressing that the cones might undergo in one configuration is balanced perfectly by equally dramatic compression or stretching in another configuration, leading to (again, on average) no change in any intrinsic volume.

When the matrix $T$ is rank deficient ($n< d$), the result is almost the same, except that all of the “mass” of the intrinsic volumes for $v_j(C)$ for $j\ge n$ get swept into a single intrinsic volume. Again, condition numbers are irrelevant. The averaging over all rotations does remarkable work.

Proof outline

The basic approach is straightforward: show the theorem is true when $C$ is a linear subspace, then apply the spherical analog of Hadwiger’s theorem to extend the result to all convex cones.

The details, of course, require justification. The most finicky technical piece was something that seemed obvious to me more than a decade ago, but with the years that have passed, I found that it was worthwhile to justify it separately. We’ll start with that preliminary lemma.

Preliminaries

Definition (Valuation). We call a functional $\phi\colon \mathcal{C}\to \mathbb{R}$ on the space $\mathcal{C}$ of convex cones a valuation if, for each $C_1, C_2 \in \mathcal{C}$ with $C_1 \cup C_2 \in \mathcal{C}$,

$$ \phi(C_1 \cup C_2) + \phi(C_1 \cap C_2) = \phi(C_1) + \phi(C_2). $$

We require the following lemma.

Lemma 1. Let $A\colon \mathbb{R}^d \to \mathbb{R}^d$ be a linear map, and let $\phi(C)$ be a continuous valuation on convex cones. Then the functional $\psi(C) := \phi(AC)$ is also a continuous valuation on convex cones.

We prove this lemma below.

Proof of the TQC lemma

We begin by restricting our attention to a linear subspace $L\subset \mathbb{R}^d$ of dimension $m$. The image $TQL$ is also almost surely a subspace of dimension $\mathrm{min}(m, n)$. Since $v_i(L) = \delta_{i,m}$, we have

$$ \mathbb{E}[v_i(TQL)] = \delta_{i, \mathrm{min}(m,n)}, $$

which agrees with our statement.

To extend the result to all convex cones via the spherical Hadwiger theorem, we need to show that the map $\phi(C) := \mathbb{E}[v_i(TQC)]$ is a continuous, unitarily-invariant valuation on the space of convex cones. Indeed, for each fixed $Q$, $\psi(C) := v_i(TQC)$ is a continuous valuation by Lemma 1. The linearity of expectation then promotes the valuation property from $\psi$ to $\phi$. Continuity follows by the dominated convergence theorem since $\abs{v_i(C)} \le 1$ for all $C\in \mathcal{C}$. Unitary invariance follows since $\phi(UC) = \mathbb{E}[v_i(TQUC)]$ and the product $QU$ has the same distribution as $Q$.

The result now follows from the Spherical Hadwiger theorem⁴.

Proof of Lemma 1

Let $C_1, \, C_2 \in \mathcal{C}$ with $C_1\cup C_2 \in \mathcal{C}$. Then a straightforward computation shows

$$ A(C_1 \cup C_2) = AC_1 \cup AC_2. \tag{1} $$

Indeed, $y \in A(C_1 \cup C_2)$ if and only if there exists an $x \in C_1 \cup C_2$ such that $Ax = y$. This in turn occurs if and only if $y \in A C_1 \cup A C_2$, which shows the equality.

We also claim that

$$ A(C_1 \cap C_2) = A C_1 \cap A C_2.\tag{2} $$

The $\subseteq$ part of the claim is easy: $y \in A( C_1 \cap C_2)$ implies that there exists a $x \in C_1 \cap C_2$ such that $Ax = y$, and thus $y \in AC_1 \cap AC_2$.

Demonstrating the $\supseteq$ direction requires us to invoke the fact that $C_1 \cup C_2$ is convex. Indeed, suppose $y \in AC_1 \cap AC_2$. Then there exists an $x_1 \in C_1$ and $x_2 \in C_2$ such that $y = Ax_1 = Ax_2$. Since $C_1 \cup C_2$ is convex, the entire segment between $x_1$ and $x_2$ lies in $C_1\cup C_2$. Since this line begins in $C_1$ and ends in $C_2$, there is a point along the segment in $C_1\cap C_2$. That is, there exists a $\lambda \in [0,1]$ such that $z := \lambda x_1 + (1-\lambda)x_2 \in C_1 \cap C_2$. But we have $Az = y$ by definition of $x_1$ and $x_2$, and the equality (2) follows.

Combining (1) and (2) demonstrates that $\psi(C)$ is a valuation. Continuity follows from the continuity of linear maps and compactness of the cones when viewed topologically as projective subsets of the sphere.