Optimization and Computational Linear Algebra for Data Science

Lecture 4: Norm and inner product

Léo Miolane · [Link]@[Link]

September 21, 2020

Warning: This material is not meant to be lecture notes. It only gathers the main concepts
and results from the lecture, without any additional explanation, motivation, examples, figures...

1 Norm
Definition 1.1 (Norm)
Let V be a vector space. A norm k · k on V is a function from V to R≥0 that verifies the
following points:

(i) Homogeneity: kαvk = |α| × kvk for all α ∈ R and v ∈ V .

(ii) Triangular inequality: ku + vk ≤ kuk + kvk for all u, v ∈ V .

(iii) Positive definiteness: if kvk = 0 for some v ∈ V , then v = 0.

Example 1.1. One can consider various norms over Rn :

qP
def
• The Euclidean norm kxk2 = i=1 xi .
n 2

def
• The `1 norm kxk1 =
Pn
i=1 |xi |.

def p 1/p .
• More generally, given p ≥ 1, the `p -norm kxkp =
Pn

i=1 |xi |

def
• The infinity-norm kxk∞ = max(|x1 |, . . . , |xn |).

2 Inner product
Definition 2.1 (Inner product)
Let V be a vector space. An inner product on V is a function h·, ·i from V × V to R that
verifies the following points:

(i) Symmetry: hu, vi = hv, ui for all u, v ∈ V .

(ii) Linearity: hu + v, wi = hu, wi + hv, wi and hαv, wi = αhv, wi for all u, v, w ∈ V and
α ∈ R.

(iii) Positive definiteness: hv, vi ≥ 0 with equality if and only if v = 0.

Example 2.1.

• For V = Rn , the Euclidean inner product hx, yi = = xT y is an inner product.

Pn
i=1 xi yi

1
 R1
• If V is the set of all continuous functions on [0, 1], then hf, gi = 0 f (t)g(t)dt is an inner
product.

• If V is the set of all random variables on a probability space Ω that have a finite variance,
then hX, Y i = E[XY ] is an inner product on V .
Proposition 2.1 (Norm induced by an inner product)
def
If h·, ·i is an inner product on V then kvk =
p
hv, vi is a norm on V . We say that the norm
k · k is induced by the inner product h·, ·i.

Remark 2.1. The Euclidean norm k · k2 on V = Rn is induced by the Euclidean inner product
x · y = ni=1 xi yi . Indeed, for x ∈ Rn ,
P

v
u n
√
kxk2 = t x2i = x · x.
uX

i=1

Exercise 2.1. Let h·, ·i be an inner product on Rn , and let k · k be the induced norm by h·, ·i.
(a) Show that for all x, y ∈ Rn we have

kx + yk2 + kx − yk2 = 2kxk2 + 2kyk2 .

