Orthogonal Projections and the Orthogonality Principle **new** 2004/06/15 16:33:37.047 GMT-5 2004/06/15 16:34:28.050 GMT-5 Richard G. Baraniuk richb@rice.edu Richard G. Baraniuk richb@rice.edu Genaro Picazo picazo@rice.edu A key problem in DSP: Given a signal y find the signal x from a subspace S that is the closest to y . y is a noisy signal and all x S are smooth.

Finding an x close to y will approximate it by a noise-free version. Geometry of the situation via linear algebra. x S x k 0 M 1 α k b k where b k are a basis for the subspace S (We assume it is an ONB).

S is an M-dim hyperplane thru the origin of N

In general, y is not S The goal is to find x S close to y , which is equivalent to finding α k . We can also measure how close x is to y by l 2 norm error in N : 2 y x 2 n 0 N 1 y n x n 2 Define e y x as the error vector and minimize l 2 strength of e .

Geometry

How close to choose - to minimize 2 x ? Choose x so that error e is ⊥ to x and ⊥ to the entire subspace S .

Orthogonality Principle 2 e is minimum when e x 0 Also have s s S e s 0 Linear algebra lets us convert a distance problem (minimize 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 onto S to obtain x closest to y in S . Now apply the OP to find the optimal approximant x S to y . Recall: y n x S N x k 0 M 1 α k b k where b k is an ONB for S .

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

Solution Apply OP: Define e y x y k α k b k Then: 0 e x y k' α k' b k' k' α k b k by linearity of OP, 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 There are 2 ways to set to zero: All α k 0 . y b k α k 0 for all k chosen. The solution to (2) is simple: y b k α k 0 or α k y b k .

Summary The optimal l 2 approximation x k α k b k to y has α k y b k when b k are an ONB for the subspace.

Projections

In , e y x , e x 0 , e S 0 x k 0 1 α k b k where b k is an ONB for S α k y b k 2 e is minimized. 2 . Find the closest x to y 2 where x lies on a 45° angled line.

Find an ONB for S, S a a x a a . ONB: b 0 1 1 2 . Optimal x k 0 0 α k b k α 0 b 0 α 0 y b 0 For example,

in , y 3 7 α 0 1 2 1 1 3 7 10 2 x 10 2 1 1 2 5 5 Given an ecg signal, y N that is a smooth signal contaminated by noise

we would like to make an estimate y ̂ that is smooth. Step1 Signal model: y x n x S , subspace of smooth functions. Find an appropriate subspace. For example, x S spanned by the 1st M≪N DCT basis vectors (lowest frequencies). x k 0 M 1 α k b k

b k in S

b k not in S

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

Note that there is more resemblence with a vector not in S that to one that is.

Step2 ⊥ project y onto S to get estimate y ̂ (In statistical DSP, this is called the inear minimum mean squared error estimate - LMMSE est.). y ̂ k 0 N 1 β k b k β k y b k

y x n

Why is y ̂ x ?

Is y ̂ closer to x than y is?

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

How do you choose the subspace and the ONB?