EE445 Midterm DUE 2022-04-30 8:00AM PST
You are *not* allowed to work with your peers. Show all work and derivations to receive credit.
Write clearly and legibly for your own benefit.
Name :
SID :
Attention!!: You will have to upload the final Python
notebook to Canvas in the midterm exam assignment
to get credit in addition to attaching a print out pdf to
the exam you submit!
1
EE445 Midterm DUE 2022-04-30 8:00AM PST
Problem 1 (Linear Independence, Matrices) [6pts].
Consider three vectors u, v, w ∈ R3 that are linearly independent, and let a, b, c ∈ R3 be defined as
a = u+ v, b = v + w, c = u+ w, d = u− v.
a. Suppose vectors u and v have unit length. What is the angle between the vectors a and d?
b. Again suppose vectors u and v have unit length. Give an expression for a left-inverse of the
matrix A =
[
a d
]
(your expression can depend on a and d).
c. Show that nullspace of the matrix B =
[
a b c
]
contains only the zero vector 0 ∈ R3.
Solution.
2
EE445 Midterm DUE 2022-04-30 8:00AM PST
Problem 2 (Matrix inverse & properties) [6pts]. Consider the following n× n matrix,
S =

1 0 . . . 0 0
1 1 . . . 0 0
...
...
. . .
...
...
1 1 . . . 1 0
1 1 . . . 1 1

