Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to follow/understand a research paper that I have, and well, it's been a while since I've done this kind of math. At this point I have an nxn matrix H and from that construct an (n-1)xn matrix H' = $[\textbf{h}_1-\textbf{h}_n$, ..., $\textbf{h}_{1-n}-\textbf{h}_n]^T$. Now "using orthogonal decomposition" I'm to obtain H'=$\textbf{QU}$, where $\textbf{Q}$ is an (n-1)x(n-1) orthogonal matrix and $\textbf{U}$, which is an (n-1)xn upper diagonal matrix.

I guess I'm hoping someone can better explain orthogonal decomposition and help me write the elements of $\textbf{Q}$ and $\textbf{U}$ in terms of the elements of H'.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

Look up QR decomposition. QR decomposition decomposes the matrix as a product of an orthonormal matrix and an upper triangular matrix. i.e. $QQ^T = Q^TQ = I$ and $R$ is upper triangular. QR decomposition is nothing but Gram-Schmidt orthogonalization process. It is relatively easy to code up QR based on Gram Schmidt orthogonalization process. Wikipedia does a nearly complete job of explaining both QR and Gram-Schmidt. The main idea behind QR/Gram Schmidt is to construct an orthonormal basis for the column space/range of $A$ using the columns of the matrix $A$. The idea is relatively simple.

  1. Take the first column of $A$ and make it into a unit vector by dividing out by the norm
  2. Take the second column of $A$ and remove the component along the first column of $A$ and make it into a unit vector by dividing out by the norm
  3. In general, take the $k^{th}$ column of $A$ and remove the components from the previous $k-1$ columns of $A$ (i.e. remove the subspace spanned by the first $k-1$ columns of $A$) and make it into a unit vector by dividing out by the norm

    This orthonormal set of vectors give you the $Q$ matrix and the (rotation) operations you perform on the vectors of the $Q$ matrix go into the $R$ (rotation) matrix.

However, the QR algorithm using Gram-Schmidt orthogonalization process can become unstable. Hence couple of other algorithms based on Givens Rotation, Householder reflection are used in practise since they tend to be more stable than Gram-Schmidt algorithm.

There is a one to one correspondence between the algorithm based on Givens Rotation and the algorithm based on Householder reflection. (Just like the correspondence between solving a system by Gauss Elimination and LU). So technically the stability of the algorithm based on Givens rotation is same as the stability of the algorithm based on Householder reflection.

share|improve this answer
    
Ahh, thank you so much! Having the right search terms makes all the difference. –  Alex S Feb 9 '11 at 19:54
    
To add to Sivaram's answer: Gram-Schmidt isn't so bad (when suitably modified, that is). I would agree though that in most cases, Householder is more than enough. Givens is useful mostly for sparse least-squares (or for certain structured matrices like semiseparable ones); using it for the dense problem requires more computational effort than using Householder. –  J. M. Apr 10 '11 at 17:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.