studEE16A
  • Introduction
  • Linear Algebra
    • Linear Equations
      • Description
      • Example Problems
    • Vector Spaces
      • Description
      • Example Problems
    • Inner Products
      • Description
      • Example Problems
    • Determinants
      • Description
      • Example Problems
    • Eigen-everything
      • Description
      • Example Problems
    • Matrices
      • Description
      • Example Problems
    • Least Squares
      • Description
      • Example Problems
    • Gram-Schmidt
      • Description
      • Example Problems
    • Basis
      • Description
      • Example Problems
    • Page Rank
  • Circuits
    • Circuit Basics
    • Capacitance
    • Nodal Analysis
    • Superposition
    • Thevenin and Norton
    • What, When, Where, and Why?
    • Op Amps
Powered by GitBook
On this page
  • Calculation
  • Example
  • System of Equations in Orthogonal Bases
  • QR Factorization
  • Calculation
  • Example
  • Least Squares using QR Factorization

Was this helpful?

  1. Linear Algebra
  2. Gram-Schmidt

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\}B={b1​,b2​,…,bn​}, which spans a subspace VVV, 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\}U={u1​,u2​,…,un​} that also spans VVV.

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

  2. Iterative case: We take each vector from B\mathcal{B}B one by one and project it onto the existing orthogonal basis vectors. For b⃗2\vec{b}_2b2​, since we only have u⃗1=b⃗1\vec{u}_1 = \vec{b}_1u1​=b1​ 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}_1projU​b2​=u1​​⋅u1​b2​⋅u1​​u1​

    We know that the error vector will be orthogonal to our existing orthogonal basis, so we subtract the projection from the b⃗\vec{b}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}_1u2​=b2​−projU​b2​=b2​−u1​​⋅u1​b2​⋅u1​​u1​

    For each successive b⃗\vec{b}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}_2u3​=b3​−projU​b3​=b3​−u1​​⋅u1​b3​⋅u1​​u1​−u2​⋅u2​b3​⋅u2​​u2​

    ⋮\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}un​=bn​−projU​bn​=bn​−u1​​⋅u1​bn​⋅u1​​u1​−⋯−un−1​⋅un−1​bn​⋅un−1​​un−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}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}0. 2. Order matters. You will get a different basis depending on the order of the b⃗\vec{b}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\}B={[11​],[21​]}.

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

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}u2​=b2​−u1​⋅u1​b2​⋅u1​​u1​=[21​]−[11​]⋅[11​][21​]⋅[11​]​[11​]=[21​]−23​[11​]=[21​−21​​]

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} = 0u1​⋅u2​=[11​]⋅[21​−21​​]=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\}U={[11​],[21​−21​​]}

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\}{[22​​22​​​],[22​​−22​​​]}

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\}U={u1​,u2​,…,un​} is an orthogonal basis for the vector space VVV. For another vector y⃗∈V\vec{y} \in Vy​∈V, we want to express y⃗\vec{y}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}_ny​=c1​u1​+c2​u2​+⋯+cn​un​.

If we dot both sides with u⃗i,1≤i≤n\vec{u}_i, 1 \leq i \leq nui​,1≤i≤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}_iy​⋅ui​=c1​u1​⋅ui​+c2​u2​⋅ui​+⋯+cn​un​⋅ui​.

However, remember that since U\mathcal{U}U is an orthonormal basis, u⃗j⋅u⃗k=0\vec{u}_j \cdot \vec{u}_k = 0uj​⋅uk​=0 if j≠kj \neq kj=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}_iy​⋅ui​=ci​ui​⋅ui​

Solving for the coefficient cic_ici​,

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

Therefore, in cases of orthogonal bases, we only need to find the projections of the vector y⃗\vec{y}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}A and re-writing the Gram-Schmidt process in matrix form. QR Factorization produces an orthogonal matrix Q\textbf{Q}Q (remember that an orthogonal matrix has orthonormal columns) and an upper triangular matrix R\textbf{R}R, where A=QR\textbf{A} = \textbf{Q}\textbf{R}A=QR.

Calculation

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

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

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

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

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}Q (i.e. divide by the lengths of each vector), we multiply the corresponding row in R\textbf{R}R by the lengths of the q⃗\vec{q}q​ vectors.

Example

Using the example from above, where A=[1211]\textbf{A} = \begin{bmatrix}1 & 2 \\ 1 & 1\end{bmatrix}A=[11​21​], 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}Q=[22​​22​​​22​​−22​​​].

To find R\textbf{R}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}R=QTA=[22​​22​​​22​​−22​​​][11​21​]=[2​0​232​​22​​​]

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

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}ATAx=ATb because if we can factorize A=QR\textbf{A} = \textbf{Q}\textbf{R}A=QR, we can take advantage of the property that Q\textbf{Q}Q is orthonormal and that R\textbf{R}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}ATAx=ATb

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

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

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

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

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

PreviousDescriptionNextBasis

Last updated 5 years ago

Was this helpful?