Topic 4 Orthogonality and Least-Squares

The final section of the study document, focusing on Topic 4: Orthogonality and Least-Squares.

This topic covers the geometric aspects of linear algebra: dot products, orthogonal complements, the Gram-Schmidt process for creating orthogonal/orthonormal bases, matrix factorizations like QR, and using the Normal Equations to find Least-Squares solutions to inconsistent systems.

Question 1: Finding a Basis for an Orthogonal Complement ($W^{\perp }$)

Source: Exam 2, Question 11
Exact Question: Let $W=\text{Span}\{\left[\begin{array}{c}1\\ 3\\ 2\\ -1\end{array}\right],\left[\begin{array}{c}2\\ 6\\ 7\\ 1\end{array}\right]\}$. Find a basis for $W^{\perp }$.

Methodology:

1. Definition: The orthogonal complement $W^{\perp }$ is the set of all vectors that are orthogonal to every vector in $W$.
2. Logic: If a vector $\mathbf{x}$ is orthogonal to the spanning vectors of $W$, its dot product with each of them is zero. This is equivalent to saying $\mathbf{x}$ is in the null space of a matrix $A$ where the rows of $A$ are the spanning vectors of $W$ (because $A\mathbf{x}=\mathbf{0}$ computes exactly these dot products).
3. Process: Put the spanning vectors as rows in a matrix $A$. Row reduce to find the parametric vector form of $\text{Nul }A$. The basis vectors of the null space form the basis for $W^{\perp }$.

Solution:

• Step 1: Construct the matrix.$$A=\left[\begin{array}{cccc}1& 3& 2& -1\\ 2& 6& 7& 1\end{array}\right]$$
• Step 2: Row reduce to solve $A\mathbf{x}=\mathbf{0}$. $R_2\to R_2-2R_1$.$$\sim \left[\begin{array}{cccc}1& 3& 2& -1\\ 0& 0& 3& 3\end{array}\right]$$
• Step 3: Scale row 2 by $1/3$, then $R_1\to R_1-2R_2$.$$\sim \left[\begin{array}{cccc}1& 3& 2& -1\\ 0& 0& 1& 1\end{array}\right]\sim \left[\begin{array}{cccc}1& 3& 0& -3\\ 0& 0& 1& 1\end{array}\right]$$
• Step 4: Extract the solution. The pivots are $x_1$ and $x_3$. Free variables are $x_2$ and $x_4$.
  $x_3=-x_4$
  $x_1=-3x_2+3x_4$$$\mathbf{x}=\left[\begin{array}{c}-3x_2+3x_4\\ x_2\\ -x_4\\ x_4\end{array}\right]=x_2\left[\begin{array}{c}-3\\ 1\\ 0\\ 0\end{array}\right]+x_4\left[\begin{array}{c}3\\ 0\\ -1\\ 1\end{array}\right]$$Final Answer:$$\text{Basis for }{W}^{\perp }=\{\left[\begin{array}{c}-3\\ 1\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}3\\ 0\\ -1\\ 1\end{array}\right]\}$$

Question 2: The Gram-Schmidt Process (Orthonormal Basis)

Source: Practice Exam 4, Question 10
Exact Question: Find an orthonormal basis of the column space of the matrix $A=\left[\begin{array}{cccc}1& 0& 1& 3\\ 1& 1& 2& 5\\ 0& 1& 1& 2\end{array}\right]$.

Methodology:

1. Objective: Convert a set of arbitrary vectors (the columns of $A$) into a set of mutually orthogonal vectors of length 1 that span the same space.
2. Gram-Schmidt Formulas: Let the original columns be ${\mathbf{a}}_1,{\mathbf{a}}_2,\dots$ and the new orthogonal vectors be ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots$
   • ${\mathbf{v}}_1={\mathbf{a}}_1$
   • ${\mathbf{v}}_2={\mathbf{a}}_2-\frac{{\mathbf{a}}_2\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1$
   • ${\mathbf{v}}_3={\mathbf{a}}_3-\frac{{\mathbf{a}}_3\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1-\frac{{\mathbf{a}}_3\cdot {\mathbf{v}}_2}{{\mathbf{v}}_2\cdot {\mathbf{v}}_2}{\mathbf{v}}_2$
   • (Note: If any ${\mathbf{v}}_i$ evaluates to the zero vector $\mathbf{0}$, it means the original column ${\mathbf{a}}_i$ was a linear combination of previous columns. Discard the zero vector and move to the next column).
3. Normalization: After finding the orthogonal basis $\{{\mathbf{v}}_1,\dots \}$, divide each vector by its magnitude $\parallel {\mathbf{v}}_i\parallel =\sqrt{{\mathbf{v}}_i\cdot {\mathbf{v}}_i}$ to make it orthonormal.

Solution:

• Step 1: ${\mathbf{v}}_1={\mathbf{a}}_1=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]$.
• Step 2: Find ${\mathbf{v}}_2$.
  ${\mathbf{v}}_2=\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]-\frac{0(1)+1(1)+1(0)}{1^2+1^2+0^2}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]-\frac{1}{2}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}-1/2\\ 1/2\\ 1\end{array}\right]$.
