profile pic
⌘ '
raccourcis clavier

useful for derive upper bounds, e.g when analysing the error or convergence rate of an algorithm

format

for all vectors vv and vv of an inner product space, we have

u,v2u,u˙v,v\mid \langle u, v \rangle \mid ^2 \le \langle u, u \rangle \dot \langle v, v \rangle

In context of Euclidean norm:

xTyx2y2\mid x^T y \mid \le \|x\|_2 \|y\|_2

proof

using Pythagorean theorem

special case of v=0v=0. Then uv=0\|u\|\|v\| =0,

if uu and vv are linearly dependent., then q.e.d

Assume that v0v \neq 0. Let zuu,vv,vvz \coloneqq u - \frac{\langle u, v \rangle}{\langle v, v \rangle} v

It follows from linearity of inner product that

z,v=uu,vv,vv,v=u,vu,vv,vv,v=0\langle z,v \rangle = \langle u - \frac{\langle u,v \rangle}{\langle v, v \rangle} v,v \rangle = \langle u,v \rangle - \frac{\langle u,v \rangle}{\langle v,v \rangle}\langle v,v \rangle = 0

Therefore zz is orthogonal to vv (or zz is the projection onto the plane orthogonal to vv). We can then apply Pythagorean theorem for the following:

u=u,vv,vv+zu = \frac{\langle u,v \rangle}{\langle v,v \rangle} v + z

which gives

u2=u,vv,v2v2+z2=u,v2(v2)2v2+z2=u,v2v2+z2u,v2v2\begin{aligned} \|u\|^{2} &= \mid \frac{\langle u,v \rangle}{\langle v,v \rangle} \mid^{2} \|v\|^{2} + \|z\|^2 \\ &=\frac{\mid \langle u,v \rangle \mid^{2}}{(\|v\|^2)^{2}} \|v\|^{2} + \|z\|^2 \\ &= \frac{\mid \langle u, v \rangle\mid^2}{\|v\|^{2} } + \|z\|^2 \ge \frac{\mid \langle u,v \rangle \mid^2}{\|v\|^{2} }\\ \end{aligned}

Follows z2=0    z=0\|z\|^{2}=0 \implies z=0, which estabilishes linear dependences between uu and vv.

q.e.d