CS/ECE/ME532 Assignment 3
1. Polynomial fitting. Suppose we observe pairs of points (ai
, bi), i = 1, . . . , m representing
measurements from a scientific experiment. The variables ai are the experimental
conditions and the bi correspond to the measured response in each condition. We fit a
degree p < m polynomial to these data. In other words, we want to find the coefficients
of a degree p polynomial w(a) so that w(ai) ≈ bi
for i = 1, 2, . . . , m.
a) Suppose w(a) is a degree p polynomial. Write the general expression for w(ai) =
bi
.
b) Express the i = 1, . . . , m equations as a system in matrix form Ax = d while
defining A and d. What is the form/structure of A in terms of the given ai?
c) Write a script to find the least-squares model fit to the m = 30 data points in
polydata.mat. Plot the points and the polynomial fits for p = 1, 2, 3.
2. Least Squares Approximation of Matrices.
a) Derive the solution to least-squares problem minw kx − T wk
2
2 when T is an nby-r matrix of orthonormal columns. Your solution should not involve a matrix
inverse.
b) Let X =
x1 x2 · · · xp
be an n-by-p matrix. Use the least-squares problems minwi
kxi − T wik
2
2
to find W =
w1 w2 · · · wp
in the approximation
X ≈ TW. Your solution should express W as a function of T and X.
3. We return to the movies rating problem of Activity 5. The ratings on a scale of 1-10
are:
Movie Jake Jennifer Jada Theo Ioan Bo Juanita
Star Trek 4 7 2 8 7 4 2
Pride and Prejudice 9 3 5 6 10 5 5
The Martian 4 8 3 7 6 4 1
Sense and Sensibility 9 2 6 5 9 5 4
Star Wars: Empire Strikes 4 9 2 8 7 4 1
A matrix X containing this data is available in the file movie.mat and the csv file
movie.csv. Our goal is to approximate X using r “tastes”, the columns of T , that
1 of 3
is, X ≈ TW where T is 5-by-r. You will use a Gram-Schmidt orthogonalization
code to find a set of tastes that approximate the ratings. A script that implements
Gram-Schmidt orthogonalization is available.
Define a 5-by-r taste matrix T =
t1 t2 · · · tr
with orthonormal columns and
the r-by-7 weight matrix
W =
w11 w12 · · · w17
w21 w22 · · · w27
.
.
.
wr1 wr2 · · · wr7
a) In Activity 5 you found the baseline (average) rating for each friend by requiring
the first basis vector in the taste matrix to be
You have noticed by now that the first vector in the Gram-Schmidt procedure
is a scaled version of the first vector of the matrix, so you decide to define an
augmented matrix X˜ =
1 X
where 1 is a column vector containing five
unity entries. Apply a Gram-Schmidt orthogonalization code to X˜ to find a set
of orthonormal basis vectors. Is the first basis vector you obtain equal to t1?
b) Use your solution to the preceding problem in this homework assignment to find
the rank-1 approximation of X using only t1. That is, find W so that X ≈ t1W.
Use W to compute t1W. This gives you each friend’s baseline ratings. Also
compute the residual error X − t1W.
c) Now find a rank-2 approximation using T =
t1 t2
. That is, find W so that
X ≈ TW. Use W to compute TW. This gives you a rank-2 approximation to
the ratings. Also compute the residual error X −TW. How does t2 relate to the
distinction between sci-fi and and romance movie preferences?
d) Now find a rank-3 approximation using T =
t1 t2 t3
. That is, find W so
that X ≈ TW. Use W to compute TW. This gives you a rank-3 approximation
to the ratings. Also compute the residual error X − TW. Qualitatively discuss
the effect of increasing the rank of the approximation on the residual error.
e) Suppose you interchange the order of Jake and Jennifer so that Jennifer’s ratings
are in the first column of X and Jake’s ratings are in the second column. Does the
2 of 3
rank-2 approximation change? Why or why not? Does the rank-3 approximation
change? Why or why not?
4. Let Q =
"
1 0
0 2 #
.
a) Is Q 0?
b) Sketch the surface y = x
TQx where x =
"
x1
x2
#
. If you find 3-D sketching too
difficult, you may draw a contour map with labeled contours.
5. Suppose P 0 and Q 0 are (symmetric) positive definite n × n matrices. Prove
that QPQ 0.
3 of 3