Gram-Schmidt orthogonalization : Graphics

Hi everyone,

This is a newbie question. Just going through the initial chapter on
vectors and I think I understand the orthogonalization process but I am
having trouble visualizing it geometrically...

>From the wiki:

Geometrically, this method proceeds as follows: to compute ui, it
projects vi orthogonally onto the subspace U generated by u1, …,
ui−1, which is the same as the subspace generated by v1, …,vi−1.
The vector ui is then defined to be the difference between vi and this
projection, guaranteed to be orthogonal to all of the vectors in the
subspace U.

Say we are in working in 3 dimensional space... So there exist 3
vectors in the orthogonal basis..

So the first vector does not change...

The second vector is calculated by projecting the second vector on the
first vector and subtracting it from the second vector so whatever s
left over must be orthogonal...

Now, for the third vector... we project it on the first two orthonormal
vectors (u1, u2)... So this will result in 2 vectors... and when I
subtract them from the third vector, why is it guaranteed to be
orthogonal to all the vectors in the subspace. I know that each of the
projections individually are orthogonal to the vector but how is the
difference (v3 - proj(v3 on u1) - proj(v3 on u2)) guranteed to be
orthogonal.

I hope I was able to phrase the question properly. Would appreciate any
help on this one.

Thanks,
Anja

Anja ha scritto:

> Hi everyone,
>
> This is a newbie question. Just going through the initial chapter on
> vectors and I think I understand the orthogonalization process but I am
> having trouble visualizing it geometrically...
>
> >From the wiki:
>
> Geometrically, this method proceeds as follows: to compute ui, it
> projects vi orthogonally onto the subspace U generated by u1, …,
> ui−1, which is the same as the subspace generated by v1, …, vi−1.
> The vector ui is then defined to be the difference between vi and this
> projection, guaranteed to be orthogonal to all of the vectors in the
> subspace U.
>
> Say we are in working in 3 dimensional space... So there exist 3
> vectors in the orthogonal basis..
>
> So the first vector does not change...
>
> The second vector is calculated by projecting the second vector on the
> first vector and subtracting it from the second vector so whatever s
> left over must be orthogonal...
>
> Now, for the third vector... we project it on the first two orthonormal
> vectors (u1, u2)... So this will result in 2 vectors... and when I
> subtract them from the third vector, why is it guaranteed to be
> orthogonal to all the vectors in the subspace. I know that each of the
> projections individually are orthogonal to the vector but how is the
> difference (v3 - proj(v3 on u1) - proj(v3 on u2)) guranteed to be
> orthogonal.

1) Let * denote the scalar product. Its result is a number, not a
vector.

2) u_j are unit normal vectors, so that
u_j * u_k = 0 if j != k
and
u_J * u_k = 1 if j == k.

3) proj (v_i, u_j) means (v_i * u_j) u_j, that is a vector parallel to
u_j and with module (length) v_i * u_j.

4) Then
v_3' = v_3 - proj(v_3, u_1) - proj(v_3, u_2)
can be rewritten as
v_3' = v_3 - (v_3 * u_1)u_1 - (v_3 * u_2)u_2

5) With the above information, now compute v_3' * u_1 and v_3' * u_2.
What is the result?

>
> I hope I was able to phrase the question properly. Would appreciate any
> help on this one.
>
> Thanks,
> Anja

Anja,

the Gram-Schmidt orthogonalization can be written
somewhat simplified by using normalized base vectors.
A sketch here illustrates the creation of the third base
vector:
http://www.fho-emden.de/~hoffmann/gram-schmidt.pdf

The doc refers as well to Sigurd Falk, Matrizen, Springer.
Here we can find an elegant orthogonalization, merely
by matrix operations (without the somewhat tedious
Gram-Schmidt decomposition). The book is more than
20 years old, the method dates back to 1951 or so.

Best regards --Gernot Hoffmann

"Anja" <anja.ende@googlemail.com> wrote in message
news:1164323109.592032.296380@l39g2000cwd.googlegr oups.com...
Hi everyone,

This is a newbie question. Just going through the initial chapter on
vectors and I think I understand the orthogonalization process but I am
having trouble visualizing it geometrically...

>From the wiki:

Geometrically, this method proceeds as follows: to compute ui, it
projects vi orthogonally onto the subspace U generated by u1, .,
ui?1, which is the same as the subspace generated by v1, ., vi?1.
The vector ui is then defined to be the difference between vi and this
projection, guaranteed to be orthogonal to all of the vectors in the
subspace U.

Say we are in working in 3 dimensional space... So there exist 3
vectors in the orthogonal basis..

So the first vector does not change...

The second vector is calculated by projecting the second vector on the
first vector and subtracting it from the second vector so whatever s
left over must be orthogonal...

