The examples below are of complexity similar to the problems in Homework 7. Please note that even in these small dimensional cases the arithmetic gets tiresome, hiding the simplicity of the solution by projection:

The intent of Homework 7 is to:

1. Gain familiarity with the Gram-Schmidt algorithm;

2. Understand the steps in solving the least squares problem by projection;

3. Understand the necessity of working with symbolic representations of vectors and matrices, leaving the arithmetic to software systems (Matlab/Octave).

Theory primer.

and seeks to find the scaling coefficients $𝒙\in {ℝ}^n$ required to most closely approximate $𝒃\in {ℝ}^m$ by linear combination of the columns of $𝑨=\left[\begin{array}{llll}{𝒂}_1& {𝒂}_2& \dots & {𝒂}_n\end{array}\right]\in {ℝ}^{m\times n}$.

The solution is found by orthogonal projection of $𝒃$ onto the column space of $𝑨$. It is efficient to define an orthonormal basis for the column space of $𝑨$ through the column vectors of $𝑸$

computed using the Gram-Schmidt algorithm (see below). Read $𝑸𝑹=𝑨$ to state: “linear combinations of the columns of $𝑸$ can be formed to obtain the column vectors of $𝑨$”. Therefore projectiing onto the column space of $𝑨$ is the same as projecting onto the column space of $𝑸$ and the projection matrix is

where $𝑸\in {ℝ}^{m\times r}$ is a matrix with $r$ mutually orthogonal columns of unit norm, and $r=\mathrm{rank}\left(𝑨\right)$. The matrix $𝑸=\left[\begin{array}{llll}{𝒒}_1& {𝒒}_2& \dots & {𝒒}_r\end{array}\right]$ is (see below).

