Best fit curve using Q-R Factorization?

[Jamin2112]

Best fit curve using Q-R Factorization?

Homework Statement

Homework Equations

The Attempt at a Solution

So ... It's part (a) that is confusing me. I already factored it into Q and R. But does the Q-R Factorization have to do with best-fit lines? (To be fair, I'm working on homework that's due next friday; so this might be something we go over later in the week.)

 

[Wingeer]

You will want to find an x that minimizes [tex]||r=b-Ax||^2[/tex] where A is an mxn matrix, and m>n. But A=QR, so r=b-QRx which is equivalent to Q^T = Q^T b - Rx. Observe then that:
[tex]Q^T r = \left[ {\begin{array}{cc}
(Q^Tb)_n - R_n x \\
Q^T b_{m-n} \\
\end{array} } \right] = \left[ {\begin{array}{cc}
u \\
v \\
\end{array} } \right][/tex]
where
[tex]R=\left[ {\begin{array}{cc}
R_n \\
0 \\
\end{array} } \right][/tex]
i.e. R is padded with zeros so that it will multiply.
Also observe that
||r||^2 = r^T r = r^T QQ^T r = u^T u + v^T v. But since v is independent of x we find the minimal value of ||r||^2 when u=0 or when
[tex]R_n x = (Q^T b)_n[/tex].

 

[Jamin2112]

You will want to find an x that minimizes [tex]||r=b-Ax||^2[/tex] where A is an mxn matrix, and m>n. But A=QR, so r=b-QRx which is equivalent to Q^T = Q^T b - Rx. Observe then that:
[tex]Q^T r = \left[ {\begin{array}{cc}
Q^Tb_n - R_n x \\
Q^T b_{m-n} \\
\end{array} } \right] = \left[ {\begin{array}{cc}
u \\
v \\
\end{array} } \right][/tex]
where
[tex]R=\left[ {\begin{array}{cc}
R_n \\
0 \\
\end{array} } \right][/tex]
i.e. R is padded with zeros so that it will multiply.
Also observe that
||r||^2 = r^T r = r^T QQ^T r = u^T u + v^T v. But since v is independent of x we find the minimal value of ||r||^2 when u=0 or when
[tex]R_n x = Q^T b_n[/tex].

Still a little confused herre. I'm minimizing ||b - QRx||, of course. I know that an orthonormal matrix's inverse is equal to its transpose, I know that an the inverse of an upper triangular matrix is easy to calculate ... how does this all come together?

 

[Wingeer]

It all comes together to solving the equation [tex]R_n x = (Q^T b)_n[/tex] for x as I derived. Observe my mistake in the last equation in the previous post which I have corrected in this post. The solution to that system will be the best fit, in your case x is alpha, beta, gamma. R_n is the part of R without zeros, Q transposed is Q transposed and b is the values for y.

 

[Jamin2112]

Here me out, brah.

So this one website gave a simple explanation:

Simple enough. I decided to use it on the following problem.

My code looked like the following.

And of course it isn't working because I can't use the backslash command with a non-square matrix.

 

[Jamin2112]

[PLAIN]http://www.docrafts.com/Content/Forum/Member/45338/bump%20hippo.jpg

 

[I like Serena]

Hi Jamin2112!

Nice pics!

The method to use QR decomposition to find a least squares fit is described here:
http://en.wikipedia.org/wiki/Numeri...east_squares#Orthogonal_decomposition_methods

Note that this article is supposedly about linear least squares, but this method applies in your case as well.

[edit] Oh, I see this is exactly what Wingeer described.
I presume your problem is to get it to work in matlab? [/edit]

[edit2] Please google "back substution in matlab" or something like that. [/edit2]

 

[Wingeer]

Your code is good. Only thing you have to do is pad the matrices with zeros, so that they can multiply.