Example Problems

Calculation

Given a basis B={b⃗1,b⃗2,…,b⃗n}\mathcal{B} = \{\vec{b}_1, \vec{b}_2, \ldots, \vec{b}_n\}, which spans a subspace VV, we want to find an orthogonal basis U={u⃗1,u⃗2,…,u⃗n}\mathcal{U} = \{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\} that also spans VV.

  1. Base case: We let u⃗1=b⃗1\vec{u}_1 = \vec{b}_1. If VV is a one-dimensional subspace, then we are done.

  2. Iterative case: We take each vector from B\mathcal{B} one by one and project it onto the existing orthogonal basis vectors. For b⃗2\vec{b}_2, since we only have u⃗1=b⃗1\vec{u}_1 = \vec{b}_1 in our orthonormal basis, we only do one projection.

    projUb⃗2=b⃗2⋅u⃗1u1⃗⋅u⃗1u⃗1\text{proj}_U \vec{b}_2 = \frac{\vec{b}_2 \cdot \vec{u}_1}{\vec{u_1} \cdot \vec{u}_1}\vec{u}_1

    We know that the error vector will be orthogonal to our existing orthogonal basis, so we subtract the projection from the b⃗\vec{b} vector.

    u⃗2=b⃗2−projUb⃗2=b⃗2−b⃗2⋅u⃗1u1⃗⋅u⃗1u⃗1\vec{u}_2 = \vec{b}_2 - \text{proj}_U \vec{b}_2 = \vec{b}_2 - \frac{\vec{b}_2 \cdot \vec{u}_1}{\vec{u_1} \cdot \vec{u}_1}\vec{u}_1

    For each successive b⃗\vec{b} vector, we repeat this algorithm. Therefore, u⃗3=b⃗3−projUb⃗3=b⃗3−b⃗3⋅u⃗1u1⃗⋅u⃗1u⃗1−b⃗3⋅u⃗2u⃗2⋅u⃗2u⃗2\vec{u}_3 = \vec{b}_3 - \text{proj}_U \vec{b}_3 = \vec{b}_3 - \frac{\vec{b}_3 \cdot \vec{u}_1}{\vec{u_1} \cdot \vec{u}_1}\vec{u}_1 - \frac{\vec{b}_3 \cdot \vec{u}_2}{\vec{u}_2 \cdot \vec{u}_2}\vec{u}_2

    ⋮\vdots

    u⃗n=b⃗n−projUb⃗n=b⃗n−b⃗n⋅u⃗1u1⃗⋅u⃗1u⃗1−⋯−b⃗n⋅u⃗n−1u⃗n−1⋅u⃗n−1u⃗n−1\vec{u}_n = \vec{b}_n - \text{proj}_U \vec{b}_n = \vec{b}_n - \frac{\vec{b}_n \cdot \vec{u}_1}{\vec{u_1} \cdot \vec{u}_1}\vec{u}_1 - \cdots - \frac{\vec{b}_n \cdot \vec{u}_{n - 1}}{\vec{u}_{n - 1} \cdot \vec{u}_{n - 1}}\vec{u}_{n - 1}

Notes: 1. Gram-Schmidt turns a set of vectors into an orthogonal basis. Since basis vectors have to be linearly independent, Gram-Schmidt will return some 0⃗\vec{0} if the set of vectors contains linearly dependent vectors. Intuitively, since the linearly dependent vector is already in the subspace, it is equal to its projection, so the error vector is 0⃗\vec{0}. 2. Order matters. You will get a different basis depending on the order of the b⃗\vec{b} vectors in which you perform Gram-Schmidt.

Example

Find an orthonormal basis for B={[11],[21]}\mathcal{B} = \left\{\begin{bmatrix}1 \\ 1\end{bmatrix}, \begin{bmatrix}2 \\ 1\end{bmatrix}\right\}.