Now, for the third vector... we project it on the first two orthonormal
vectors (u1, u2)... So this will result in 2 vectors... and when I
subtract them from the third vector, why is it guaranteed to be
orthogonal to all the vectors in the subspace. I know that each of the
projections individually are orthogonal to the vector but how is the
difference (v3 - proj(v3 on u1) - proj(v3 on u2)) guranteed to be
orthogonal.
----


note that if you have a two vectors v1, v2

then the projection of v2 onto v1, i.e., Proj_v1(v2)

is a vector s.t., if you treat v2 as the hypotenuse and Proj_v1(v2) as a
"leg" then they form a right triangle. i.e. ||Proj_v1(v2)|| = ||v2||*cos(t)

Therefore if we write treat the the sides of the right triangle we can get
the other side by vector subtraction, therefore

v2 - Proj_v1(v2) is a vector that is orthogonal to v1.

Now, suppose we have a third vector v3, We know that by the same logic above
the two vectors

v3 - Proj_v2(v3)
v3 - Proj_(v2 - Proj_v1(v2))(v3)

are orthogonal to v2 and v2 - Proj_v2(v2))(v3) respectively. We do not know
if they are orthogonal "pairwise"... i.e.

is
<v1, v3 - Proj_v2(v3)> = 0
<v1, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
<v2, v3 - Proj_v2(v3)> = 0
<v2, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
?

The answer to that is obviously no to some, it must be true for all... and
besides that, we only want one vector.

But here we see that

<v1, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
<v2, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0

You can see this by doing the math or looking at it geometrically and
notating that the vectors form a cube(or right triangle)

So inactuality the vector

v3 - Proj_(v2 - Proj_v1(v2))(v3) suits our needs and is orthogonal not just
to v2(which by construction it is) but also to v1. Its orthogonal to v1
because its construction took it out of the plane that is spaned by v1 and
v2 and hence it must be.

Now you might think that we could find a vector that is orthogonal to v2 but
not orthogonal to v1 and this is true, but the nature of v3 - Proj_(v2 -
Proj_v1(v2))(v3) is a vector that is orthogonal to v1. It is because it
"contains" the vector that is orthogonal to v1 and v2.

If you don't understand this then I suggest you either do the math and carry
about the last 2 equations or you look at it geometrically to see what is
going on.

You could also try and find the orthogonal vector to the plane constructed
by v1 and v2. You will get a vector that is parallel to v3 - Proj_(v2 -
Proj_v1(v2))(v3).

Also, note that

v3 - Proj_v2(v3) is a vector that is orthogonal to v2 but not to v1. This
the other possible vector. If the Gram-Scmidt process chose this one then it
wouldn't work.

Convince yourself that there are only two possible vectors(in R^3)
orthogonal to v2 that are not also orthogonal to v3 but one of these must be
orthogonal to v1 and the other will not be. Actually, in general, its more
complicated because each time you have orthogonal vectors but not orthogonal
to all the other previous vectors. But there is one only orthogonal to all
and this is, in some sense, a combination of all.

The point isn't so much to be able to conceptualize this in N dimensions but
to realize that the process is recursive(which you can prove by induction
easily). Your not going to be able to understand how the 37 vector is
orthogonal to all the others in any real sense except by inductive
reasoning.

Jon

Jon Slaughter wrote:

