## 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