5
$\begingroup$

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'.

1 Answers 1

5

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.

  • 1
    To add to Sivaram's answer: [Gram-Schmidt isn't so bad (when suitably modified, that is).](http://dx.doi.org/10.1007/BF01934122) 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.2011-04-10