The projection of $𝒃$ onto $C\left(𝑨\right)$ is a vector $𝒗$ that (since it's in the column space of $𝑨$) can also be expressed as $𝒗=𝑨𝒙$

This leads to

Note that if $𝒃\in C\left(𝑨\right)$ ($𝒃$ is in the column space of $𝑨$) then $𝒃=𝑸𝒚$ and

stating that the projection of $𝒃$ is $𝒃$ itself. In this case the least squares problem has a solution such that $𝒃=𝑨𝒙$ exactly.

1. Matrix $𝑨$ with linearly independent columns, $𝒃$ not in the column space

   ${\displaystyle 𝑨=\left[\begin{array}{ll}{𝒂}_1& {𝒂}_2\end{array}\right]=\left[\begin{array}{ll}1& -1\\ 0& 0\\ 1& 1\end{array}\right],𝒃=\left[\begin{array}{l}1\\ 1\\ 1\end{array}\right].}$

   Solution. Note that the column vectors are orthogonal

   ${\displaystyle {𝒂}_1^T{𝒂}_2=\left[\begin{array}{lll}1& 0& 1\end{array}\right]\left[\begin{array}{l}-1\\ 0\\ 1\end{array}\right]=0.}$

   Remember to first look at a problem before blindly carrying out calculations. In this case $𝑸$ is found by scaling each column vector by its norm

   ${\displaystyle 𝑸=\left[\begin{array}{ll}{𝒒}_1& {𝒒}_2\end{array}\right]=\left[\begin{array}{ll}\frac{{𝒂}_1}{||{𝒂}_1||}& \frac{{𝒂}_2}{||{𝒂}_2||}\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{ll}1& -1\\ 0& 0\\ 1& 1\end{array}\right],}$

   and the matrix $𝑹$ is a diagonal matrix containing the norms

   ${\displaystyle 𝑹=\left[\begin{array}{ll}\sqrt{2}& 0\\ 0& \sqrt{2}\end{array}\right].}$

   Verify:

   ${\displaystyle 𝑸𝑹=\frac{1}{\sqrt{2}}\left[\begin{array}{ll}1& -1\\ 0& 0\\ 1& 1\end{array}\right]\left[\begin{array}{ll}\sqrt{2}& 0\\ 0& \sqrt{2}\end{array}\right]=\left[\begin{array}{ll}1& -1\\ 0& 0\\ 1& 1\end{array}\right]\left[\begin{array}{ll}1& 0\\ 0& 1\end{array}\right]=\left[\begin{array}{ll}1& -1\\ 0& 0\\ 1& 1\end{array}\right]=𝑨}$

   Now that the $QR$ factorization has been found, here are the steps to solve the least squares problem.

   1. Find the vector $𝒚={𝑸}^T𝒃$

      ${\displaystyle 𝒚=\frac{1}{\sqrt{2}}\left[\begin{array}{lll}1& 0& 1\\ -1& 0& 1\end{array}\right]\left[\begin{array}{l}1\\ 1\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{l}2\\ 0\end{array}\right]}$

   2. Solve the system $𝑹𝒙=𝒚$

      ${\displaystyle 𝑹𝒙=\left[\begin{array}{ll}\sqrt{2}& 0\\ 0& \sqrt{2}\end{array}\right]𝒙=\frac{1}{\sqrt{2}}\left[\begin{array}{l}2\\ 0\end{array}\right]=𝒚}$

      Find

      ${\displaystyle 𝒙=\left[\begin{array}{l}1\\ 0\end{array}\right],𝒗=𝑨𝒙=\left[\begin{array}{ll}1& -1\\ 0& 0\\ 1& 1\end{array}\right]\left[\begin{array}{l}1\\ 0\end{array}\right]=\left[\begin{array}{l}1\\ 0\\ 1\end{array}\right]}$

   Computer solution (useful as verification). The above calculations can also be carried out in Matlab/Octave

   >>	A=[1 -1; 0 0; 1 1]; [Q,R]=qr(A,0)

   >>

   Q

   ${\displaystyle \left(\begin{array}{cc}-0.7071& 0.7071\\ 0.0& 0.0\\ -0.7071& -0.7071\end{array}\right)}$

   >>

   R

   ${\displaystyle \left(\begin{array}{cc}-1.4142& -3.3307e-16\\ 0.0& -1.4142\end{array}\right)}$

   >>

   Note that Matlab/Octave returned orthogonal vectors in the opposite orientation, highlighting that there are multiple ways to orthonormalize the columns of $𝑨$.

   In Matlab/Octave the least squares solution is returned by the backslash operator

   >>	b=[1; 1; 1]; x=A\b; disp(x)

   1

   0

   >>

2. Matrix $𝑨$ with linearly independent columns, $𝒃$ in the column space

   ${\displaystyle 𝑨=\left[\begin{array}{ll}{𝒂}_1& {𝒂}_2\end{array}\right]=\left[\begin{array}{ll}1& -1\\ 1& 0\\ 1& 1\end{array}\right],𝒃=\left[\begin{array}{l}2\\ 2\\ 2\end{array}\right].}$

   Solution. Note that $𝒃$ is a simple scaling of the first column of $𝑨$

   ${\displaystyle 𝒃=2{𝒂}_1=\left[\begin{array}{ll}{𝒂}_1& {𝒂}_2\end{array}\right]\left[\begin{array}{l}2\\ 0\end{array}\right]=𝑨𝒙\Rightarrow 𝒙=\left[\begin{array}{l}2\\ 0\end{array}\right].}$

   This example again highlights the need to first look at a problem before blindly carrying out calculations.

3. Matrix $𝑨$ with linearly independent columns, $𝒃$ not in the column space

   ${\displaystyle 𝑨=\left[\begin{array}{ll}{𝒂}_1& {𝒂}_2\end{array}\right]=\left[\begin{array}{ll}1& -1\\ 1& 2\\ 1& 1\end{array}\right],𝒃=\left[\begin{array}{l}1\\ 2\\ 1\end{array}\right].}$

   Solution. In this case the Gram-Schmidt algorithm is applied to find the $𝑸𝑹$ factorization of $𝑨$. Here are the GS steps:

   GS1. Find ${𝒒}_1$

   ${\displaystyle r_{11}=||{𝒂}_1||=\sqrt{3},{𝒒}_1=\frac{{𝒂}_1}{r_{11}}=\frac{1}{\sqrt{3}}\left[\begin{array}{l}1\\ 1\\ 1\end{array}\right]}$

   GS2. Find ${𝒒}_2$. This is carried out in two sub-steps:

   1. Subtract from ${𝒂}_2$ its component along the previously determined direction ${𝒒}_1$

      ${\displaystyle 𝒘={𝒂}_2-({𝒒}_1^T{𝒂}_2){𝒒}_1={𝒂}_2-r_{12}{𝒒}_1}$ ${\displaystyle r_{12}=\frac{1}{\sqrt{3}}\left[\begin{array}{lll}1& 1& 1\end{array}\right]\left[\begin{array}{l}-1\\ 2\\ 1\end{array}\right]=\frac{2}{\sqrt{3}}}$ ${\displaystyle 𝒘={𝒂}_2-r_{12}{𝒒}_1=\left[\begin{array}{l}-1\\ 2\\ 1\end{array}\right]-\frac{2}{3}\left[\begin{array}{l}1\\ 1\\ 1\end{array}\right]=\frac{1}{3}\left[\begin{array}{l}-5\\ 4\\ 1\end{array}\right].}$

      This vector is orthogonal to ${𝒒}_1$. Verify

      ${\displaystyle {𝒒}_1^T𝒘={𝒒}_1^T({𝒂}_2-r_{12}{𝒒}_1)=r_{12}-r_{12}{𝒒}_1^T{𝒒}_1=r_{12}-r_{12}\cdot 1=0}$ ${\displaystyle \frac{1}{\sqrt{3}}\left[\begin{array}{lll}1& 1& 1\end{array}\right]\frac{1}{3}\left[\begin{array}{l}-5\\ 4\\ 1\end{array}\right]=\frac{1}{3\sqrt{3}}(-5+4+1)=0}$

   2. Divide the resulting vector by its norm

      ${\displaystyle r_{22}=||𝒘||=\frac{\sqrt{42}}{3},{𝒒}_2=\frac{𝒘}{r_{22}}=\frac{1}{\sqrt{42}}\left[\begin{array}{l}-5\\ 4\\ 1\end{array}\right]}$

   Verify:

   ${\displaystyle 𝑸𝑹=\left[\begin{array}{ll}1/\sqrt{3}& -5/\sqrt{42}\\ 1/\sqrt{3}& 4/\sqrt{42}\\ 1/\sqrt{3}& 1/\sqrt{42}\end{array}\right]\left[\begin{array}{ll}\sqrt{3}& 2/\sqrt{3}\\ 0& \sqrt{42}/3\end{array}\right]=\left[\begin{array}{ll}1& -1\\ 1& 2\\ 1& 1\end{array}\right]=𝑨}$

   Here are the steps to solve the least squares problem.

   1. Find the vector $𝒚={𝑸}^T𝒃$

      ${\displaystyle 𝒚=\left[\begin{array}{lll}1/\sqrt{3}& 1/\sqrt{3}& 1/\sqrt{3}\\ -5/\sqrt{42}& 4/\sqrt{42}& 1/\sqrt{42}\end{array}\right]\left[\begin{array}{l}1\\ 2\\ 1\end{array}\right]=\left[\begin{array}{l}4/\sqrt{3}\\ 4/\sqrt{42}\end{array}\right]}$

   2. Solve the system $𝑹𝒙=𝒚$

      ${\displaystyle 𝑹𝒙=\left[\begin{array}{ll}\sqrt{3}& 2/\sqrt{3}\\ 0& \sqrt{42}/3\end{array}\right]𝒙=\left[\begin{array}{l}4/\sqrt{3}\\ 4/\sqrt{42}\end{array}\right]=𝒚}$

      Find

      ${\displaystyle 𝒙=\left[\begin{array}{l}24/21\\ 6/21\end{array}\right],𝒗=𝑨𝒙=\left[\begin{array}{ll}1& -1\\ 1& 2\\ 1& 1\end{array}\right]\left[\begin{array}{l}24/21\\ 6/21\end{array}\right]=\left[\begin{array}{l}6/7\\ 12/7\\ 10/7\end{array}\right]}$

   Computer solution (useful as verification). The above calculations can also be carried out in Matlab/Octave

   >>	A=[1 -1; 1 2; 1 1]; [Q,R]=qr(A,0)

   >>

   Q

   ${\displaystyle \left(\begin{array}{cc}-0.5774& 0.7715\\ -0.5774& -0.6172\\ -0.5774& -0.1543\end{array}\right)}$

   >>

   R

   ${\displaystyle \left(\begin{array}{cc}-1.7321& -1.1547\\ 0.0& -2.1602\end{array}\right)}$

   In Matlab/Octave the least squares solution is returned by the backslash operator

   >>	b=[1; 2; 1]; x=A\b; disp(x)

   1.1429

   0.2857

   >>	[24/21; 6/21]

   ${\displaystyle \left(\begin{array}{c}1.1429\\ 0.2857\end{array}\right)}$

   >>