Problem sets COMS 3251 Fall 2022
9 Singular value decomposition
Problem 9.1. Let P ∈ R4×4 denote the elementary projector to the line
span({z}) along the hyperplane NS(wT), where z = w = (1, 1, 1, 1). Find
singular value decompositions of the following matrices. That is, for each of
the following matrices, write left singular vectors u1, . . . ,ur, right singular
vectors v1, . . . ,vr, and singular values σ1, . . . , σr, where r is the rank of the
matrix; use an ordering of the vectors and values so that σ1 ≥ · · · ≥ σr.
(a) P (an elementary projector)
(b) I − P (complement to an elementary projector)
(c) I − 2P (an elementary reflector)
You might find the following ONB for R4 helpful:

+1/2
+1/2
+1/2
+1/2
 ,

+1/2
−1/2
+1/2
−1/2
 ,

+1/2
+1/2
−1/2
−1/2
 ,

+1/2
−1/2
−1/2
+1/2

.
Problem 9.2. Let P denote the orthogonal projection operator for
W = span



+1
+1
+1
+1
+1
+1
+1
+1

,

+1
−1
+1
−1
+1
−1
+1
−1

,

+1
+1
−1
−1
+1
+1
−1
−1

,

+1
−1
−1
+1
+1
−1
−1
+1

,

−1
−1
−1
−1
−1
−1
−1
−1



,
which is a subspace of R8.
(a) Compute the value of tr(P ), and explain how you obtained your answer.
(b) Write the singular values of P , and explain how you obtained your
answer.
1
Problem sets COMS 3251 Fall 2022
Problem 9.3. Suppose A is an m × n matrix, Q is an m × m orthogonal
matrix (i.e., the columns of Q form an ONB for Rm), and R is an n × n
orthogonal matrix.
(a) Prove that (QA)+ = A+QT.
(b) Prove that (AR)+ = RTA+.
Problem 9.4. Color images can be represented by collection of matrices, one
per “color channel”, with the (i, j)-th entry in one such matrix specifying the
intensity of the corresponding color at the (i, j)-th pixel. A m×n pixel image
with three color channels is therefore generally represented by 3mn numbers.
If each matrix is replaced by its rank k SVD approximation, the image can
be (implicitly) represented by 3(m+ n)k numbers. So there is some “space”
savings to be had by using the approximations as long as k < mn/(m+ n).
Get the Jupyter notebook compressed image.ipynb from Courseworks
and implement the function compressed image. This function takes as input
a positive integer k, as well as a m × n pixel image, which is represented
as three m × n matrices R,G,B ∈ [0, 1]m×n, one for each color channel. It
should return an implicit representation of a new image: again, three matrices
Rˆ, Gˆ, Bˆ ∈ Rm×n, one per color channel, but each of Rˆ, Gˆ, Bˆ is implicitly
specified by the product of an m×k matrix and a k×n matrix. The Jupyter
notebook has code that shows how this function will be used. The numpy
functions numpy.linalg.svd and numpy.diag may be useful.
Please include in your write-up:
(a) your source code for compressed image (a screenshot is fine);
(b) the 4 images from the notebook corresponding to the rank 8, 16, 32,
and 64 approximations of the original image (screenshots are fine).
Problem 9.5. Suppose you are given all pairwise distances betweenm points
in an n-dimensional Euclidean space (e.g., n = 2). Let’s say these are given
in a matrix D ∈ Rm×m such that Di,j is the squared distance between the
ith and jth points. (Of course, having the squared distances is just as good
as having the distances themselves.) Is it possible to recover the original
coordinates of the m points from D?
The answer is no, for a couple of reasons.
2
Problem sets COMS 3251 Fall 2022
• If a displacement vector o ∈ Rn is added to every point, then the coor-
dinates of the points could change, but the pairwise distances between
points would not change.
• If all of the points are linearly transformed by an n × n orthogonal
matrix Q, then the coordinates of the points could change, but the
pairwise distances between points would not change.
It turns out that these are the only reasons: any two equal size sets of points in
a Euclidean space realizing the same pairwise (squared) distances are related
by these two so-called “rigid” transformations.
Suppose our goal, then, is instead to simply find an m×n matrix B with
rows bT1, . . . ,b
T
m such that
∥bi − bj∥2 = Di,j for all i, j ∈ {1, . . . ,m}. (Goal)
In first two parts below, assume that there exists a “ground truth” matrix A
with rows aT1, . . . , a
T
m such that ∥ai − aj∥2 = Di,j for all i, j ∈ {1, . . . ,m}.
(a) Suppose the ai’s are centered, i.e.,
∑m
i=1 ai = 0. Prove that the column
space of A is contained in the orthogonal complement of span({1m})
(in Rm), where 1m is the all-ones vector in Rm.
Hint: The orthogonal projection operator for span({1m})⊥ is
P = I − 1
m
1m1
T
m.
(b) Let v = (v1, . . . , vm) ∈ Rm be the vector of squared lengths of the ai’s,
i.e., vi = ∥ai∥2 for each i ∈ {1, . . . ,m}. Convince yourself that
D = v1T − 2AAT + 1vT.
Define
M = −1
2
PDP T (MDS)
(where P is as defined above). Prove that if the ai’s are centered, then
M = AAT.
3
Problem sets COMS 3251 Fall 2022
(c) Prove that if a matrix B satisfies BBT = M (where M is as defined in
(MDS)), then B satisfies (Goal).
Hint: First, write a formula for the (i, j)th entry of M in terms of the
entries of D. Then write a formula for ∥bi−bj∥2 in terms of the entries
of M ; use the first formula to eventually get everything in terms of
entries of D; it should simplify to Di,j. (Your proof may just show the
steps of this derivation.)
(d) It turns out that if M = UΣV T is a compact SVD of M (as defined
in (MDS)), and D really is the matrix of squared distances between
points, then
B = U
√
Σ
satisfies (Goal), where
√
Σ is the diagonal matrix whose entries are the
(non-negative) square roots of that of the diagonal matrix Σ. (This
uses the fact that M is positive semidefinite, which implies U = V in
a compact SVD.) Note that B will be an m× r matrix, where r is the
rank of M .
This overall procedure (going from D to B) is called multidimensional
scaling (MDS). However, in real implementations of MDS, one may find
that the rank of the matrix M is higher than expected, or even find
that the matrix M is not positive semidefinite!3 This might be due to
numerical rounding errors; or it could be that the “squared distances” in
D did not actually come from squared Euclidean distances (but instead
were just some other arbitrary matrix of numbers). So, instead, real
implementations of MDS use a rank k truncated SVD of M (instead of
the SVD itself), where k is a given “target” dimension (e.g., k = 2)4:
letting σ1 ≥ σ2 ≥ · · · be the singular values of M and u1,u2, . . . be the
corresponding left singular vectors of M , we use
B =
[√
σ1u1 · · · √σkuk
]
.
Get the Jupyter notebook mds.ipynb from Courseworks and implement
(the rank k version of) MDS as the function mds. The Jupyter notebook
3For example, you obtain pairwise distance measurements between 33 buildings in a mostly flat region of
NYC, but the matrix M has rank much higher than 2.
4This is not entirely accurate, but good enough for this problem.
4
Problem sets COMS 3251 Fall 2022
has code that shows how this function will be used. The numpy functions
numpy.linalg.svd and numpy.diag may be useful.
Please include in your write-up:
(a) your source code for mds;
(b) the resulting plot of the points from the notebook from applying
mds to the given pairwise distances (which correspond to a certain
collection of buildings . . . ).
(Screenshots are fine in both cases.)