Gram-Schmidt Orthogonalization and Projection

from sympy import *

Gram-Schmidt Procedure

Suppose we have a subspace $\mathbb{S}$ of ${\mathbb{R}}^n$ whose basis consists of $k$ vectors ${\overrightarrow{v}}_1,{\overrightarrow{v}}_2,\dots ,{\overrightarrow{v}}_k$.

$$\mathbb{S}=\mathrm{span}\{{\overrightarrow{v}}_1,{\overrightarrow{v}}_2,\dots ,{\overrightarrow{v}}_k\}.$$

The Gram-Schmidt procedure computes from this basis a new basis for $\mathbb{S}$ that is orthonormal (that is, the vectors of of unit length and mutually orthogonal). That is,

$$\mathrm{gram}\mathrm{\_}\mathrm{schmidt}\left(\{{\overrightarrow{v}}_1,{\overrightarrow{v}}_2,\dots ,{\overrightarrow{v}}_k\}\right)\to \{{\overrightarrow{w}}_1,{\overrightarrow{w}}_2,\dots ,{\overrightarrow{w}}_k\}$$

where

• $|{\overrightarrow{w}}_i|=1$, for all $i$,
• ${\overrightarrow{w}}_i\cdot {\overrightarrow{w}}_j=0$ for all $i\ne j$.

The procedure usually constructs the vectors by, setting ${\overrightarrow{w}}_1={\overrightarrow{v}}_1/|{\overrightarrow{v}}_1|$, and then recursively building the rest of the vectors by

$${\overrightarrow{w}}_j={\mathrm{perp}}_{\mathrm{span}\{{\overrightarrow{w}}_1,\dots ,{\overrightarrow{w}}_{j-1}\}}({\overrightarrow{v}}_j),1<j\le k.$$

It follows that, for each $1\le i\le k$

$$\mathrm{span}\{{\overrightarrow{v}}_1,{\overrightarrow{v}}_2\dots ,{\overrightarrow{v}}_i\}=\mathrm{span}\{{\overrightarrow{w}}_1,{\overrightarrow{w}}_2\dots ,{\overrightarrow{w}}_i\}$$

There is a nice Gram-Schmidt orthogonalizer which will take a list of vectors and orthogonalize them with respect to another. The vectors in the list must be linearly independent. There is an optional argument which specifies whether or not the output should also be normalized, it defaults to False.

Example

Use the Gram-Schmidt procedure on the set

$$\{\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-1\\ 2\\ 1\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]\}$$

A = [Matrix([1, 1, 0]), Matrix([-1, 2, 1]), Matrix([0, 1, 1])]
pprint(GramSchmidt(A))

$[\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-3/2\\ 3/2\\ 1\end{array}\right],\left[\begin{array}{c}2/11\\ -2/11\\ 6/11\end{array}\right]]$

Use optional argument True to have a normalized basis returned.

A = [Matrix([1, 1, 0]), Matrix([-1, 2, 1]), Matrix([0, 1, 1])]
pprint(GramSchmidt(A, True))

$[\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ 0\end{array}\right],\left[\begin{array}{c}\frac{-3}{\sqrt{22}}\\ \frac{3}{\sqrt{22}}\\ \frac{2}{\sqrt{22}}\end{array}\right],\left[\begin{array}{c}\frac{1}{\sqrt{11}}\\ \frac{-1}{\sqrt{11}}\\ \frac{3}{\sqrt{11}}\end{array}\right]]$

If we have a matrix of column vectors we wish to orthogonalize, first extract them to a list.

A = Matrix([[1, 1, 0], [-1, 2, 1], [0, 1, 1]]).T
vectorList = [A.col(i) for i in range(A.shape[1])]
GramSchmidt(vectorList)

Note: we can check that the vectors returned by GramSchmidt are orthonormal. This would mean that the matrix of these vectors must be orthogonal. Recall, a matrix $Q$ is orthogonal if $Q^{T}Q=I$.

A = [Matrix([1, 1, 0]), Matrix([-1, 2, 1]), Matrix([0, 1, 1])]
L = GramSchmidt(A,True)
B = L[0]
for col in L[1:]:
    B = B.row_join(col)
B.T*B  

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

Example

Use the Gram-Schmidt procedure on the set

$$\{\left[\begin{array}{c}1\\ 1\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}2\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]\}$$

Note: the third vector is in the span of the first two. Since GramSchmidt requires the list of vectors to be linearly independent we'll use rref to extract the linearly independent columns.

A = Matrix([[1, 1, 0, 1],[1, 0, 1, 1],[2, 1, 1, 2],[1, 0, 0, 1]]).T
A

