Boosting the van der Corput inequality using the tensor power trick

What's new 2021-02-27

In this previous blog post I noted the following easy application of Cauchy-Schwarz:

Lemma 1 (Van der Corput inequality) Let ${v,u_1,\dots,u_n}$ be unit vectors in a Hilbert space ${H}$ . Then
$\displaystyle (\sum_{i=1}^n |\langle v, u_i \rangle_H|)^2 \leq \sum_{1 \leq i,j \leq n} |\langle u_i, u_j \rangle_H|.$

Proof: The left-hand side may be written as ${\langle v, \sum_{i=1}^n \epsilon_i u_i \rangle_H}$ for some unit complex numbers ${\epsilon_i}$ . By Cauchy-Schwarz we have

$\displaystyle |\langle v, \sum_{i=1}^n \epsilon_i u_i \rangle_H|^2 \leq \langle \sum_{i=1}^n \epsilon_i u_i, \sum_{j=1}^n \epsilon_j u_j \rangle_H$

and the claim now follows from the triangle inequality. $\Box$

As a corollary, correlation becomes transitive in a statistical sense (even though it is not transitive in an absolute sense):

Corollary 2 (Statistical transitivity of correlation) Let ${v,u_1,\dots,u_n}$ be unit vectors in a Hilbert space ${H}$ such that ${|\langle v,u_i \rangle_H| \geq \delta}$ for all ${i=1,\dots,n}$ and some ${0 < \delta \leq 1}$ . Then we have ${|\langle u_i, u_j \rangle_H| \geq \delta^2/2}$ for at least ${\delta^2 n^2/2}$ of the pairs ${(i,j) \in \{1,\dots,n\}^2}$ .

Proof: From the lemma, we have

$\displaystyle \sum_{1 \leq i,j \leq n} |\langle u_i, u_j \rangle_H| \geq \delta^2 n^2.$

The contribution of those ${i,j}$ with ${|\langle u_i, u_j \rangle_H| < \delta^2/2}$ is at most ${\delta^2 n^2/2}$ , and all the remaining summands are at most ${1}$ , giving the claim. $\Box$

One drawback with this corollary is that it does not tell us which pairs ${u_i,u_j}$ correlate. In particular, if the vector ${v}$ also correlates with a separate collection ${w_1,\dots,w_n}$ of unit vectors, the pairs ${(i,j)}$ for which ${u_i,u_j}$ correlate may have no intersection whatsoever with the pairs in which ${w_i,w_j}$ correlate (except of course on the diagonal ${i=j}$ where they must correlate).

While working on an ongoing research project, I recently found that there is a very simple way to get around the latter problem by exploiting the tensor power trick:

Corollary 3 (Simultaneous statistical transitivity of correlation) Let ${v, u^k_i}$ be unit vectors in a Hilbert space for ${i=1,\dots,n}$ and ${k=1,\dots,K}$ such that ${|\langle v, u^k_i \rangle_H| \geq \delta_k}$ for all ${i=1,\dots,n}$ , ${k=1,\dots,K}$ and some ${0 < \delta_K \leq 1}$ . Then there are at least ${(\delta_1 \dots \delta_K)^2 n^2/2}$ pairs ${(i,j) \in \{1,\dots,n\}^2}$ such that ${\prod_{k=1}^K |\langle u^k_i, u^k_j \rangle_H| \geq (\delta_1 \dots \delta_K)^2/2}$ . In particular (by Cauchy-Schwarz) we have ${|\langle u^k_i, u^k_j \rangle_H| \geq (\delta_1 \dots \delta_K)^2/2}$ for all ${k}$ .

Proof: Apply Corollary 2 to the unit vectors ${u^{\otimes K}}$ and ${u^1_i \otimes \dots \otimes u^K_i}$ , ${i=1,\dots,n}$ in the tensor power Hilbert space ${H^{\otimes K}}$ . $\Box$

It is surprisingly difficult to obtain even a qualitative version of the above conclusion (namely, if ${v}$ correlates with all of the ${u^k_i}$ , then there are many pairs ${(i,j)}$ for which ${u^k_i}$ correlates with ${u^k_j}$ for all ${k}$ simultaneously) without some version of the tensor power trick. For instance, even the powerful Szemerédi regularity lemma, when applied to the set of pairs ${i,j}$ for which one has correlation of ${u^k_i}$ , ${u^k_j}$ for a single ${i,j}$ , does not seem to be sufficient. However, there is a reformulation of the argument using the Schur product theorem as a substitute for (or really, a disguised version of) the tensor power trick. For simplicity of notation let us just work with real Hilbert spaces to illustrate the argument. We start with the identity

$\displaystyle \langle u^k_i, u^k_j \rangle_H = \langle v, u^k_i \rangle_H \langle v, u^k_j \rangle_H + \langle \pi(u^k_i), \pi(u^k_j) \rangle_H$

where ${\pi}$ is the orthogonal projection to the complement of ${v}$ . This implies a Gram matrix inequality

$\displaystyle (\langle u^k_i, u^k_j \rangle_H)_{1 \leq i,j \leq n} \succ (\langle v, u^k_i \rangle_H \langle v, u^k_j \rangle_H)_{1 \leq i,j \leq n} \succ 0$

for each ${k}$ where ${A \succ B}$ denotes the claim that ${A-B}$ is positive semi-definite. By the Schur product theorem, we conclude that

$\displaystyle (\prod_{k=1}^K \langle u^k_i, u^k_j \rangle_H)_{1 \leq i,j \leq n} \succ (\prod_{k=1}^K \langle v, u^k_i \rangle_H \langle v, u^k_j \rangle_H)_{1 \leq i,j \leq n}$

and hence for a suitable choice of signs ${\epsilon_1,\dots,\epsilon_n}$ ,

$\displaystyle \sum_{1 \leq i, j \leq n} \epsilon_i \epsilon_j \prod_{k=1}^K \langle u^k_i, u^k_j \rangle_H \geq \delta_1^2 \dots \delta_K^2 n^2.$

One now argues as in the proof of Corollary 2.

A separate application of tensor powers to amplify correlations was also noted in this previous blog post giving a cheap version of the Kabatjanskii-Levenstein bound, but this seems to not be directly related to this current application.