Dimensionality Reduction - Mining of Massive Datasets - page 398

Figure 11.5 The form of a singular-value decomposition

EXAMPLE 11.8 Figure 11.6 gives a rank-2 matrix representing ratings of movies by users.
In this contrived example there are two “concepts” underlying the movies: science-fiction
and romance. All the boys rate only science-fiction, and all the girls rate only romance. It
is this existence of two strictly adhered to concepts that gives the matrix a rank of 2. That
is, we may pick one of the first four rows and one of the last three rows and observe that
there is no nonzero linear sum of these rows that is 0. But we cannot pick three independent
rows. For example, if we pick rows 1, 2, and 7, then three times the first minus the second,
plus zero times the seventh is 0 .

Figure 11.6 Ratings of movies by users

We can make a similar observation about the columns. We may pick one of the first three
columns and one of the last two rows, and they will be independent, but no set of three
columns is independent.
The decomposition of the matrix M from Fig. 11.6 into U , Σ, and V , with all elements
correct to two significant digits, is shown in Fig. 11.7 . Since the rank of M is 2, we can
use r = 2 in the decomposition. We shall see how to compute this decomposition in Section
11.3.6 . □

Figure 11.7 SVD for the matrix M of Fig. 11.6

11.3.2 Interpretation of SVD

The key to understanding what SVD offers is in viewing the r columns of U , Σ, and V as
representing concepts that are hidden in the original matrix M . In Example 11.8 , these con-
cepts are clear; one is “science fiction” and the other is “romance.” Let us think of the rows
of M as people and the columns of M as movies. Then matrix U connects people to con-
cepts. For example, the person Joe, who corresponds to row 1 of M in Fig. 11.6 , likes only