Database Reference
In-Depth Information
from the column of
M
for
Alien
. The 5 in the second column reflects the 5 in
M
's row for
Jenny and column for
Casablanca
; the latter is the column of
M
from which the second
column of
C
was derived. Similarly, the second row of
W
is the entries in the row for Jack
and columns for
Alien
and
Casablanca
, respectively.
□
The matrix
U
is constructed from
W
by the Moore-Penrose pseudoinverse described in
elements in the matrix Σ of singular values by their numerical inverses, to obtain the pseu-
doinverse Σ
+
. Then
U
=
Y
(Σ
+
)
2
X
T
.
EXAMPLE
11.15 Let us construct
U
from the matrix
W
that we constructed in
Example
That is, the three matrices on the right are
X
, Σ, and
Y
T
, respectively. The matrix Σ has
no zeros along the diagonal, so each element is replaced by its numerical inverse to get its
Moore-Penrose pseudoinverse:
Now
X
and
Y
are symmetric, so they are their own transposes. Thus,
11.4.4
The Complete CUR Decomposition
We now have a method to select randomly the three component matrices
C
,
U
, and
R
.
Their product will approximate the original matrix
M
. As we mentioned at the beginning of
the discussion, the approximation is only formally guaranteed to be close when very large
numbers of rows and columns are selected. However, the intuition is that by selecting rows
and columns that tend to have high “importance” (i.e., high Frobenius norm), we are ex-
tracting the most significant parts of the original matrix, even with a small number of rows
and columns. As an example, let us see how well we do with the running example of this
section.
EXAMPLE
11.16 For our running example, the decomposition is shown in
Fig. 11.13
. While
there is considerable difference between this result and the original matrix
M
, especially in
the science-fiction numbers, the values are in proportion to their originals. This example is
much too small, and the selection of the small numbers of rows and columns was arbitrary
