Description
1. Let A =
3 3 3 −1 −1 −1
1 1 1 −3 −3 −3
1 1 1 −3 −3 −3
3 3 3 −1 −1 −1
. Use the provided script to help you complete
the problem.
a) Understand the code for implementing the k-means algorithm and fill in the blank
to define the distance function used by k-means.
b) Use the k-means algorithm to represent the columns of A with a single cluster.
c) Construct a matrix Abr=1 whose i-th column is the centroid corresponding to the
i-th column of A .
Note that this can be viewed as a rank-1 approximation to A.
Compare the rank-1 approximation to the original matrix and explain the nature
of the approximation in terms of the properties of the k-means algorithm
d) Repeat (b) and (c) with k = 2.
Compare the rank-2 approximation to the original
matrix and explain the nature of the approximation in terms of the properties of
the k-means algorithm.
2. Again let A =
3 3 3 −1 −1 −1
1 1 1 −3 −3 −3
1 1 1 −3 −3 −3
3 3 3 −1 −1 −1
. Now consider the singular value decomposition (SVD) A = USV T
.
a) If the full SVD is computed, find the dimensions of U,S, and V .
b) Find the dimensions of U,S, and V in the economy or skinny SVD of A.
c) The Python and NumPy command U,s,VT = np.linalg.svd(A,full matrices=True)
computes the singular value decomposition, A = USV T where U and V are matrices with orthonormal columns comprising the left and right singular vectors and
S is a diagonal matrix of singular values. Use this command to find the SVD of
A.
i. Compute the SVD of A and make sure that A = UΣV
T
.
ii. Find UT U and V
TV . Are the columns of U and V orthonormal? Why?
Hint: compute UT U.
1 of 2
iii. Find UUT and V V T
. Are the rows of U and V orthonormal? Why?
iv. Find the left and right singular vectors associated with the largest singular
value.
v. What is the rank of A?
d) The commandU,s,VT = np.linalg.svd(A,full matrices=False) computes the
economy or skinny singular value decomposition, A = USV T where U and V are
matrices with orthonormal columns comprising the left and right singular vectors
and S is a square diagonal matrix of singular values. Find the economy SVD of
A.
i. Find UT U and V
TV . Are the columns of U and V orthonormal? Why?
ii. Find UUT and V V T
. Are the rows of U and V orthonormal? Why?
e) Compare the singular vectors and singular values of the economy and full SVD.
How do they differ?
f) Identify an orthonormal basis for the space spanned by the columns of A.
g) Identify an orthonormal basis for the space spanned by the rows of A.
h) Define the rank-r approximation to A as
Ar =
Xr
i=1
σiuiv
T
i
where σi
is the ith singular value with left singular vector ui and right singular
vector vi
.
i. Find the rank-1 approximation A1. How does A1 compare to A?
ii. Find the rank-2 approximation A2. How does A2 compare to A?
i) The economy SVD is based on the dimension of the matrices and does not consider
the rank of the matrix.
What is the smallest economy SVD (minimum dimension
of the square matrix S) possible for the matrix A? Find U,S, and V for this
minimal economy SVD.
2 of 2