Let U={u⃗1,u⃗2}\mathcal{U} = \{\vec{u}_1, \vec{u}_2\} be the orthogonal basis. Then, u⃗1=b⃗1=[11]\vec{u}_1 = \vec{b}_1 = \begin{bmatrix}1 \\ 1\end{bmatrix}.

u⃗2=b⃗2−b⃗2⋅u⃗1u⃗1⋅u⃗1u⃗1=[21]−[21]⋅[11][11]⋅[11][11]=[21]−32[11]=[12−12]\vec{u}_2 = \vec{b}_2 - \frac{\vec{b}_2 \cdot \vec{u}_1}{\vec{u}_1 \cdot \vec{u}_1}\vec{u}_1 = \begin{bmatrix}2 \\ 1\end{bmatrix} - \frac{\begin{bmatrix}2 \\ 1\end{bmatrix} \cdot \begin{bmatrix}1 \\ 1\end{bmatrix}}{\begin{bmatrix}1 \\ 1\end{bmatrix} \cdot \begin{bmatrix}1 \\ 1\end{bmatrix}}\begin{bmatrix}1 \\ 1\end{bmatrix} = \begin{bmatrix}2 \\ 1\end{bmatrix} - \frac{3}{2}\begin{bmatrix}1 \\ 1\end{bmatrix} = \begin{bmatrix}\frac{1}{2} \\ -\frac{1}{2}\end{bmatrix}

Sanity check:

u⃗1⋅u⃗2=[11]⋅[12−12]=0\vec{u}_1 \cdot \vec{u}_2 = \begin{bmatrix}1 \\ 1\end{bmatrix} \cdot \begin{bmatrix}\frac{1}{2} \\ -\frac{1}{2}\end{bmatrix} = 0

U={[11],[12−12]}\mathcal{U} = \left\{\begin{bmatrix}1 \\ 1\end{bmatrix}, \begin{bmatrix}\frac{1}{2} \\ -\frac{1}{2}\end{bmatrix}\right\}

However, the question asks for an orthonormal basis, so we just normalize each of these vectors to get our orthonormal basis:

{[2222],[22−22]}\left\{\begin{bmatrix}\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2}\end{bmatrix}, \begin{bmatrix}\frac{\sqrt{2}}{2} \\ -\frac{\sqrt{2}}{2}\end{bmatrix}\right\}

System of Equations in Orthogonal Bases

Assume that U={u⃗1,u⃗2,…,u⃗n}\mathcal{U} = \{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\} is an orthogonal basis for the vector space VV. For another vector y⃗∈V\vec{y} \in V, we want to express y⃗\vec{y} as a linear combination of the orthogonal basis vectors and solve y⃗=c1u⃗1+c2u⃗2+⋯+cnu⃗n\vec{y} = c_1\vec{u}_1 + c_2\vec{u}_2 + \cdots + c_n\vec{u}_n.

If we dot both sides with u⃗i,1≤i≤n\vec{u}_i, 1 \leq i \leq n, then we get

y⃗⋅u⃗i=c1u⃗1⋅u⃗i+c2u⃗2⋅u⃗i+⋯+cnu⃗n⋅u⃗i\vec{y} \cdot \vec{u}_i = c_1\vec{u}_1 \cdot \vec{u}_i + c_2\vec{u}_2 \cdot \vec{u}_i + \cdots + c_n\vec{u}_n \cdot \vec{u}_i.

However, remember that since U\mathcal{U} is an orthonormal basis, u⃗j⋅u⃗k=0\vec{u}_j \cdot \vec{u}_k = 0 if j≠kj \neq k. Therefore, the above equation becomes

y⃗⋅u⃗i=ciu⃗i⋅u⃗i\vec{y} \cdot \vec{u}_i = c_i\vec{u}_i \cdot \vec{u}_i

Solving for the coefficient cic_i,

ci=y⃗⋅u⃗iu⃗i⋅u⃗ic_i = \frac{\vec{y} \cdot \vec{u}_i}{\vec{u}_i \cdot \vec{u}_i}

