Description
In this assignment, you will implement two simple versions of lossy image compression
— one based on PCA, and the other on K-means. Each question is worth 10 points.
PCA
Suppose you are given a dataset of samples each of which has
dimensions. We could compress this dataset by seeking a set of scalars
along with a single vector with dimensions. The approximation is that
N x ,⋯ , x ,
(1) (N) D
N a1,⋯ , aN
w D
x ≈
(n) anw.
Suppose we want the values an and w to minimize reconstruction error, i.e. we want
∥x − w
min
a
min N
1
n=1
∑
N
(n) anw∥ .
2
5/16/2021 6 Unsupervised Learning
https://www.notion.so/justindomke/6-Unsupervised-Learning-fbf3702c1bd44ea7b3ccc1570cb4b198 3/7
Let X be a matrix with x on the th row. (n) n
Question 1: Suppose that is fixed. What is the value of that minimizes
reconstruction error
w a
arg ∥x −
a
min
N
1
n=1
∑
N
(n) anw∥ ?
2
Show your work.
Question 2: Suppose is fixed. What is the reconstruction error if each is set to the
optimal value you found in the previous question, i.e.
w an
∥x − a
min N
1
n=1
∑
N
(n) anw∥ ?
2
Show your work.
Question 3: If you minimize the reconstruction error over both and , what is the
optimal ? Give your answer in terms of the matrix using eigenvalues and
eigenvectors. Show your work.
w a 4
w X
Hint: You might as well assume that since if this is not true, you could rescale
to make it true.
∥w∥ = 1
a
Hint: You might find it helpful to define the covariance matrix of the data,
.
C =
x x N
1 ∑n=1
N (n) (n)⊤
Question 4: Suppose that, in the training data, for all , ,
and finally . (Assume is even.)
n, x2 =
(n)
2 × x1
(n) x4 =
(n)
2 × x3
(n) ⋯ xD =
(n)
2 × xD−1
(n) D
5/16/2021 6 Unsupervised Learning
https://www.notion.so/justindomke/6-Unsupervised-Learning-fbf3702c1bd44ea7b3ccc1570cb4b198 4/7
Suppose you will project and reconstruct this data using a linear codebook, as
described in lecture. What is the minimum number of dimensions you will need in your
code such that the data can be reconstructed without error? Explain in at most 4
sentences.
2
Hint: Thinking about the cases where D = 2 or D = 4 might help.
Faces.zip 231.2KB
Question 5: You are given a set of 100 images of faces. Each is 50×50 and grayscale, and
so can be treated as a vector in R . The covariance matrix of the data is 2500
C = (x − N
1
n=1
∑
N
(n) xˉ)(x − ) ,
(n) xˉ
⊤
where Note that For each value of
, find the eigenvectors associated with the largest
eigenvalues of . Call these vectors . Project the data on to them, and call
the compressed representations . Note that and
xˉ = x . 2 N
1 ∑n=1
N (n) C ∈ R .
2500×2500 k ∈
{3, 5, 10, 30, 50, 100} k k
C w1 ,⋯ , wk
y ,⋯ , y
(1) (N) y ∈
(n) R
k
yj =
(n) w ⋅ j x .
(n)
You can approximately reconstruct x as (n)
5/16/2021 6 Unsupervised Learning
https://www.notion.so/justindomke/6-Unsupervised-Learning-fbf3702c1bd44ea7b3ccc1570cb4b198 5/7
3
x^ =
(n) y w .
j=1
∑
k
j
(n)
j
Show in your report the original face.png (download the image above) as well as the
reconstruction obtained for each value of .
1
k
For this question, you may use a package that computes eigenvalues and eigenvectors
(e.g. numpy.linalg.eigh ) but you may not use any package that computes PCA.
(Apologies for the confusion — YOU MAY USE SKLEARN’S PCA.) You may also not use
any external libraries for image processing except for numpy , sklearn , and
matplotlib .
1
Hint: PNG images can be loaded using matplotlib.mpimg :
import matplotlib.image as mpimg img = mpimg.imread(‘face.png’)
Question 6: Make a table showing the compression rate for each value of . The
compression rate is the amount of memory needed to store the compressed
representation ( and ) divided by the amount of memory
used to store the original data. Represent all data, including the original image, using a
64-bit float.
k 2
w1 ,⋯ , wk y ,⋯ , y
(1) (N)
K-Means
In the following questions, you will compress the following (single) image of width 393
and height 309:
5/16/2021 6 Unsupervised Learning
https://www.notion.so/justindomke/6-Unsupervised-Learning-fbf3702c1bd44ea7b3ccc1570cb4b198 6/7
1
For these questions, you are permitted to use sklearn for your implementation of kmeans.
Question 7: K-means is an algorithm that splits the data into clusters. There are various
different ways to choose the number of clusters. The “elbow” rule is a common
heuristic. Explain it in at most 4 sentences.
Question 8: Another issue with K-means is that the final results depend on initialization.
A possible solution to this problem is called K-means++. Briefly explain the idea behind
this algorithm.
Question 9: You are given above an image of a shopping street. If you break this up
into 3×3 chunks, there will be 13,493=131×103 total chunks. Since pixels are RBG, each
can be interpreted as a vector in . Transform the dataset into a set of 13493
elements of length 27. Next, for each , apply Kmeans clustering, so that each 3×3 chunk is represented by a single integer. Reconstruct
the original image from each compressed representation and show it. Show one
reconstructed image for each value of .
9
R
27
k ∈ {2, 5, 10, 25, 50, 100, 200, 1000}
k
Question 10: For each value of in the above question, compute the reconstruction
error, the mean squared difference in intensity, averaged over all pixels, and color
channels. Show your results as a table.
k 4
5/16/2021 6 Unsupervised Learning
https://www.notion.so/justindomke/6-Unsupervised-Learning-fbf3702c1bd44ea7b3ccc1570cb4b198 7/7
Question 11: How many total numbers are in your compressed representation for each
value of ? Give your answer as a table.
2
k
Question 12: For each value of compute the compression rate. Don’t worry about bits,
just assume that the original image uses 393x309x3 numbers and use your answer from
the previous question. Give your answer as a table.
k 1