13 Pre-Class Assignment: Projections
Contents
13 Pre-Class Assignment: Projections#
Readings for this topic (Recommended in bold)#
Goals for today’s pre-class assignment#
1. Orthogonal and Orthonormal#
Definition: A set of vectors is said to be orthogonal if every pair of vectors in the set is orthogonal (the dot product is 0). The set is orthonormal if it is orthogonal and each vector is a unit vector (norm equals 1).
Result: An orthogonal set of nonzero vectors is linearly independent.
Definition: A basis that is an orthogonal set is called an orthogonal basis. A basis that is an orthonormal set is called an orthonormal basis.
Result: Let \(\{u_1,\dots,u_n\}\) be an orthonormal basis for a vector space \(V\). Then for any vector \(v\) in \(V\), we have $\(v=(v\cdot u_1)u_1+(v\cdot u_2)u_2 +\dots + (v\cdot u_n)u_n\)$
✅ DO THIS: Let’s think why the above result is true. Since \(\{u_1,\dots,u_n\}\) is a basis, we can express \(v\) as a linear combination of the form $\(v=a_1u_1 + \dots a_nu_n.\)\( Now, take the dot product of \)v\( with \)u_i\(, what is the result? (Hint: Use the fact that the basis is orthonormal and show \)v\cdot u_i =a_i$). Explain why and explain why the above formula is correct.
Put your answer to the above question here
Definition: A square matrix is orthogonal if \(A^{-1}=A^\top\).
Result: Let \(A\) be a square matrix. The following three statements are equivalent.
(a) \(A\) is orthogonal.
(b) The column vectors of \(A\) form an orthonormal set.
(c) The row vectors of \(A\) form an orthonormal set.
(d) \(A^{-1}\) is orthogonal.
(e) \(A^\top\) is orthogonal.
Result: If \(A\) is an orthogonal matrix, then we have \(|A|=\pm 1\).
Consider the following vectors \(u_1, u_2\), and \(u_3\) that form a basis for \(\mathbb R^3\).
✅ DO THIS: Show that the vectors \(u_1\), \(u_2\), and \(u_3\) are linearly independent (HINT: see the pre-class 12-Change_Basis):
Put your answer to the above here
✅ QUESTION 1: How do you show that \(u_1\), \(u_2\), and \(u_3\) are orthogonal?
Put your answer to the above question here
✅ QUESTION 2: How do you show that \(u_1\), \(u_2\), and \(u_3\) are normal vectors?
Put your answer to the above question here
✅ DO THIS: Express the vector \(v = (7,5,-1)\) as a linear combination of the \(u_1\), \(u_2\), and \(u_3\) basis vectors:
# Put your answer here
2. Orthogonal Projections#
from IPython.display import YouTubeVideo
YouTubeVideo("5B8XluiqdHM",width=640,height=360, cc_load_policy=True)
The (orthogonal) projection of the vector \(v\) onto the vector \(u\) is given by $\(\mbox{proj}_u v = \frac{v \cdot u}{u \cdot u} u.\)$
✅ QUESTION 3: How does the above formula simplify if the vector \(u\) is normal (has lenght 1)?
Put your answer here
✅ QUESTION 4: Calculate the projection of the vector \(v=(2,5)\) onto \(u=(3,4)\).
Put your answer here
Projection of a Vector onto a Subspace#
Think of a projection onto a subspace is analogous to a shadow on a surface. Aspects of an objects 3D space is represented in a 2D shadow but you can’t take the shadow by itself and exactly recreate the 3D surface.
Image from https://commons.wikimedia.org
The following is the matimatical defination of projection onto a subspace.
Definition: Let \(W\) be a subspace of \(R^n\) of dimension \(m\). Let \(\{w_1,\cdots,w_m\}\) be an orthonormal basis for \(W\). Then the projection of vector \(v\) in \(R^n\) onto \(W\) is denoted as \(\mbox{proj}_Wv\) and is defined as $\(\mbox{proj}_Wv = (v\cdot w_1)w_1+(v\cdot w_2)w_2+\cdots+(v\cdot w_m)w_m\)$
Another way to say the above defination is that the project of \(v\) onto the \(W\) is just the sumation of \(v\) projected onto each vector in a basis of \(W\)
Remarks:
In the Gram-Schmidt algorithm below, we will use projection for \(m>1\).
The projection does not depend on which orthonormal basis you choose.
If \(v\) is in \(W\), we have \(\mbox{proj}_Wv=v\).
✅ QUESTION 5: If the vector \(v\) is orthogonal to the subspace \(S\), what is \(\mbox{proj}_S v\)? If \(v\) is a vector in \(S\), what is \(\mbox{proj}_S v\)?
Put your answer here
✅ QUESTION 6: If \(v\) is a vector in \(S\), what is \(\mbox{proj}_S v\)?
Put your answer here
3. Code Review#
In the next in-class assignment, we are going to avoid some of the more advanced libraries ((i.e. no numpy or scipy or sympy) to try to get a better understanding about what is going on in the math.
The following code implements some common linear algebra functions:
#Standard Python Libraries only
import math
import copy
def dot(u,v):
'''Calculate the dot product between vectors u and v'''
if len(u) != len(v):
print("ERROR - dimensions not equal")
else:
temp = 0;
for i in range(len(u)):
temp += u[i]*v[i]
return temp
✅ DO THIS: Write a quick test to compare the output of the above dot function with the numpy dot function.
# Put your test code here
def multiply(m1,m2):
'''Calculate the matrix multiplication between m1 and m2 represented as list-of-list.'''
n = len(m1)
d = len(m2)
m = len(m2[0])
if len(m1[0]) != d:
print("ERROR - inner dimensions not equal")
else:
#make zero matrix
result = [[0 for j in range(m)] for i in range(n)]
#print(result)
for i in range(0,n):
for j in range(0,m):
for k in range(0,d):
#print(i,j,k)
#print('result', result[i][j])
#print('m1', m1[i][k])
#print('m2', m2[k][j])
result[i][j] = result[i][j] + m1[i][k] * m2[k][j]
return result
✅ DO THIS: Write a quick test to compare the output of the above multiply function with the numpy multiply function.
# Put your test code here
Here is a mathematical definition of the big-O notation: https://en.wikipedia.org/wiki/Big_O_notation
and here is a computer science perspective of the big-O notation:
from IPython.display import YouTubeVideo
YouTubeVideo("v4cd1O4zkGw",width=640,height=360, cc_load_policy=True)
✅ QUESTION: What is the big-O complexity of the above multiply function?
Put your answer to the above question here.
✅ QUESTION: Line 11 in the provided multiply code initializes a matrix of the size of the output matrix as a list of lists with zeros. What is the big-O complexity of line 11?
Put your answer to the above question here.
def norm(u):
'''Calculate the norm of vector u'''
nm = 0
for i in range(len(u)):
nm += u[i]*u[i]
return math.sqrt(nm)
✅ DO THIS: Write a quick test to compare the outputs of the above norm function with the numpy norm function.
#Put your test code here
def transpose(A):
'''Calculate the transpose of matrix A represented as list of lists'''
n = len(A)
m = len(A[0])
AT = list()
for j in range(0,m):
temp = list()
for i in range(0,n):
temp.append(A[i][j])
AT.append(temp)
return AT
✅ DO THIS: Write a quick test to compare the output of the above transpose function with the numpy transpose function.
# Put your test code here
✅ QUESTION: What is the big-O complexity of the above transpose function?
Put your answer to the above question here
✅ QUESTION: Explain any differences in results between the provided functions and their numpy counterparts.
Put your answer to the above question here
4. Gram-Schmidt#
Watch this video for the indroduction of Gram-Schmidt, which we will implement in class.
from IPython.display import YouTubeVideo
YouTubeVideo("rHonltF77zI",width=640,height=360, cc_load_policy=True)
Written by Dr. Dirk Colbry, Michigan State University
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
###STARTFOOTER###