Van der Corput inequality

In mathematics, the van der Corput inequality is a corollary of the Cauchy–Schwarz inequality that is useful in the study of correlations among vectors, and hence random variables. It is also useful in the study of equidistributed sequences, for example in the Weyl equidistribution estimate. Loosely stated, the van der Corput inequality asserts that if a unit vector $v$ in an inner product space $V$ is strongly correlated with many unit vectors $u_{1},\dots ,u_{n}\in V$ , then many of the pairs $u_{i},u_{j}$ must be strongly correlated with each other. Here, the notion of correlation is made precise by the inner product of the space $V$ : when the absolute value of $\langle u,v\rangle$ is close to $1$ , then $u$ and $v$ are considered to be strongly correlated. (More generally, if the vectors involved are not unit vectors, then strong correlation means that $|\langle u,v\rangle |\approx \|u\|\|v\|$ .)

Statement of the inequality

Let $V$ be a real or complex inner product space with inner product $\langle \cdot ,\cdot \rangle$ and induced norm $\|\cdot \|$ . Suppose that $v,u_{1},\dots ,u_{n}\in V$ and that $\|v\|=1$ . Then

\displaystyle \left(\sum _{i=1}^{n}|\langle v,u_{i}\rangle |\right)^{2}\leq \sum _{i,j=1}^{n}|\langle u_{i},u_{j}\rangle |.

In terms of the correlation heuristic mentioned above, if $v$ is strongly correlated with many unit vectors $u_{1},\dots ,u_{n}\in V$ , then the left-hand side of the inequality will be large, which then forces a significant proportion of the vectors $u_{i}$ to be strongly correlated with one another.

Proof of the inequality

\left|\sum _{i=1}^{n}\langle v,u_{i}\rangle \right|^{2}

=\left|\left\langle v,\sum _{i=1}^{n}u_{i}\right\rangle \right|^{2}

since the inner product is bilinear

\leq \|v\|^{2}\left\|\sum _{i=1}^{n}u_{i}\right\|^{2}

by the Cauchy–Schwarz inequality

=\|v\|^{2}\left\langle \sum _{i=1}^{n}u_{i},\sum _{j=1}^{n}u_{j}\right\rangle

by the definition of the induced norm

=1\cdot \sum _{i,j=1}^{n}\langle u_{i},u_{j}\rangle

since

v

is a unit vector, and the inner product is bilinear

=\sum _{i,j=1}^{n}|\langle u_{i},u_{j}\rangle |.

External links

A blog post by Terence Tao on correlation transitivity, including the van der Corput inequality

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.