Orthogonal Projections and the Orthogonality Principle

Module by: Richard Baraniuk

Note: Your browser may not currently support MathML. Chrome will attempt to display MathML, but it should not be considered correct. Safari will attempt to display MathML, but it should not be considered correct. Please install the required MathPlayer plugin to view MathML correctly.Firefox requires additional mathematics fonts to display MathML correctly.Firefox requires additional mathematics fonts to display MathML correctly. See our browser support page for additional details. You can always view the correct math in the PDF version.

(Show MathML examples)

If the two examples below are mathematically the same, your browser is correctly displaying MathML, and you can dismiss this message.

Example 1:	$\frac{\sqrt{\frac{1}{2}}}{\sqrt{{f(x+y)}^2}}\frac{\sqrt{1}}{2}\langle ℝ\rangle$	Example 2:		(Hide examples)

A key problem in DSP:

Given a signal y y find the signal x x from a subspace SS that is the closest to y y.

Example 1

y y is a noisy signal and all x∈S x S are smooth.

Figure 1

Finding an x x close to y y will approximate it by a noise-free version.

Geometry of the situation via linear algebra. x∈S⇒x=∑k=0M−1 α k bk x S x k 0 M 1 α k b k where bk b k are a basis for the subspace S S (We assume it is an ONB).

Figure 2: S S is an M-dim hyperplane thru the origin of ℝN N

The goal is to find x∈S x S close to y y, which is equivalent to finding αk α k .

We can also measure how close x x is to y y by l 2 l 2 norm error in ℝN N : ∥y−x∥22=∑n=0N−1yn−xn2 2 y x 2 n 0 N 1 y n x n 2 Define e=y−x e y x as the error vector and minimize l 2 l 2 strength of e e.

Geometry

Figure 3

Exercise 1

How close to choose - to minimize ∥x∥2 2 x ?

Solution

Choose x x so that error e e is ⊥ to x x and ⊥ to the entire subspace S S.

Figure 4

[ Show Solution ] [ Hide Solution ]

Orthogonality Principle

∥e∥2 2 e is minimum when <e,x>=0 e x 0 Also have ∀s,s∈S:<e,s>=0 s s S e s 0

Note:

Linear algebra lets us convert a distance problem (minimize l 2 l 2 distance between 2 vectors) into an angle problem (minimize the inner product between error and subspace).

We perform an orthogonal projection of y y onto S S to obtain x x closest to y y in S S.

Now apply the OP to find the optimal approximant x∈S x S to y y.

Recall: y∈ℂn y n x∈S⊆ℂN x S N x=∑k=0M−1 α k bk x k 0 M 1 α k b k where bk b k is an ONB for S S.

Purpose

The goal is that given y y, we must find α k α k 's.

Solution

Apply OP: Define e=y−x=y−∑k= α k b k e y x y k α k b k Then: 0=<e,x>=<y−∑k'= α k' bk',∑k'= α k bk> 0 e x y k' α k' b k' k' α k b k by linearity of OP,

0=<y,∑k'= α k bk>−<∑k'= α k' bk',∑k'= α k bk>=∑k'= α k ¯<y,bk>−∑k'= α k ¯<∑k'=αk'bk',bk>=∑k'= α k ¯<y,bk>−<∑k'= α k' bk',bk>=∑k'= α k ¯<y,bk>−∑k= α k' <bk',bk>=∑k'= α k ¯<y,bk>− α k 0 y k' α k b k k' α k' b k' k' α k b k k' α k y b k k' α k k' α k' b k' b k k' α k y b k k' α k' b k' b k k' α k y b k k α k' b k' b k k' α k y b k α k (1)

There are 2 ways to set to zero:

1. All α k =0 α k 0 .
2. <y,bk>− α k =0 y b k α k 0 for all kk chosen.

The solution to (2) is simple: <y,bk>− α k =0 y b k α k 0 or α k =<y,bk> α k y b k .

Summary

The optimal l 2 l 2 approximation x=∑k= α k bk x k α k b k to y y has α k =<y,bk> α k y b k when bk b k are an ONB for the subspace.

Projections

Figure 5

In Figure 5, e=y−x e y x , <e,x>=0 e x 0 , <e,S>=0 e S 0 x=∑k=01 α k bk x k 0 1 α k b k where bk b k is an ONB for SS α k =<y,bk> α k y b k ∥e∥2 2 e is minimized.

Example 2

ℝ2 2 . Find the closest x x to y∈ℝ2 y 2 where x x lies on a 45° angled line.

Figure 6

1. Find an ONB for SS, S=∀a,a∈ℝ:x=aa S a a x a a . ONB: b 0 =112 b 0 1 1 2 .
2. Optimal x=∑k=00 α k bk= α 0 b0 x k 0 0 α k b k α 0 b 0 α 0 =<y,b0> α 0 y b 0

For example,

Figure 7

in Figure 7, y=37 y 3 7 α 0 =121137=102 α 0 1 2 1 1 3 7 10 2 x=102112=55 x 10 2 1 1 2 5 5

Example 3

Given an ecg signal, y∈ℂN y N that is a smooth signal contaminated by noise

Figure 8

we would like to make an estimate y ̂ y ̂ that is smooth.

• Step1: Signal model: y=x+n y x n x∈S x S , subspace of smooth functions. Find an appropriate subspace. For example, x∈S x S spanned by the 1st M≪N DCT basis vectors (lowest frequencies). x=∑k=0M−1 α k bk x k 0 M 1 α k b k

  Figure 9: bk b k in SS

  Figure 10: bk b k not in SS

  Noise model: Assume for example, that n n is zero-mean Gaussian noise (i.i.d.).

  Figure 11: Note that there is more resemblence with a vector not in SS that to one that is.

• Step2: ⊥ project y y onto SS to get estimate y ̂ y ̂ (In statistical DSP, this is called the inear minimum mean squared error estimate - LMMSE est.). y ̂ =∑k=0N−1 β k bk y ̂ k 0 N 1 β k b k β k =<y,bk> β k y b k

  Figure 12: y=x+n y x n

Exercise 2

2.a)

Why is y ̂ ≠x y ̂ x ?

2.b)

Is y ̂ y ̂ closer to xx than yy is?

2.c)

Using the DCT basis, could you solve this problem in matlab?

2.d)

How do you choose the subspace and the ONB?

Comments, questions, feedback, criticisms?

Send feedback

• E-mail the author of the module, Orthogonal Projections and the Orthogonality Principle

Footer

This work is licensed by Richard Baraniuk under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by Genaro Picazo on Jul 6, 2004 8:30 pm GMT-5.