$\left[\begin{array}{cccc}1& 1& 2& 1\\ 1& 0& 1& 0\\ 0& 1& 1& 0\\ 1& 1& 2& 1\end{array}\right]$

pivots = A.rref()[1]
L = []
for i in pivots:
    L.append(A[:,i])
pprint(L)

$[\left[\begin{array}{c}1\\ 1\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]]$

Now we have a list of linearly independent vectors from the original list. We can apply GramSchmidt to this list.

pprint(GramSchmidt(L)) # (1)

1. use optional second argument True to return a set of normalize vectors

$[\left[\begin{array}{c}1\\ 1\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}1/3\\ -2/3\\ 1\\ 1/3\end{array}\right],\left[\begin{array}{c}1/5\\ -2/5\\ -2/5\\ 1/5\end{array}\right]]$

Gram-Schmidt via QR Decomposition

The Gram-Schmidt can be found hidden in the SymPy's QR decomposition. We'll cover a number of matrix decompositions methods in the next section, but for now we note that QR decomposition is a factorization of the form

$$A=QR$$

where $Q$ is orthogonal (i.e. columns are orthonormal), and $R$ is upper triangular. This means that column $i$ of $A$ is a linear combination of the first $i$ columns of $Q$. Column $i$ of $R$ tells us exactly what this linear combination is. This is true for each column $i$.

The function sympy.QRdecomposition returns the two matrices $Q$ and $R$ associated with matrix $A$.

Let's redo the two examples above.

Example

Use sympy.QRdecomposition to find the Gram-Schmidt basis for the set

$$\{\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-1\\ 2\\ 1\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]\}$$

First form a column matrix, then return the matrix $Q$ from QR decomposition.

A = Matrix([[1, 1, 0],[-1, 2, 1],[0, 1, 1]]).T
Q, R = A.QRdecomposition()
Q

$\left[\begin{array}{ccc}\frac{\sqrt{2}}{2}& -\frac{3\sqrt{22}}{22}& \frac{\sqrt{11}}{11}\\ \frac{\sqrt{2}}{2}& \frac{3\sqrt{22}}{22}& -\frac{\sqrt{11}}{11}\\ 0& \frac{\sqrt{22}}{11}& \frac{3\sqrt{11}}{11}\end{array}\right]$

This is the same collection of orthonormal vectors we found above (up to scaling by $-1$).

Here is the example we looked at above, where the original set of vectors is linearly dependent.

Example

Use sympy.QRdecomposition to find the Gram-Schmidt basis for the set

$$\{\left[\begin{array}{c}1\\ 1\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}2\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]\}$$

First form a column matrix, then return the matrix $Q$ from QR decomposition.

A = Matrix([[1, 1, 0, 1],[1, 0, 1, 1],[2, 1, 1, 2],[1, 0, 0, 1]]).T
Q, R = A.QRdecomposition()
Q

$\left[\begin{array}{ccc}\frac{\sqrt{3}}{3}& \frac{\sqrt{15}}{15}& \frac{\sqrt{10}}{10}\\ \frac{\sqrt{3}}{3}& -\frac{2\sqrt{15}}{15}& -\frac{\sqrt{10}}{5}\\ 0& \frac{\sqrt{15}}{5}& -\frac{\sqrt{10}}{5}\\ \frac{\sqrt{3}}{3}& \frac{\sqrt{15}}{15}& \frac{\sqrt{10}}{10}\end{array}\right]$

This is the same collection of vectors we found above, they are just normalized here..

Projection onto a Subspace

Suppose we have an orthogonal basis $\{{\overrightarrow{w}}_1,{\overrightarrow{w}}_2,\dots ,{\overrightarrow{w}}_k\}$ for a subspace $\mathbb{S}$. The the projection of a vector $\overrightarrow{v}$ onto $\mathbb{S}$ is given by:

$${\mathrm{proj}}_{\mathbb{S}}(\overrightarrow{v})=\frac{\overrightarrow{v}\cdot {\overrightarrow{w}}_1}{{\overrightarrow{w}}_1\cdot {\overrightarrow{w}}_1}{\overrightarrow{w}}_1+\frac{\overrightarrow{v}\cdot {\overrightarrow{w}}_2}{{\overrightarrow{w}}_2\cdot {\overrightarrow{w}}_2}{\overrightarrow{w}}_2+\cdots +\frac{\overrightarrow{v}\cdot {\overrightarrow{w}}_k}{{\overrightarrow{w}}_k\cdot {\overrightarrow{w}}_k}{\overrightarrow{w}}_k$$

This is used in the Gram-Schmidt procedure. Here we just implement the projection and perpendicular as functions in python so we can use them as needed.

