Projection onto 1D subspaces

Loading...

From the course by Imperial College London

Mathematics for Machine Learning: PCA

172 ratings

Imperial College London

Mathematics for Machine Learning: PCA

172 ratings

Course 3 of 3 in the Specialization Mathematics for Machine Learning

This intermediate-level course introduces the mathematical foundations to derive Principal Component Analysis (PCA), a fundamental dimensionality reduction technique. We'll cover some basic statistics of data sets, such as mean values and variances, we'll compute distances and angles between vectors using inner products and derive orthogonal projections of data onto lower-dimensional subspaces. Using all these tools, we'll then derive PCA as a method that minimizes the average squared reconstruction error between data points and their reconstruction. At the end of this course, you'll be familiar with important mathematical concepts and you can implement PCA all by yourself. If you’re struggling, you'll find a set of jupyter notebooks that will allow you to explore properties of the techniques and walk you through what you need to do to get on track. If you are already an expert, this course may refresh some of your knowledge. The lectures, examples and exercises require: 1. Some ability of abstract thinking 2. Good background in linear algebra (e.g., matrix and vector algebra, linear independence, basis) 3. Basic background in multivariate calculus (e.g., partial derivatives, basic optimization) 4. Basic knowledge in python programming and numpy Disclaimer: This course is substantially more abstract and requires more programming than the other two courses of the specialization. However, this type of abstract thinking, algebraic manipulation and programming is necessary if you want to understand machine learning algorithms.

From the lesson

Orthogonal Projections

In this module, we will look at orthogonal projections of vectors, which live in a high-dimensional vector space, onto lower-dimensional subspaces. This will play an important role in the next module when we derive PCA. We will start off with a geometric motivation of what an orthogonal projection is and work our way through the corresponding derivation. We will end up with a single equation that allows us to project any vector onto a lower-dimensional subspace. However, we will also understand how this equation came about. As in the other modules, we will have both pen-and-paper practice and a small programming example with a jupyter notebook.

Welcome to module 30:40

Projection onto 1D subspaces7:42

Example: projection onto 1D subspaces3:26

Projections onto higher-dimensional subspaces8:33

Example: projection onto a 2D subspace3:52

This was module 3!0:32

Meet the Instructors

Marc P. Deisenroth
Lecturer in Statistical Machine Learning
Department of Computing

In this video, we'll look at orthogonal

projections of vectors onto one-dimensional subspaces.

Let's look at an illustration.

We are given vector x in two dimensions,

and x can be represented as a linear combination of the basis vectors of r2.

We also have one-dimensional subspace u with a basis vector b.

That means all vectors in u can be represented as lambda time b for some lambda.

Now we're interested in finding a vector in u that is closest to x.

Let's have a look at this.

When I compute the length of the difference of all vectors in u and the vector x,

I'm getting the graph on the right.

It turns out that we can't find the vector in u that is closest to x,

but orthogonal projection of x onto u.

That means the difference vector of x and its projection is orthogonal to u.

Overall, we are looking for the orthogonal projection of x onto u,

and we will denote this projection by pi u of x.

The projection has two important properties.

First, since pi u of x is in u,

it follows that there exists a lambda in r such that

pi u of x can be written as lambda times,

b the multiple of the basis vector that spans u.

The lambda is the coordinate of

the projection with respect to the basis b of the subspace u.

The second property is that

the difference vector of x and its projection onto u is orthogonal to u.

That means it's orthogonal to the basis vector that spans u.

So, the second property is that the inner product between b and

the difference between pi u of x and x is zero.

So that's the orthogonality condition.

These properties generally hold for any x in RD and one-dimensional subspaces u.

Now let's explore these two properties to find

pi u of x. I found the setting once more over here.

We have a two-dimensional vector x.

We have one-dimensional subspace u which is spanned by the vector b.

And we're interested in finding

the orthogonal projection of x onto u which we call pi u of x.

And we have two conditions for pi u of x.

The first thing is that since pi u of x is an element of u,

we can write it as a scaled version of the vector b.

There must be a lambda in r such that pi u of x is lambda times b.

And the second condition is

the orthogonality condition that the difference vector between

x and pi u of x is orthogonal to u,

which means it's orthogonal to the spanning vector b.

And now let's explore these two properties to find pi u of x.

So, first, we start writing.

We use the condition that b and pi u of x minus x inner product is zero,

which is equivalent to that the inner product of b and pi u of

x minus the inner product of b and x

is zero where we exploit it now the linearity of the inner product.

Now we are going to rewrite pi u of x as lambda times b.

So, this is equivalent to b times lambda b,

or inner product with lambda b minus inner product of b and x. That must be zero.

Now we can move the lambda out again because of the linearity of the inner product,

which is then lambda times the squared norm of b minus the inner product of b,

and x must be zero.

And that is equivalent to lambda is

the inner product of b with x divided by the squared norm of b.

So, now we found lambda which is

the coordinate of our projection with respect to the basis b.

And that means that

our projection using the first condition is lambda times b,

which is now the inner product of b with x divided by the squared norm of b times b.

If we choose the dot product as the inner product,

we can rewrite this in a slightly different way.

So, we would get b transpose times x times b divided by the squared norm of b.

So now, given that this one is a scaler,

we can just move it over here.

So, this is equivalent then to saying b times b transpose divided by

the squared norm of b times x is our projected point.

And if we look at this,

this is a matrix.

And this matrix is a projection matrix that projects

any point in two-dimensions onto the one-dimensional subspace.

So now, if we look at the special case of b having norm one,

then we get a much simpler result.

So, if the norm of b equals one,

then we will get that lambda is b transpose times x,

and pi u of x is b times b transpose times x.

So, we would get the coordinate of the projected point with

respect to the basis b just by looking at the dot product of b with x.

And the projection matrix is simply given by b times b transpose.

Let me make a comment at the end.

Our projection pi u of x is still a vector in RD.

However, we no longer require D coordinates to represent it,

but we only need a single one,

which is the lambda.

In this video, we discussed orthogonal projections of

vectors onto one-dimensional subspaces.

We arrived at the solution by making two observations.

You must be able to represent the projected point

using a multiple of the basis vector that spans the subspace.

And the difference vector between the original vector and

its projection is orthogonal to the subspace.

In the next video, we will look at an example.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play