> "Anja" <anja.ende@googlemail.com> wrote in message
> news:1164323109.592032.296380@l39g2000cwd.googlegr oups.com...
> Hi everyone,
>
> This is a newbie question. Just going through the initial chapter on
> vectors and I think I understand the orthogonalization process but I am
> having trouble visualizing it geometrically...
>
> >From the wiki:
>
> Geometrically, this method proceeds as follows: to compute ui, it
> projects vi orthogonally onto the subspace U generated by u1, .,
> ui?1, which is the same as the subspace generated by v1, ., vi?1.
> The vector ui is then defined to be the difference between vi and this
> projection, guaranteed to be orthogonal to all of the vectors in the
> subspace U.
>
> Say we are in working in 3 dimensional space... So there exist 3
> vectors in the orthogonal basis..
>
> So the first vector does not change...
>
> The second vector is calculated by projecting the second vector on the
> first vector and subtracting it from the second vector so whatever s
> left over must be orthogonal...
>
> Now, for the third vector... we project it on the first two orthonormal
> vectors (u1, u2)... So this will result in 2 vectors... and when I
> subtract them from the third vector, why is it guaranteed to be
> orthogonal to all the vectors in the subspace. I know that each of the
> projections individually are orthogonal to the vector but how is the
> difference (v3 - proj(v3 on u1) - proj(v3 on u2)) guranteed to be
> orthogonal.
> ----
>
>
> note that if you have a two vectors v1, v2
>
> then the projection of v2 onto v1, i.e., Proj_v1(v2)
>
> is a vector s.t., if you treat v2 as the hypotenuse and Proj_v1(v2) as a
> "leg" then they form a right triangle. i.e. ||Proj_v1(v2)|| = ||v2||*cos(t)
>
> Therefore if we write treat the the sides of the right triangle we can get
> the other side by vector subtraction, therefore
>
> v2 - Proj_v1(v2) is a vector that is orthogonal to v1.
>
> Now, suppose we have a third vector v3, We know that by the same logic above
> the two vectors
>
> v3 - Proj_v2(v3)
> v3 - Proj_(v2 - Proj_v1(v2))(v3)
>
> are orthogonal to v2 and v2 - Proj_v2(v2))(v3) respectively. We do not know
> if they are orthogonal "pairwise"... i.e.
>
> is
> <v1, v3 - Proj_v2(v3)> = 0
> <v1, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
> <v2, v3 - Proj_v2(v3)> = 0
> <v2, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
> ?
>
> The answer to that is obviously no to some, it must be true for all... and
> besides that, we only want one vector.
>
> But here we see that
>
> <v1, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
> <v2, v3 - Proj_(v2 - Proj_v1(v2))(v3)> = 0
>
> You can see this by doing the math or looking at it geometrically and
> notating that the vectors form a cube(or right triangle)
>
> So inactuality the vector
>
> v3 - Proj_(v2 - Proj_v1(v2))(v3) suits our needs and is orthogonal not just
> to v2(which by construction it is) but also to v1. Its orthogonal to v1
> because its construction took it out of the plane that is spaned by v1 and
> v2 and hence it must be.
>
> Now you might think that we could find a vector that is orthogonal to v2 but
> not orthogonal to v1 and this is true, but the nature of v3 - Proj_(v2 -
> Proj_v1(v2))(v3) is a vector that is orthogonal to v1. It is because it
> "contains" the vector that is orthogonal to v1 and v2.
>
> If you don't understand this then I suggest you either do the math and carry
> about the last 2 equations or you look at it geometrically to see what is
> going on.
>
> You could also try and find the orthogonal vector to the plane constructed
> by v1 and v2. You will get a vector that is parallel to v3 - Proj_(v2 -
> Proj_v1(v2))(v3).
>
> Also, note that
>
> v3 - Proj_v2(v3) is a vector that is orthogonal to v2 but not to v1. This
> the other possible vector. If the Gram-Scmidt process chose this one then it
> wouldn't work.
>
> Convince yourself that there are only two possible vectors(in R^3)
> orthogonal to v2 that are not also orthogonal to v3 but one of these must be
> orthogonal to v1 and the other will not be. Actually, in general, its more
> complicated because each time you have orthogonal vectors but not orthogonal
> to all the other previous vectors. But there is one only orthogonal to all
> and this is, in some sense, a combination of all.
>
> The point isn't so much to be able to conceptualize this in N dimensions but
> to realize that the process is recursive(which you can prove by induction
> easily). Your not going to be able to understand how the 37 vector is
> orthogonal to all the others in any real sense except by inductive
> reasoning.
>
> Jon

Hi Jon,

Thanks for the explanation! I had missed the point that making the
vectors orthogonal to the projections, we are basically taking them out
of the plane... It is clear to me now..

Thanks,
Anja

"Anja" <anja.ende@googlemail.com> wrote in message
news:1164503284.473682.93350@l12g2000cwl.googlegro ups.com...
>
> Jon Slaughter wrote:
<snip>
> Hi Jon,
>
> Thanks for the explanation! I had missed the point that making the
> vectors orthogonal to the projections, we are basically taking them out
> of the plane... It is clear to me now..

Well, not out of the plane, but the hyperplane formed by all previous
vectors.

So the first vector sets up a line and you are finding an orthogonal(normal)
vector to it. Now you take these two vectors and they represent a plane...
take the normal vector to that.... etc... etc... etc...


You can also think of it as looking at the orthogonal subspace to the space
generated by all the previous vectors.

In R^n, if we have v1 then the subspace generated by v1 has an orthogonal
subspace. Any vector in this space will work to be our second vector. The
Gram-Schmidt method chooses a vector that is also contained in the subspace
generated by v1 and v2.

i.e.

step 1: pick vector orthogonal to the subspace generated by v1 but contained
in the subspace generated by {v1, v2}.

step 2: pick a vector orthogonal to the subspace generated by {v1,v2} but
contained in the subspace generated by {v1,v2,v3}

etc...

Theoretically one can just find choose any vector that is in the orthogonal
subspace to v1. i.e., if you know how to find the orthogonal subspace of v1
then just choose a vector in it. then we have v2 which we know is orthogonal
to v1. Now do the same for the subspace generated by {v1, v2}. etc...

Here the idea is very similar to the above but the Gram-Schmidt method uses
the fact that we already have a set of vectors to try and simplify the
mathematics. (i.e., the only difference between the "general" method and
this Gram-Schmidt is the "contained in the subspace generated by" in the
steps above.


Anyways, just trying to point out some things for nostalgia.

Jon