• Step 3: Find ${\mathbf{v}}_3$.
  ${\mathbf{v}}_3={\mathbf{a}}_3-\frac{{\mathbf{a}}_3\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1-\frac{{\mathbf{a}}_3\cdot {\mathbf{v}}_2}{{\mathbf{v}}_2\cdot {\mathbf{v}}_2}{\mathbf{v}}_2$
  ${\mathbf{a}}_3\cdot {\mathbf{v}}_1=3$. ${\mathbf{v}}_1\cdot {\mathbf{v}}_1=2$.
  ${\mathbf{a}}_3\cdot {\mathbf{v}}_2=-1/2+1+1=3/2$. ${\mathbf{v}}_2\cdot {\mathbf{v}}_2=1/4+1/4+1=6/4=3/2$.
  ${\mathbf{v}}_3=\left[\begin{array}{c}1\\ 2\\ 1\end{array}\right]-\frac{3}{2}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]-\frac{3/2}{3/2}\left[\begin{array}{c}-1/2\\ 1/2\\ 1\end{array}\right]=\left[\begin{array}{c}1-3/2+1/2\\ 2-3/2-1/2\\ 1-0-1\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$.
  Because we get the zero vector, we discard ${\mathbf{a}}_3$.
• Step 4: Find ${\mathbf{v}}_4$ (using ${\mathbf{a}}_4$).
  Following the same math, ${\mathbf{v}}_4$ also results in the zero vector (discard it). The orthogonal basis is just $\{{\mathbf{v}}_1,{\mathbf{v}}_2\}$.
• Step 5: Normalize the vectors.
  $\parallel {\mathbf{v}}_1\parallel =\sqrt{2}$. $⟹{\mathbf{u}}_1=\left[\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\\ 0\end{array}\right]$.
  $\parallel {\mathbf{v}}_2\parallel =\sqrt{3/2}=\frac{\sqrt{6}}{2}$. $⟹{\mathbf{u}}_2=\frac{2}{\sqrt{6}}\left[\begin{array}{c}-1/2\\ 1/2\\ 1\end{array}\right]=\left[\begin{array}{c}-1/\sqrt{6}\\ 1/\sqrt{6}\\ \sqrt{2/3}\end{array}\right]$.
  Final Answer:$$\{\left[\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\\ 0\end{array}\right],\left[\begin{array}{c}-1/\sqrt{6}\\ 1/\sqrt{6}\\ \sqrt{2/3}\end{array}\right]\}$$

Question 3: QR Decomposition

Source: Practice Exam 3, Question 7
Exact Question: Let $A=\left[\begin{array}{cc}1& -2\\ 0& 1\\ -1& 4\end{array}\right]$. Find an QR decomposition of $A$.

Methodology:

1. Objective: Factor matrix $A$ into $QR$, where $Q$ has orthonormal columns (meaning $Q^{T}Q=I$) and $R$ is an upper triangular invertible matrix.
2. Process:
   • Apply the Gram-Schmidt process to the columns of $A$ to get an orthogonal basis $\{{\mathbf{v}}_1,{\mathbf{v}}_2\}$.
   • Normalize these vectors to get an orthonormal basis $\{{\mathbf{u}}_1,{\mathbf{u}}_2\}$. These form the columns of $Q$.
   • Compute $R$ using the formula $R=Q^{T}A$.

Solution:

• Step 1: Gram-Schmidt.
  ${\mathbf{v}}_1={\mathbf{a}}_1=\left[\begin{array}{c}1\\ 0\\ -1\end{array}\right]$.
  ${\mathbf{v}}_2={\mathbf{a}}_2-\frac{{\mathbf{a}}_2\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1=\left[\begin{array}{c}-2\\ 1\\ 4\end{array}\right]-\frac{(-2)(1)+(1)(0)+(4)(-1)}{1^2+0^2+(-1{)}^2}\left[\begin{array}{c}1\\ 0\\ -1\end{array}\right]=\left[\begin{array}{c}-2\\ 1\\ 4\end{array}\right]-\frac{-6}{2}\left[\begin{array}{c}1\\ 0\\ -1\end{array}\right]=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$.
• Step 2: Normalize to create $Q$.
  $\parallel {\mathbf{v}}_1\parallel =\sqrt{2}$. $⟹{\mathbf{u}}_1=\left[\begin{array}{c}1/\sqrt{2}\\ 0\\ -1/\sqrt{2}\end{array}\right]$.
  $\parallel {\mathbf{v}}_2\parallel =\sqrt{3}$. $⟹{\mathbf{u}}_2=\left[\begin{array}{c}1/\sqrt{3}\\ 1/\sqrt{3}\\ 1/\sqrt{3}\end{array}\right]$.$$Q=\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{3}\\ 0& 1/\sqrt{3}\\ -1/\sqrt{2}& 1/\sqrt{3}\end{array}\right]$$
• Step 3: Compute $R=Q^{T}A$.$$R=\left[\begin{array}{ccc}1/\sqrt{2}& 0& -1/\sqrt{2}\\ 1/\sqrt{3}& 1/\sqrt{3}& 1/\sqrt{3}\end{array}\right]\left[\begin{array}{cc}1& -2\\ 0& 1\\ -1& 4\end{array}\right]=\left[\begin{array}{cc}\sqrt{2}& -3\sqrt{2}\\ 0& \sqrt{3}\end{array}\right]$$(Note that $R$ is upper triangular as expected!)
  Final Answer:$$Q=\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{3}\\ 0& 1/\sqrt{3}\\ -1/\sqrt{2}& 1/\sqrt{3}\end{array}\right],R=\left[\begin{array}{cc}\sqrt{2}& -3\sqrt{2}\\ 0& \sqrt{3}\end{array}\right]$$

