In this previous blog post I noticed the following simple application of Cauchy Black:

Lemma 1 (Van der Corput inequality) To 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 side can be written as {|   langle v,  sum_ {i = 1} ^ n  epsilon_i u_i  rangle_H |  ^ 2} for some units complex numbers { epsilon_i}. We got from Cauchy-Schwarz

 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

Hence, the correlation becomes transitive in the statistical sense (although it is not transitive in the absolute sense):

Corollary 2 (statistical transitivity of the correlation) To let {v, u_1,  dots, u_n} be unit vectors in a Hilbert space {H} so that {|   langle v, u_i  rangle_H |   geq  delta} for all {i = 1,  dots, n} and some < delta leq 1}" class="latex" />. Then we have {|   langle u_i, u_j  rangle_H |   geq  delta ^ 2/2} for at least { delta ^ 2 n ^ 2/2} of couples {(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 < delta ^ 2/2}" class="latex" /> is at most { delta ^ 2 n ^ 2/2}and all remaining summands are at most {1}to give the claim. Box

One disadvantage of this inference is that it tells us nothing Which Couples {u_i, u_j} are related to each other. Especially 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} The correlate may not have any intersection with the pairs in which {w_i, w_j} correlate (except of course on the diagonal {i = j} where they need to correlate).

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

Corollary 3 (Simultaneous statistical transitivity of the correlation) To let {v, u ^ k_i} be unit vectors in a Hilbert space for {i = 1,  dots, n} and {k = 1,  dots, K} so that {|   langle v, u ^ k_i  rangle_H |   geq  delta_k} for all {i = 1,  dots, n}, {k = 1,  dots, K} and some < delta_k leq 1}" class="latex" />. Then at least there is {( delta_1  dots  delta_K) ^ 2 n ^ 2/2} Couples {(i, j)  in  {1,  dots, n } ^ 2} so that { prod_ {k = 1} ^ K |   langle u ^ k_i, u ^ k_j  rangle_H |   geq ( delta_1  dots  delta_K) ^ 2/2}. In particular (from 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 {v ^ { otimes K}} and {u ^ 1_i  otimes  dots  otimes u ^ K_i}, {i = 1,  dots, n} in the tensor force Hilbert space {H ^ { otimes K}}. Box

It is surprisingly difficult to get even a qualitative version of the above conclusion (namely, if {v} correlates with all {u ^ k_i}Then there are a lot of couples {(i, j)} for which {u ^ k_i} correlates with {u ^ k_j} for all {k} simultaneously) without any version of the tensor power trick. For example, even the powerful Szemerédi regularity lemma, if it is 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 set as a replacement (or really a disguised version) of the tensor power trick. To simplify the notation, let’s just work with real Hilbert spaces to illustrate the argument. We start with 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 assertion that {FROM} is positive semi-definite. We conclude from this with the Schur product set

 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 thus for a suitable selection of characters { 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 forces to reinforce correlations was also mentioned in this previous blog post which features a cheap version of the Kabatjanskii-Levenstein bond, but this does not seem to be directly related to this current application.

LEAVE A REPLY

Please enter your comment!
Please enter your name here