The mother of all inequalities

Theoretical computer scientists love inequalities. After all, a great many of our papers involve showing either an upper bound or a lower bound on some quantity. So I thought I’d share some cool stuff I’ve learned this Friday in our reading group‘s talk by Zeev Dvir. This is based on my partial and vague recollection of Zeev’s talk, so please see the references in his paper with Hu (and a previous paper of Hardt and Moitra) for the complete (and correct) information. See also this blog post of James Lee.

The Brascamp–Lieb inequality is actually a shorthand for a broad family of inequalities generalizing the Holder Inequality, Young’s Inequality, the Loomis–Whitney inequality and many more. As Zeev put it, it probably generalizes any inequality you (or at least I) know about. Barthe gave an (alternative) proof of these inequalities, in the course of which he produced a magical lemma that turns out to be useful in many varying theoretical CS scenarios, from communication complexity to bounds for locally decodable codes, as well as for obtaining generalizations of the Sylvester-Gallai theorem in geometry.

One way to think about the Brascamp-Lieb inequality (as shown by Carlen and Cordero-Erausquin) is as generalizing the sub-additivity of entropy. We all know that given a random variable X over ℝ^d,  H(X) ≤ H(X₁) + ⋯ + H(X_d)

Where X_i is the i^th coordinate of X. Now suppose that we let denote the j^th coordinate of X in some different basis. Then by the same reasoning we know that  

The Brascamp-Lieb inequality can be thought of as asking for the most general form of such inequalities. Specifically, given an arbitrary linear map F : ℝ^d → ℝⁿ, we can ask for what vector of numbers γ = (γ₁, …, γ_n) it holds that

H(X) ≤ γ₁H(F(X)₁) + ⋯γ_nH(F(X)_n) + C

for all random variables X where C is a constant independent of X (though can depend on F, γ).

The answer of Brascamp-Lieb is that this is the case if (and essentially only if) the vector γ can be written as a convex combination of vectors of the form 1_S where S ⊆ [n] is a d-sized set such that the functions {F_i}_i ∈ S are linearly independent. You can see that the two cases above are a special case of this condition (where it also turns out that C = 0). (There is an even more general form where each can map into a subspace of dimension higher than one; see the papers for more.)

The heart of the proof (if I remember Zeev’s explanations correctly) is to show that the worst-case for such an inequality is always when the variables F(X)₁, …, F(X)_n are a Gaussian process, that is X is some kind of a multivariate Gaussian distribution. Once this is show, one can phrase computing the supremum of C as a convex optimization problem over the parameters of this Gaussian distribution and then prove some bound on it.

For proving Brascamp-Lieb it is sufficient to simply bound C, but it turns out that the parameters that achieve the optimum C as a function of F and γ, have a very interesting property. Since the derivative of the objective function at this point must be zero, some algebraic manipulations show that one can obtain from them an invertible linear transofmation G such that
∑γ_iG(F_i)G(F_i)^⊤/∥G(F_i)∥² = I (*)
where I is the identity map on ℝ^d and F_i is the d-dimensional vector corresponding to the i^th coordinate of F. The condition (*) looks somewhat mysterious, but one way to think about it is that it means that after a change of basis and rescaling so that each F_i is a unit vector, we can make the vectors F₁, …, F_n be “evenly spread out” in ℝ^d in the sense that no direction is favored over any other one.

This turns out to be useful in some surprising contexts. For example, the notion of sign rank of a matrix is very important in several communication complexity applications. The sign rank of a matrix A ∈ { ± 1}ⁿ² is the minimum rank of a matrix B such that sign(B_i, j) = A_i, j for every i, j. Clearly the sign rank might be much smaller than the rank, and proving that a matrix has large sign rank is a non-trivial matter. Nevertheless Forster managed to prove the following theorem:

Forster’s Theorem: The sign rank of A is at least n/∥A∥ where ∥A∥ is the spectral norm of A.

Which in particular gave a highly non trivial lower bound of on the sign rank of the Hadamard matrix.

The proof is easy given the above corollary (*). (Forster wasn’t aware of Barthe’s work, and as far as I know, the connection between the two works was first discovered by Moritz Hardt.) Suppose that there exists B of rank d such that sign(B_i, j) = A_i, j for every i, j. Then we can write B_i, j = 〈u_i, v_j〉for some vectors u₁, …, u_n, v₁, …, v_n ∈ ℝ^d. By making a tiny perturbation, we can assume that for every subset S ⊆ [n] the vectors {u_i}_i ∈ S are linearly independent and hence in particular the vector γ = (d/n, …, d/n) can be expressed as a convex combination of the vectors of the form 1_S, and hence in particular we get that after applying some change of basis and rescaling (which will not affect the sign of 〈u_i, v_j〉 ) we can assume without loss of generality that every u_i,v_j is a unit vector and moreover .

Now note that under our assumption B_i, jA_i, j = |B_i, j| and hence

The last inequality follows from the fact that for every two matrices A, B, A ⋅ B ≤ ∑|λ_iσ_i|≤ max{λ_i}∑|σ_i|, where the λ_i‘s and σ_i‘s are the singular values of A and B respectively. We then use the fact that ∥A∥ = max{λ_i} and in B at most d of those are nonzero and hence by Cauchy-Schwarz . However by the condition (*) Tr(BB^⊤) = ∑_i∑_j〈u_i, v_j〉〉² = n²/d, and on the other hand (since every entry of B is a dot product of unit vectors and hence smaller than one) ∑|B_i, j| = ∑_i, j|〈u_i, v_j〉| ≥ ∑_i, j|〈u_i, v_j〉|² = n²/d. So we get

or n/∥A∥ ≤ d as we wanted.