Question 4: Orthogonal Decomposition

Source: Practice Exam 4, Question 11
Exact Question: Let $\mathbf{y}=\left[\begin{array}{c}5\\ -15\\ 5\end{array}\right]$, ${\mathbf{b}}_1=\left[\begin{array}{c}0\\ -6\\ -8\end{array}\right]$, ${\mathbf{b}}_2=\left[\begin{array}{c}0\\ 2\\ 11\end{array}\right]$ and $W=\text{Span}\{{\mathbf{b}}_1,{\mathbf{b}}_2\}$. The vector $\mathbf{y}$ has an orthogonal decomposition $\mathbf{y}=\hat{\mathbf{y}}+\mathbf{z}$, where $\hat{\mathbf{y}}\in W$ and $\mathbf{z}\in W^{\perp }$. Compute $\mathbf{z}$.

Methodology:

1. Objective: Find $\mathbf{z}$, which is the component of $\mathbf{y}$ orthogonal to $W$. By definition, $\mathbf{z}=\mathbf{y}-\hat{\mathbf{y}}$, where $\hat{\mathbf{y}}$ is the projection of $\mathbf{y}$ onto $W$.
2. Crucial Check: The projection formula $\hat{\mathbf{y}}=\frac{\mathbf{y}\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1+\frac{\mathbf{y}\cdot {\mathbf{v}}_2}{{\mathbf{v}}_2\cdot {\mathbf{v}}_2}{\mathbf{v}}_2$ only works if the basis vectors are orthogonal. Check ${\mathbf{b}}_1\cdot {\mathbf{b}}_2=0-12-88\ne 0$. They are not orthogonal!
3. Process:
   • First, apply Gram-Schmidt to $\{{\mathbf{b}}_1,{\mathbf{b}}_2\}$ to find an orthogonal basis $\{{\mathbf{v}}_1,{\mathbf{v}}_2\}$ for $W$.
   • Compute $\hat{\mathbf{y}}$ using the projection formula with the new orthogonal basis.
   • Compute $\mathbf{z}=\mathbf{y}-\hat{\mathbf{y}}$.

Solution:

• Step 1: Gram-Schmidt on the basis.
  ${\mathbf{v}}_1={\mathbf{b}}_1=\left[\begin{array}{c}0\\ -6\\ -8\end{array}\right]$.
  ${\mathbf{v}}_2={\mathbf{b}}_2-\frac{{\mathbf{b}}_2\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1=\left[\begin{array}{c}0\\ 2\\ 11\end{array}\right]-\frac{-100}{100}\left[\begin{array}{c}0\\ -6\\ -8\end{array}\right]=\left[\begin{array}{c}0\\ 2\\ 11\end{array}\right]+\left[\begin{array}{c}0\\ -6\\ -8\end{array}\right]=\left[\begin{array}{c}0\\ -4\\ 3\end{array}\right]$.
• Step 2: Compute $\mathbf{z}$ directly (you can do $\mathbf{z}=\mathbf{y}-{\text{proj}}_W\mathbf{y}$).
  $\hat{\mathbf{y}}=\frac{\mathbf{y}\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1+\frac{\mathbf{y}\cdot {\mathbf{v}}_2}{{\mathbf{v}}_2\cdot {\mathbf{v}}_2}{\mathbf{v}}_2$
  $\mathbf{y}\cdot {\mathbf{v}}_1=(5)(0)+(-15)(-6)+(5)(-8)=0+90-40=50$.
  $\mathbf{y}\cdot {\mathbf{v}}_2=(5)(0)+(-15)(-4)+(5)(3)=0+60+15=75$.
  $\hat{\mathbf{y}}=\frac{50}{100}\left[\begin{array}{c}0\\ -6\\ -8\end{array}\right]+\frac{75}{25}\left[\begin{array}{c}0\\ -4\\ 3\end{array}\right]=\left[\begin{array}{c}0\\ -3\\ -4\end{array}\right]+\left[\begin{array}{c}0\\ -12\\ 9\end{array}\right]=\left[\begin{array}{c}0\\ -15\\ 5\end{array}\right]$.
• Step 3: Subtract.
  $\mathbf{z}=\mathbf{y}-\hat{\mathbf{y}}=\left[\begin{array}{c}5\\ -15\\ 5\end{array}\right]-\left[\begin{array}{c}0\\ -15\\ 5\end{array}\right]=\left[\begin{array}{c}5\\ 0\\ 0\end{array}\right]$.
  Final Answer:$$\mathbf{z}=\left[\begin{array}{c}5\\ 0\\ 0\end{array}\right]$$

Question 5: Least-Squares Curve Fitting & Normal Equations

Source: Exam 2, Question 6
Exact Question: Consider the points $(1,10)$, $(-1,-25)$, $(3,10)$ and $(2,10)$. Find the equation $y=a+bx$ of the best line (in the least-squares sense) that fits these points.

Methodology:

1. Objective: Find the coefficients $(a,b)$ that best satisfy an inconsistent system of linear equations derived from data points.
2. Setup the Design Matrix ($A$) and Observation Vector ($\mathbf{b}$):
   • For the equation $y=a+bx$, plug each $(x,y)$ data point in to get a row.
   • $10=a+b(1)$
   • $-25=a+b(-1)$
   • $10=a+b(3)$
   • $10=a+b(2)$
   • Write this as a matrix equation $A\mathbf{x}=\mathbf{b}$, where $\mathbf{x}=\left[\begin{array}{c}a\\ b\end{array}\right]$. The first column of $A$ is all 1s (coefficients of $a$), the second column is the $x$-values (coefficients of $b$). $\mathbf{b}$ holds the $y$-values.
3. Normal Equations: To find the least squares solution $\hat{\mathbf{x}}$, you must solve the consistent system: $A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$.

Solution:

• Step 1: Define matrices.$$A=\left[\begin{array}{cc}1& 1\\ 1& -1\\ 1& 3\\ 1& 2\end{array}\right],\mathbf{b}=\left[\begin{array}{c}10\\ -25\\ 10\\ 10\end{array}\right]$$
• Step 2: Compute $A^{T}A$.$$A^{T}A=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 3& 2\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& -1\\ 1& 3\\ 1& 2\end{array}\right]=\left[\begin{array}{cc}4& 5\\ 5& 15\end{array}\right]$$
• Step 3: Compute $A^T\mathbf{b}$.$$A^T\mathbf{b}=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 3& 2\end{array}\right]\left[\begin{array}{c}10\\ -25\\ 10\\ 10\end{array}\right]=\left[\begin{array}{c}10-25+10+10\\ 10+25+30+20\end{array}\right]=\left[\begin{array}{c}5\\ 85\end{array}\right]$$
• Step 4: Solve the Normal Equations $\left[\begin{array}{cc}4& 5\\ 5& 15\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}5\\ 85\end{array}\right]$.
  • You can row reduce the augmented matrix or use the inverse formula. Using the inverse:
  • $det(A^{T}A)=60-25=35$.
  • $\left[\begin{array}{c}a\\ b\end{array}\right]=\frac{1}{35}\left[\begin{array}{cc}15& -5\\ -5& 4\end{array}\right]\left[\begin{array}{c}5\\ 85\end{array}\right]=\frac{1}{35}\left[\begin{array}{c}75-425\\ -25+340\end{array}\right]=\frac{1}{35}\left[\begin{array}{c}-350\\ 315\end{array}\right]=\left[\begin{array}{c}-10\\ 9\end{array}\right]$.
• Step 5: Write the final equation.
  Final Answer: $y=-10+9x$

Additional Note: Generating Design Matrices for Complex Curves

Source: Practice Exam 3, Question 5
(Quick Methodology highlight)
If asked to fit a more complex curve like $y=\alpha x+\beta x^5$, the process for finding the design matrix $X$ is exactly the same as Step 1 above. The columns of $X$ map to the functions attached to your coefficients.

• Col 1: Evaluations of "$x$" for each data point.
• Col 2: Evaluations of "$x^5$" for each data point.
  You do not include a column of 1s unless the equation contains a standalone constant term (like $a$ in $y=a+bx$). The $y$-values always go into the observation vector $\mathbf{b}$, never into $X$.