Description
THEORY
Problem 4.1 (Quadratic constraints)
OptM Problem 4.2.
Problem 4.2 (Practice computing SVDs)
Compute by hand the singular value decomposition of
A =
”
3 2 2
2 3 −2
#
.
In other words, express A as A = UΣ˜V
T where U ∈ R
2,2 and V ∈ R
3,3 are orthogonal matrices
and Σ˜ ∈ R
2,3
, specify the values of
(a) Specify the singular values by specifying Σ. ˜
(b) Specify the right singular vectors by specifying V .
(c) Specify the left singular vectors by specifying U.
(d) Reassemble your calculations of parts (a)-(c) to show that UΣ˜V
T
in fact does equal the A
you started with. Also express A as a sum of rank-one matrices where each matrix is the
outer product of a left singular vector and a right singular value scaled by a singular value.
Problem 4.3 (SVD of an orthogonal matrix)
OptM Problem 5.1.
APPLICATION
Problem 4.4 (Latent semantic indexing)
In this problem you build off the problem “Angles between word vectors” from PS01, making a
connection to the singular value decomposition. First complete the following two parts of OptM
problem 5.5:
(a) OptM problem 5.5 part 3.
(b) OptM problem 5.5 part 4.
In the following parts we connect OptM problem 5.5 to the “Angles between word vectors” (ABWV)
problem in PS01, and apply the latent semantic indexing method to the Wikipedia article collection.
We start by briefly re-describing the ABWV problem set-up below, but please feel free to go back
and read the original problem statement.
ECE367 Problem Sets
In ABWV, we considered a set of documents D the where the number of documents is |D|. The
set W denotes the union of words in all articles, i.e., the lexicon of the set of documents where the
cardinality of W is |W|. We assume the lexicon is ordered “lexiographically” (e.g., alphabetically)
so that there is a one-to-one mapping from each word w ∈ W to an element of the index set
t ∈ [|W|]. Let fterm(t, d) denote the number of times the word w ∈ W that is indexed as t ∈ [|W|]
appears in the dth article where d ∈ [|D|]. For ABWV, you were provided with a pre-processed
MATLAB data file wordVecV.mat. Please re-use the same data file for this problem. You can
load the content in the second file into MATLAB by using command load ‘wordVecV.mat’. After
loading, you will see a variable V of dimensions 1651 × 10. We refer to this matrix as V . The value
in the tth row and dth column of this matrix is fterm(t, d). Note that in the given dataset |D| = 10
and |W| = 1651.
Now we connect OptM problem 5.5 to the ABWV problem set-up. You will immediately notice
that m = |D| and n = |W|. You can compute the n × m “(raw) term-by-document matrix” M by
noting that [M]i,j = 1 ([V ]i,j ), where 1(x) is 1 if x > 0 and 0 otherwise. The OptM problem 5.5
also describes how to obtain M˜ , a normalized version of M.
(c) Use MATLAB svd command to compute the singular value decomposition of M˜ . List the 10
largest singular values in sorted order.
(d) In part (b) you assumed a low-rank approximation of M˜ and found an expression for the
document similarity. Let the distance between ith and jth documents be d(i, j) as per your
expression from part (b). Let the rank of your approximation be k where 0 < k ≤ min(m, n).
Compute d(i, j) for i, j ∈ [m] by assuming k = 9. Write down the titles of two most similar
documents.
(e) Repeat what you did in part (d) with k = 8, 7, . . . , 1. What is the lowest k that does not
change your answer for part (d)? If your answer for lowest k is greater than 1 what is the
pair of most similar documents for k − 1?
OPTIONAL
None on this problem set
