Modified Gram Schmidt

Question

How does the Modified Gram Schmidt works? I want to use it but I am confused by the notations and I could not find any example online.

Answer 1

First, let's establish Gram Schmidt (sometimes called Classical GS) to be clear.

We use GS because we wish to solve the system $A \overrightarrow{x} = \overrightarrow{b}$. We want to compute $\overrightarrow{x}$ s.t. $||\overrightarrow{r}||_2$ is minimized where $\overrightarrow{r} = A\overrightarrow{x} - \overrightarrow{b}$.

One way is GS, where we define $A =QR$ s.t. $Q^TQ=I$ where $I$ is the identity matrix of size n x n and $R$ is an upper right triangular matrix of size n x n.

Our goal is to find $$\{ \overrightarrow{q}_1 , \overrightarrow{q}_2 , \cdots, \overrightarrow{q}_n \}$$ s.t. $$span \{ \overrightarrow{q}_1 , \overrightarrow{q}_2 , \cdots, \overrightarrow{q}_n \} = span \{\overrightarrow{a}_1 , \overrightarrow{a}_2 , \cdots, \overrightarrow{a}_n \}$$

Also, let us define the dot product as, $$<a,b>$$

Then we want

$$<\overrightarrow{q}_i , \overrightarrow{q}_j > \quad = 0 \quad if \quad i \not=j$$

$$<\overrightarrow{q}_i , \overrightarrow{q}_j > \quad = 1 \quad if \quad i = j$$

Suppose $\{ \overrightarrow{q}_1 , \overrightarrow{q}_2 , \cdots, \overrightarrow{q}_r \}$ are already found, then we can find $\overrightarrow{q}_{r+1}$ by the following

$$\overrightarrow{q}_{r+1} = \overrightarrow{a}_{r+1} - <\overrightarrow{a}_{r+1},\overrightarrow{q}_1>\overrightarrow{q}_1 - <\overrightarrow{a}_{r+1},\overrightarrow{q}_2>\overrightarrow{q}_2 - \cdots - <\overrightarrow{a}_{r+1},\overrightarrow{q}_r>\overrightarrow{q}_r$$

In other words, the above is our generic case on how to solve for $\overrightarrow{q}_i$.

Let's look at an example:

$$ \overrightarrow{a}_1 = \begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}$$

$$ \overrightarrow{a}_2 = \begin{pmatrix} -1 \\ 0 \\ 2 \end{pmatrix}$$

$$ \overrightarrow{a}_3 = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$$

It is important to note this process only works if our columns are linearly independent. You can check this by taking the determinant of our matrix A. If it $\not= 0$, it's linearly independent.

$$det \begin{pmatrix} 1 & -1 & 0 \\ 2 & 0 & 0 \\ 2 & 2 & 1 \end{pmatrix} = 3$$

We are good, so let's continue.

$$r_{11} = ||\overrightarrow{a}_1 ||_2 = (1^2 + 2^2 +2^2)^{\frac{1}{2}} = 3$$

$$\overrightarrow{q}_1 = \frac{\overrightarrow{a}_1}{r_{11}} = \frac{1}{2} \begin{pmatrix} 1 \\ 2\\ 2 \end{pmatrix}$$

$$\overrightarrow{q}_2 = \overrightarrow{a}_2 - <\overrightarrow{a}_2, \overrightarrow{q}_1> \overrightarrow{q}_1$$

$$\overrightarrow{q}_2 = \begin{pmatrix} -1 \\ 0 \\ 2 \end{pmatrix} - \left(\frac{-1}{3} + (2) \left( \frac{2}{3} \right) \right) \frac{1}{3} \begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}$$

$$\overrightarrow{q}_2 = \begin{pmatrix} \frac{-4}{3} \\ \frac{-2}{3} \\ \frac{4}{3} \end{pmatrix}$$

Now $\overrightarrow{q}_2$ needs to be normalized.

$$\overrightarrow{q}_2 = \frac{\overrightarrow{q}_2}{||\overrightarrow{q}_2||_2} = \begin{pmatrix} \frac{-2}{3} \\ \frac{-1/3} \\ \frac{2}{3} \end{pmatrix}$$

Our left hand side $\overrightarrow{q}_2$ is our new $\overrightarrow{q}_2$ value.