Therefore, in cases of orthogonal bases, we only need to find the projections of the vector y⃗\vec{y} onto each basis vector.

QR Factorization

What and why

QR Factorization is basically using Gram-Schmidt to find an orthonormal basis spanning the column space of a matrix A\textbf{A} and re-writing the Gram-Schmidt process in matrix form. QR Factorization produces an orthogonal matrix Q\textbf{Q} (remember that an orthogonal matrix has orthonormal columns) and an upper triangular matrix R\textbf{R}, where A=QR\textbf{A} = \textbf{Q}\textbf{R}.

Calculation

The most straighforward way to calculate Q\textbf{Q} and R\textbf{R} is to first calculate Q\textbf{Q} using Gram-Schmidt and then normalizing the result. To find R\textbf{R}, we can use the property that Q\textbf{Q} is orthonormal, i.e. Q−1=QT\textbf{Q}^{-1} = \textbf{Q}^T.

A=QR\textbf{A} = \textbf{Q}\textbf{R}

QTA=QTQR\textbf{Q}^T\textbf{A} = \textbf{Q}^T\textbf{Q}\textbf{R}

R=QTA\textbf{R} = \textbf{Q}^T\textbf{A}

The other way (which will not be discussed here) is to use the Gram-Schmidt equations and re-writing them in matrix form. When we then normalize the columns Q\textbf{Q} (i.e. divide by the lengths of each vector), we multiply the corresponding row in R\textbf{R} by the lengths of the q⃗\vec{q} vectors.

Example

Using the example from above, where A=[1211]\textbf{A} = \begin{bmatrix}1 & 2 \\ 1 & 1\end{bmatrix}, we know that Q=[222222−22]\textbf{Q} = \begin{bmatrix}\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2}\end{bmatrix}.

To find R\textbf{R},

R=QTA=[222222−22][1211]=[2322022]\textbf{R} = \textbf{Q}^T\textbf{A} = \begin{bmatrix}\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2}\end{bmatrix}\begin{bmatrix}1 & 2 \\ 1 & 1\end{bmatrix} = \begin{bmatrix}\sqrt{2} & \frac{3\sqrt{2}}{2} \\ 0 & \frac{\sqrt{2}}{2}\end{bmatrix}

Note that R\textbf{R} is upper triangular. Check for yourself that A=QR\textbf{A} = \textbf{Q}\textbf{R}.

Least Squares using QR Factorization

QR Factorization is helpful when solving doing least squares ATAx⃗=ATb⃗\textbf{A}^T\textbf{A}\vec{x} = \textbf{A}^T\vec{b} because if we can factorize A=QR\textbf{A} = \textbf{Q}\textbf{R}, we can take advantage of the property that Q\textbf{Q} is orthonormal and that R\textbf{R} is invertible (and easy to invert because it's upper triangular).

ATAx⃗=ATb⃗\textbf{A}^T\textbf{A}\vec{x} = \textbf{A}^T\vec{b}

(QR)TQRx⃗=(QR)Tb⃗(\textbf{Q}\textbf{R})^T\textbf{Q}\textbf{R}\vec{x} = (\textbf{Q}\textbf{R})^T\vec{b}

RTQTQRx⃗=RTQTb⃗\textbf{R}^T\textbf{Q}^T\textbf{Q}\textbf{R}\vec{x} = \textbf{R}^T\textbf{Q}^T\vec{b}

RTRx⃗=RTQTb⃗\textbf{R}^T\textbf{R}\vec{x} = \textbf{R}^T\textbf{Q}^T\vec{b}

Rx⃗=QTb⃗\textbf{R}\vec{x} = \textbf{Q}^T\vec{b}

x⃗=R−1QTb⃗\vec{x} = \textbf{R}^{-1}\textbf{Q}^T\vec{b}

PreviousDescriptionNextBasis

Last updated