Cauchy-Schwarz
useful for derive upper bounds, e.g when analysing the error or convergence rate of an algorithm
for all vectors v and v of an inner product space, we have
∣⟨u,v⟩∣2≤⟨u,u⟩⟨˙v,v⟩
In context of Euclidean norm:
∣xTy∣≤∥x∥2∥y∥2
proof
using Pythagorean theorem
special case of v=0. Then ∥u∥∥v∥=0,
⇒ if u and v are linearly dependent., then q.e.d
Assume that v=0. Let z:=u−⟨v,v⟩⟨u,v⟩v
It follows from linearity of inner product that
⟨z,v⟩=⟨u−⟨v,v⟩⟨u,v⟩v,v⟩=⟨u,v⟩−⟨v,v⟩⟨u,v⟩⟨v,v⟩=0
Therefore z is orthogonal to v (or z is the projection onto the plane orthogonal to v). We can then apply Pythagorean theorem for the following:
u=⟨v,v⟩⟨u,v⟩v+z
which gives
∥u∥2=∣⟨v,v⟩⟨u,v⟩∣2∥v∥2+∥z∥2=(∥v∥2)2∣⟨u,v⟩∣2∥v∥2+∥z∥2=∥v∥2∣⟨u,v⟩∣2+∥z∥2≥∥v∥2∣⟨u,v⟩∣2
Follows ∥z∥2=0⟹z=0, which estabilishes linear dependences between u and v.
q.e.d