(b) Deduce from the previous question that the `1 norm k · k1 and the infinity norm k · k∞ are
not induced by an inner product.

Theorem 2.1 (Cauchy-Schwarz inequality)

Let k · k be the norm induced by the inner product h·, ·i on the vector space V . Then for all
x, y ∈ V :
|hx, yi| ≤ kxk kyk. (1)
Moreover, there is equality in (1) if and only if x and y are linearly dependent, i.e. x = αy or
y = αx for some α ∈ R.

Proof. If x = 0 or y = 0 the result is obvious, we assume therefore to be in the case where x 6= 0

and y 6= 0. For t ∈ R we define the function f (t) = ktx − yk2 . Since the norm k · k is induced by
the inner product h·, ·i we have

f (t) = htx − y, tx − yi = t2 kxk2 − 2thx, yi + kyk2 .

f is therefore a quadratic function of t. Notice that f is non-negative because f (t) = ktx−yk2 ≥ 0.

This gives that its discriminant ∆ is non-positive:

∆ = (2hx, yi)2 − 4kxk2 kyk2 ≤ 0,

which proves (1). We have equality in (1) if and only if ∆ = 0 that is if and only if f admits a
zero α, which is equivalent to αx − y = 0, i.e. y = αx. 

3 Orthogonality
In this section we consider an inner product h·, ·i (that induces a norm k · k) on a vector space V .
For simplicity one may think of h·, ·i and k · k to be the usual Euclidean dot product and norm
on V = Rn .

2
Definition 3.1 (Orthogonality)

• We say that vectors x and y are orthogonal if hx, yi = 0. We write then x ⊥ y.

• We say that a vector x is orthogonal to a set of vectors A ⊂ V if x is orthogonal to all

the vectors in A, i.e. ∀y ∈ A, hx, yi = 0. We write then x ⊥ A.

• More generality we say that A ⊂ V and B ⊂ V are orthogonal if hx, yi = 0 for all x ∈ A
and all y ∈ B. As before, we write A ⊥ B.

Theorem 3.1 (Pythagorean theorem)

Let x, y ∈ V . Then
x ⊥ y ⇐⇒ kx + yk2 = kxk2 + kyk2 .

Definition 3.2 (Orthogonal and orthonormal families of vectors)

Let v1 , . . . , vk be vectors of V . We say that the family of vectors (v1 , . . . , vk ) is

• orthogonal if the vectors v1 , . . . , vn are pairwise orthogonal, i.e. hvi , vj i = 0 for all i 6= j.

• orthonormal if it is orthogonal and if all the vi have unit norm: kv1 k = · · · = kvk k = 1.

Orthonormal basis are particularly convenient for computing coordinates of vectors:

Proposition 3.1
Assume that dim(V ) = n and let (v1 , . . . , vn ) be an orthonormal basis of V . Then the
coordinates of a vector x ∈ V in the basis (v1 , . . . , vn ) are (hv1 , xi, . . . , hvn , xi):

x = hv1 , xiv1 + · · · + hvn , xivn .

Moreover, for all y ∈ V , we have hx, yi = hv1 , xihv1 , yi + · · · + hvn , xihvn , yi. Taking y = x
leads to q
kxk = hv1 , xi2 + · · · + hvn , xi2 .

4 Orthogonal projection and distance to a subspace

We assume in this section that V = Rn and that h·, ·i, k · k are respectively the Euclidean dot
product and Euclidean norm.
Definition 4.1 (Orthogonal projection and distance to a subspace)
Let S be a subspace of Rn . The orthogonal projection of a vector x onto S is defined as the
vector PS (x) is S that minimizes the distance to x:
def
PS (x) = arg min kx − yk.
y∈S

The distance of x to the subspace S is then defined as

def
d(x, S) = min kx − yk = kx − PS (x)k.
y∈S

3
Proposition 4.1
Let S be a subspace of Rn and let (v1 , . . . , vk ) be an orthonormal basis of S. Then for all
x ∈ Rn ,
PS (x) = hv1 , xiv1 + · · · + hvk , xivk .
In other words, if we let  
| | |
V =  v1 v2 · · · vk  ∈ Rn×k ,
 
| | |
then PS is a linear transformation whose matrix is V V T :

∀x ∈ Rn , PS (x) = V V T x.

Proof. Let us add vectors vk+1 , . . . , vn to the basis (v1 , . . . , vk ) to obtain an orthonormal basis
of Rn . (This is made possible by the Gram-Schmidt orthonormalization principle that we will
see in the next lecture.) Let α1 = hx, v1 i, . . . , αn = hx, vn i be the coordinates of x in the
basis (v1 , . . . , vn ). Let y ∈ S, and let β1 , . . . , βk be its coordinates in the basis (v1 , . . . , vk ). By
Proposition 3.1:
k n
kx − yk2 = (αi − βi )2 +
X X
αi2 .
i=1 i=k+1

Minimizing this quantity over y ∈ S is equivalent to minimizing it over the coordinates β1 , . . . , βk

of y. The minimum is uniquely achieved for βi = αi for all i, hence
def
PS (x) = arg min kx − yk = α1 v1 + · · · + αk vk = hv1 , xiv1 + · · · + hvk , xivk .
y∈S

The second part of the proposition is a rewritting of this last equation, obtained by noticing that

− v1 − hv1 , xi
   
 ..   .. 
V x =  . x =  . .
T

− vk − hvk , xi

Corollary 4.1
For all x ∈ Rn ,

• x − PS (x) is orthogonal to S.

• kPS (x)k ≤ kxk.

Definition 4.2 (Orthogonal complement)

Let S be a subspace of Rn . The orthogonal complement of S is defined by
def
S ⊥ = x ∈ Rn x ⊥ S = x ∈ Rn ∀y ∈ S, hx, yi = 0 .
 

Proposition 4.2
Let S be a subspace of Rn . Then S ⊥ is also a subspace of Rn with dimension

dim(S ⊥ ) = n − dim(S).

4
5