Now we need to solve for $\overrightarrow{q}_3$.

$$\overrightarrow{q}_3 = \overrightarrow{a}_3 - < \overrightarrow{a}_3 , \overrightarrow{q}_1 > \overrightarrow{q}_1 - <\overrightarrow{a}_3 , \overrightarrow{q}_2> \overrightarrow{q}_2$$

$$\overrightarrow{q}_3 = \begin{pmatrix} 0 \\ 0\\ 1 \end{pmatrix} - \frac{2}{3} \begin{pmatrix} \frac{1}{3} \\ \frac{2}{3} \\ \frac{2}{3} \end{pmatrix} - \begin{pmatrix} \frac{-2}{3} \\ \frac{-1}{3} \\ \frac{2}{3} \end{pmatrix} $$

$$\overrightarrow{q}_3 = \begin{pmatrix} \frac{2}{9} \\ \frac{-2}{9} \\ \frac{1}{9} \end{pmatrix}$$

Once again, it needs to be normalized. $\overrightarrow{q}_3$ becomes

$$\overrightarrow{q}_3 = \frac{\overrightarrow{q}_3}{||\overrightarrow{q}_3||_2} = \begin{pmatrix} \frac{2}{3} \\ \frac{-2}{3} \\ \frac{1}{3} \end{pmatrix}$$

Now $r_{ij} = < \overrightarrow{a}_j , \overrightarrow{q}_i>$ when $i \not=j$ and $r_{ii} = || \overrightarrow{a}||_2$

With this knowledge we find $r_{12} = 1$, $r_{22} = 2$, $r_{13} = \frac{2}{3}$, $r_{23} = \frac{2}{3}$, and $r_{33} = \frac{1}{3}$

Now we have all the pieces and parts.

$$ Q = \begin{pmatrix} = \frac{1}{3} & \frac{-2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{-1}{3} & \frac{-2}{3} \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \end{pmatrix}$$

and

$$ R = \begin{pmatrix} = 3 & 1 & \frac{2}{3} \\ 0 & 2 & \frac{2}{3} \\ 0 & 0 & \frac{1}{3} \end{pmatrix}$$

Remember that we wanted $A = QR$, so now we have

$$ A = \begin{pmatrix} = \frac{1}{3} & \frac{-2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{-1}{3} & \frac{-2}{3} \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \end{pmatrix} \begin{pmatrix} = 3 & 1 & \frac{2}{3} \\ 0 & 2 & \frac{2}{3} \\ 0 & 0 & \frac{1}{3} \end{pmatrix}$$

However, it's a good idea to check if $QR$ actually equals $A$ (ours does). At this point you can use QR factorization to solve.

However, that's not the point of this solution.

Modified Version of Gram Schmidt:

In classical GS we solve for $\overrightarrow{q}_j$ directly. In Modified GS we take multiple steps to get to $\overrightarrow{q}_j$. This takes care of errors like floating point errors when solving by computer $$\overrightarrow{q}_j^0 = \overrightarrow{a}_j$$

$$\overrightarrow{q}_j^1 = \overrightarrow{q}_j^0 - <\overrightarrow{q}_j^0 , \overrightarrow{q}_1> \overrightarrow{q}_1$$

$$\overrightarrow{q}_j^2 = \overrightarrow{q}_j^1 - <\overrightarrow{q}_j^1 , \overrightarrow{q}_2> \overrightarrow{q}_2$$

$$ \cdots$$

$$\overrightarrow{q}_j^{j-1} = \overrightarrow{q}_j^{j-2} - <\overrightarrow{q}_j^{j-2} , \overrightarrow{q}_{j-1}> \overrightarrow{q}_{j-1}$$

And as with Classical GS, it needs to be normalized to give a final result of

$$\overrightarrow{q}_j = \frac{\overrightarrow{q}_j^{j-1}}{||\overrightarrow{q}_j^{j-1}||_2}$$

The key to Modified GS is every $\overrightarrow{q}_i$ needs to be solved this way. The values of $r_{ij}$ and $\overrightarrow{q}_i$ (note this is $\overrightarrow{q}$ with no superscript) are still solved the same as in Classical GS. Again, solve for $Q$ and $R$ and then solve by QR Factorization.