What does the matrix S do when applied to a vector? Find the inverse of S: Solve SX = I for the
unknown matrix X by writing the linear equations each column of X should satisfy. What is the
interpretation of S−1?
3
EE445 Midterm DUE 2022-04-30 8:00AM PST
Problem 3 (Least Squares Placement) [18pts]. This problem has parts a–e. We have provided
space below each problem for the solution.
The vectors p1, . . . , pN , each in R2 represent the locations of N objects. There are two types of
objects: factories and warehouses. The first K objects are factories, whose locations are fixed and
given. Our goal in the placement problem to choose the locations of the last N −K objects i.e the
warehouses.
Our choice of the locations is guided by an undirected graph; an edge between two objects means
we would like them to be close to each other. In least squares placement, we choose the locations
pK+1, . . . , pN of warehouses so as to minimize the sum of the squares of the distances between
objects connected by an edge, where the L edges of the graph are given by the set E. For a specific
location of factories p1, . . . , pK , we can frame our task as solving the following optimization:
g(p1, . . . pK) = min
pK+1,...pN
∑
(i,j)∈E
∥pi − pj∥2
For illustration, see the figure below. The factories are denoted by red squares, and warehouses by
blue circles; we want to move the blue circles so that the objective is minimized.
a. In each of the simplified cases below, state what the optimal objective value would be. Further,
what assignment to {pK+1, . . . pN} would achieve this optimal objective? If there are multiple
optimal assignments, state any one.
i. The factories are fixed at pN−K+1 = · · · = pN−1 = pN = 0.
ii. There is K = 1 factory. Write your answer in terms of the fixed location p1.
iii. All edges are from one warehouse to another. In other words, for any (i, j) ∈ E, both
(pi, pj) are warehouses. Write your answer in terms of E.
Solution part a.
4
EE445 Midterm DUE 2022-04-30 8:00AM PST
5
EE445 Midterm DUE 2022-04-30 8:00AM PST
b. Now, we move towards solving the problem in the more general case.
Let D be the Dirichlet energy of the graph, which is defined as follows (more details are given
in §7.3 of VMLS, and specifically page 135; you may want to take a look):
Consider a graph G = ({1, . . . , N}, E) composed of a set of edges E and N nodes
{1, . . . , N} such that nodes i, j ∈ {1, . . . , N} are connected if and only if there
exists an edge (i, j) ∈ E. Let B be the incidence matrix of the graph, and let
w ∈ RN be the potential for the graph—i.e., wi is the value of some quantity
at node i ∈ {1, . . . , N}. The Dirichlet energy is D(w) = ∥B⊤w∥2 and can be
equivalently expressed as
D(v) =
∑
(i,j)∈E
(wj − wj)2
which is the sum of the squares of the potential differences of w across all edges in
the graph.
Show that the sum of the squared distances between theN factories can be expressed asD(u)+
D(v), where u = ((p1)1 , . . . , (pN )1) and v = ((p1)2 , . . . , (pN )2) are N -vectors containing the
first and second coordinates of the factories, respectively.
Solution part b.
6
EE445 Midterm DUE 2022-04-30 8:00AM PST
c. Express the least squares placement problem as a least squares problem, with variable x =(
u1:(N−K), v1:(N−K)
)
. In other words, express the objective above (the sum of squares of the
distances across edges) as ∥Ax− b∥2, for an appropriate m×n matrix A and m-vector b. You
will find that m = 2L.
Hint: You can use the fact that D(y) = ∥∥B⊤y∥∥2, where B is the incidence matrix of the
graph.
Solution part c.
7
EE445 Midterm DUE 2022-04-30 8:00AM PST
d. Solve the least squares placement problem for the specific problem with N = 10, K = 5, L =
13, fixed locations
p1 = (0.55, 0.15), p2 = (0, 0), p3 = (0, 1), p4 = (1, 1), p5 = (1, 0),
The edges are:
(1, 6), (2, 6), (5, 6), (1, 7), (4, 7), (2, 8),
(3, 8), (3, 9), (5, 9), (5, 10), (7, 9), (6, 10), (7, 10).
Using the provided Python notebook, plot the locations, showing the graph edges as lines
connecting the locations. Specifically, solve Python-P3d in the provided notebook and print
the pdf and attach it at the end of your exam. You will have to upload the final
notebook to Canvas to get credit in addition to attaching a print out pdf to the
exam you submit!
8
EE445 Midterm DUE 2022-04-30 8:00AM PST
Problem 4 (Recursive Least Squares) [12pts]. Suppose we have data (x(1), . . . , x(m)) and (y(1), . . . , y(m))
and we believe that y(i) ≈ (x(i))⊤θ—that is, y(i) is approximately a linear function of x(i). The
x(i) ∈ Rn are n-dimensional vectors and y(i) ∈ R are scalars. The least squares method seeks to
minimize
J(θ) =
m∑
k=1
(y(k) − (x(k))⊤θ)2
We saw in lecture that
θˆm :=
(
m∑
k=1
x(k)(x(k))⊤
)−1 m∑
k=1
x(k)y(k)
minimizes J(θ). There are three parts to the problem and on the next page put your solutions to
parts a and b. For part c, print your pdf and attach it at the end of your exam. You will also need
to provide the ipynb of your solutions.
a. Define X⊤m = [x(1) x(2) · · · x(m)] and Ym = [y(1) y(2) · · · y(m)]⊤. Show that
θˆm := (X
⊤
mXm)
−1X⊤mYm
minimizes ∥Ym −Xmθ∥2 by taking the derivative of ∥Ym −Xmθ∥2 and setting it to zero.
b. Now suppose one more data pair (x(m+1), y(m+1)) becomes available and define
X⊤m+1 = [X
⊤
m x
(m+1)] and Ym = [Y
⊤
m y
(m+1)]⊤
Hence, the new least squares solution is
θˆm+1 := (X
⊤
m+1Xm+1)
−1X⊤m+1Ym+1 = R
−1
m+1
m+1∑
k=1
x(k)y(k) (1)
where
Rm+1 :=
m+1∑
k=1
x(k)(x(k))⊤.
Show that the least squares solution can be obtained by the following recursive procedure:
θˆm+1 = θˆm +R
−1
m+1x
(m+1)(y(m+1) − (x(m+1))⊤θˆm) (2)
Rm+1 = Rm + x
(m+1)(x(m+1))⊤ (3)
That is, show that these equations hold given the definition of Rm and the expression for the
least squares solution.
Hint: First, verify (3) holds given the definition of Rm+1. Then, to verify (2), take the ex-
pression in (1) for θˆm+1, and expand the sum
∑m+1
k=1 x
(k)y(k) = x(m+1)y(m+1)+
∑m
k=1 x
(k)y(k).
Now, use (3) and the expression you have for θˆm to show (2) holds.
c. Implement recursive least squares. In the provided Python notebook, solve Python-P4. You
will have to upload the final notebook to Canvas to get credit in addition to
attaching a print out pdf to the exam you submit!
9
EE445 Midterm DUE 2022-04-30 8:00AM PST
Solution.
a. Provide your solution to part a. here.
10
EE445 Midterm DUE 2022-04-30 8:00AM PST
b. Provide your solution to part b. here.
11
EE445 Midterm DUE 2022-04-30 8:00AM PST
Problem 5 (Least Norm Solution) [6pts]. In class we saw how to obtain the least squares ap-
proximate solution to Ax = b corresponding to an over-determined set of equations—that is, where
A ∈ Rm×n with m > n (“tall matrix”). In this case, there is rarely an exact solution to Ax = b,
and instead we find an approximate solution by minimizing ∥Ax− b∥2.
If on the other hand A is a “wide matrix”, meaning n > m, then the set of equations is under-
determined. This means there are more unknowns than equations and hence, potentially many
solutions. In this case we select, amongst the solutions, the one with the smallest norm—i.e., the
least norm solution. That is, we seek xˆ such that Axˆ = b and ∥xˆ∥ ≤ ∥x∥ for all other x such that
Ax = b.
Consider an under-determined system of equations Ax = b where b ∈ Rn and A ∈ Rm×n are given
with n > m. Suppose that A is full rank and b ∈ range(A)—this ensures there is at least one
solution. Show that xˆ = A⊤(AA⊤)−1b is the least norm solution to Ax = b. In particular, letting
S = {x ∈ Rn| Ax = b} be the set of solutions to Ax = b, you need to show that
∥xˆ∥ ≤ ∥x∥ ∀ x ∈ S.
Solution.
12