Projection onto a Subspace

def proj(v, A):
    '''input : v is a vector, and A is a matrix whose
               column vectors are form an orthogonal basis.
       output: the projection of v onto the subspace spanned
               columns of A.'''
    num_rows = A.shape[0]
    num_cols = A.shape[1]
    w = zeros(num_rows)
    for i in range(num_cols):
        coli = A[:,i]
        w += (v.dot(coli)/coli.dot(coli))*coli
    return w

def perp(v,A):
    '''input : v is a vector, and A is a matrix whose
               column vectors are form an orthogonal basis.
       output: the perpendicular of the projection of v onto
               the subspace spanned columns of A.'''
    return v - proj(v,A)

Example

Let $\mathbb{S}=\mathrm{span}\{\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right]\}$ and let $\overrightarrow{x}=\left[\begin{array}{c}2\\ 5\\ -7\\ 3\end{array}\right]$. Determine ${\mathrm{proj}}_{\mathbb{S}}(\overrightarrow{x})$ and ${\mathrm{perp}}_{\mathbb{S}}(\overrightarrow{x})$.

Note: Basis is already orthogonal, so we can project directly onto it.

A = Matrix([[1.,1,1,1],[1,-1,1,-1]]).T
v = Matrix([2,5,-7,3])
print('projection of v onto columnspace of A: ')
pprint(proj(v,A))
print('perpendicular of v onto columnspace of A: ')
pprint(perp(v,A))

$\text{projection of v onto columnspace of A:}$

$\left[\begin{array}{c}-2.5\\ 4\\ -2.5\\ 4\end{array}\right]$

$\text{perpendicular of v onto columnspace of A:}$

$\left[\begin{array}{c}4.5\\ 1\\ -4.5\\ -1\end{array}\right]$

In the next example, we use the Gram-Schmidt procedure to first find an orthogonal basis for the subspace, then we project the vector onto this.

Example

Project $\overrightarrow{v}=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$ onto the space with basis:

$${\overrightarrow{v}}_1=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],{\overrightarrow{v}}_2=\left[\begin{array}{c}-1\\ 2\\ 1\end{array}\right]$$

The first thing to do would be to find an orthogonal basis, we could use Gram-Schmidt to do this (see above), but here we didn't normalize:

$${\overrightarrow{w}}_1=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],{\overrightarrow{w}}_2=\left[\begin{array}{c}-3\\ 3\\ 2\end{array}\right]$$

Then projecting $\overrightarrow{x}$ onto this basis we get

$${\mathrm{proj}}_{\mathbb{S}}(\overrightarrow{v})=\frac{\overrightarrow{v}\cdot {\overrightarrow{w}}_1}{{\overrightarrow{w}}_1\cdot {\overrightarrow{w}}_1}{\overrightarrow{w}}_1+\frac{\overrightarrow{v}\cdot {\overrightarrow{w}}_2}{{\overrightarrow{w}}_2\cdot {\overrightarrow{w}}_2}{\overrightarrow{w}}_2$$

$$=\left[\begin{array}{c}2/2-6/22\\ 2/2+6/22\\ 2/11\end{array}\right]=\left[\begin{array}{c}8/11\\ 14/11\\ 2/11\end{array}\right]$$

Also,

$${\mathrm{perp}}_{\mathbb{S}}(\overrightarrow{v})=\overrightarrow{v}-{\mathrm{proj}}_{\mathbb{S}}(\overrightarrow{v})=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]-\left[\begin{array}{c}8/11\\ 14/11\\ 2/11\end{array}\right]=\left[\begin{array}{c}3/11\\ -3/11\\ 9/11\end{array}\right]$$

Let's check this in python:

v1 = Matrix([1,1,0])
v2 = Matrix([-1,2,1])
A = [v1,v2]
Q = GramSchmidt(A)
pprint(Q)

$[\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-3/2\\ 3/2\\ 1\end{array}\right]]$

Q = Matrix(Q).reshape(2,3).T
Q

$\left[\begin{array}{cc}1& -3/2\\ 1& 3/2\\ 0& 1\end{array}\right]$

v = Matrix([1,1,1])
print('projection of v onto columnspace of Q:')
pprint(proj(v,Q))

$\text{projection of v onto columnspace of Q:}$

$\left[\begin{array}{c}8/11\\ 14/11\\ 2/11\end{array}\right]$

print('perpendicular of v onto columnspace of Q:')
pprint(perp(v,Q))

$\text{perpendicular of v onto columnspace of Q:}$

$\left[\begin{array}{c}3/11\\ -3/11\\ 9/11\end{array}\right]$