Finding orthonormal set using Gram-Schmidt and least squares


by tatianaiistb
Tags: gram-schmidt, least squares, subspaces
tatianaiistb
tatianaiistb is offline
#1
Oct26-11, 09:20 PM
P: 47
1. The problem statement, all variables and given/known data

A) Find an orthonormal set q1, q2, q3 for which q1,q2 span the column space A [1 1; 2, -1; -2,4] (this is a 3x2 matrix).

B) Which fundamental subspace contains q3?

C) What is the least-squares solution of Ax=b if b=[1 2 7]T?

2. Relevant equations

Gram-Schmidt

3. The attempt at a solution

A) So I figured out q1, q2, and q3 using Gram-Schmidt process. These are q1 = [1/3 2/3 -2/3]T, q2 = [2/3 1/3 2/3]T, and q3 = +-[-2/3 2/3 1/3]T

B) Don't know how to determine this

C) For the least square, since they are orthonormal sets, I used the formula x= [q1Tb; q2Tb] However, I'm not getting the right answer. In addition, I tried doing it the long way using the formula x=(ATA)-1ATb, I'm getting even different numbers... Please help!
1. The problem statement, all variables and given/known data



2. Relevant equations



3. The attempt at a solution
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
TheoMcCloskey
TheoMcCloskey is offline
#2
Oct27-11, 12:06 PM
P: 181
You found the orthonormal set (Q), but that is not equal to A. What is A equal to?
tatianaiistb
tatianaiistb is offline
#3
Oct27-11, 01:46 PM
P: 47
[1 1
2 -1 = A
-2 4]

I'm now only having trouble with part C. Thanks!

TheoMcCloskey
TheoMcCloskey is offline
#4
Oct27-11, 02:00 PM
P: 181

Finding orthonormal set using Gram-Schmidt and least squares


Yes, I understand. But there is another way to represent [itex]A[/itex] using the orthogonal basis that you constructed and another factor of [itex]A[/itex]. This factor, call it [itex]R[/itex], is an upper right triangular matrix. [itex]R[/itex] is constructed such that [itex]QR = A[/itex]. We note [itex]Q[/itex] is orthogonal so [itex]Q^{T} = Q[/itex]. Thus, using this factorization for [itex]A[/itex] in the normal equations yields a linear triangualr system for solving the Least Squares problem.
TheoMcCloskey
TheoMcCloskey is offline
#5
Oct27-11, 02:02 PM
P: 181
I should add that, as part of the construction of Q, you will have already computed the elements of R.
tatianaiistb
tatianaiistb is offline
#6
Oct27-11, 06:50 PM
P: 47
Thanks Theo! I do understand about A=QR and the construction of it. But I don't understand how that can help me finding x(hat), which is the least-squares solution.

What I was thinking is that x(hat)=Q^T*b because Q has already orthonormal vectors.

I'm getting that x(hat) = (-3 6 3)^T, but it says the solution is supposed to be x(hat) = [1 2]^T which they supposedly got from q1^Tb and q2^Tb. However, if I multiply the very same q's I got (which I was confirmed are correct) by the given b, I'm not getting the given answer. So I'm going in circles... Any help?
TheoMcCloskey
TheoMcCloskey is offline
#7
Oct28-11, 06:54 AM
P: 181
Firstly, let me make a correction to one of my previous posts (post #4).

We note [itex]Q[/itex] is orthogonal so [itex]Q^{T}=Q[/itex].
should read

We note [itex]Q[/itex] is orthogonal so [itex]Q^{T}=Q^{-1}[/itex].
Secondly, return to the Normal equations for the Least Squares solution:

[tex]
A^{T}A \, x = A^{T} \, b
[/tex]
Now substitute the factor expresion for [itex]A[/itex], ie, [itex]A=QR[/itex]
[tex](QR)^{T}(QR)\,x = (QR)^{T}b[/tex]
[tex]R^{T}(Q^{T}Q)\,R\,x = R^{T}Q^{T}b[/tex]
[tex]R^{T}R\,x = R^{T}Q^{T}b[/tex]
since [itex]Q^{T}Q=I[/itex]. Now pre-multiply both sides by [itex]R^{-T}[/itex] to yield
[tex]R\,x = Q^{T}b[/tex]
It is this system that you need to solve for [itex]x[/itex] to yield the Least Squares solution. Remember, just because you found the orthogonal basis for [itex]A[/itex] doesn't mean its equal to [itex]A[/itex] . There is a certain amount of translation and rotation of that basis to yield that [itex]A[/itex] (hence the [itex]R[/itex] factor).

Remember, [itex]R[/itex] is triangular, so a simple backsolve operation will yield the solution (no need to compute [itex]R^{-1}[/itex]).


Register to reply

Related Discussions
Gram-Schmidt procedure to find orthonormal basis Calculus & Beyond Homework 5
Orthonormal basis/Gram-Schmidt [Easy?] Calculus & Beyond Homework 6
Gram-Schmidt orthonormal basis Calculus & Beyond Homework 6
Gram-Schmidt problem - I'm stuck Linear & Abstract Algebra 9
Gram Schmidt Linear & Abstract Algebra 2