"Statistical learning methods (2nd Edition)" Li Hang Chapter 15 singular value decomposition SVD mind map notes and after-school exercise answers (detailed steps) SVD matrix singular value Chapter 15

15.1

Try to find the matrix
$$A=\left[\begin{array}{lll}1& 2& 0\\ 2& 0& 2\end{array}\right]$$
Singular value decomposition of .

Calculate the result by hand ,
$$U=\frac{1}{\sqrt{5}}\left[\begin{array}{ll}1& 2\\ 2& -1\end{array}\right],\Sigma =\left[\begin{array}{lll}3& 0& 0\\ 0& 2& 0\end{array}\right],V^T=\frac{1}{\sqrt{5}}\left[\begin{array}{lll}\frac{5}{3}& \frac{2}{3}& \frac{4}{3}\\ 0& 2& -1\\ -2& 1& 2\end{array}\right]$$
Check it out ：

import numpy as np

U = 1 / np.sqrt(5) * np.array([[1, 2], [2, -1]])
Sigma = np.array([[3, 0, 0], [0, 2, 0]])
V_transpose = 1 / np.sqrt(5) * np.array([[5/3, 2/3, 4/3], [0, 2, -1], [-2, 1, 2]])

U @ Sigma @ V_transpose

array([[1., 2., 0.],
       [2., 0., 2.]])

to glance at numpy Decomposition in ：

A = np.array([[1, 2, 0], [2, 0, 2]])
U, Sigma, V_transpose = np.linalg.svd(A)

print('U:\n', U)
print('Sigma:\n', Sigma)
print('V_transpose:\n', V_transpose)

U:
 [[ 0.4472136  -0.89442719]
 [ 0.89442719  0.4472136 ]]
Sigma:
 [3. 2.]
V_transpose:
 [[ 7.45355992e-01  2.98142397e-01  5.96284794e-01]
 [ 1.94726023e-16 -8.94427191e-01  4.47213595e-01]
 [-6.66666667e-01  3.33333333e-01  6.66666667e-01]]

1 / np.sqrt(5) * np.array([[1, 2], [2, -1]]) #  Hand calculated U

array([[ 0.4472136 ,  0.89442719],
       [ 0.89442719, -0.4472136 ]])

1 / np.sqrt(5) * np.array([[5/3, 2/3, 4/3], [0, 2, -1], [-2, 1, 2]]) #  Hand calculated V Transposition 

array([[ 0.74535599,  0.2981424 ,  0.59628479],
       [ 0.        ,  0.89442719, -0.4472136 ],
       [-0.89442719,  0.4472136 ,  0.89442719]])

You can find ,numpy Self contained decomposition , The second basis of the left singular matrix is one sign away from the result of the manual calculation , It shows that the selection of decomposition time base is not unique , Corresponding V.T The second line of is also a minus sign , And for V.T The third line of is a A Base of zero space , My choice is not very strict , Just meet in zero space , and numpy I don't know how to guarantee V.T Row orthogonality of , So as to ensure the orthogonality of its columns , But in fact, the direction of our basis vector is the same , This degree of freedom is being restored A Time does not make an impression , As verified above .

15.2

Try to find the matrix
$$A=\left[\begin{array}{ll}2& 4\\ 1& 3\\ 0& 0\\ 0& 0\end{array}\right]$$
And write its outer product expansion .

This $A^{T}A$ The eigenvalue of is an irrational number , Manual calculation is a little cumbersome , So I solved it directly with code ：

15 - np.sqrt(13*17), 15 + np.sqrt(13*17) #  The above two eigenvalues 

(0.13393125268149397, 29.866068747318508)

A = np.array([[2, 4], [1, 3], [0, 0], [0, 0]])
U, Sigma, V_transpose = np.linalg.svd(A)

print('U:\n', U)
print('Sigma:\n', Sigma)
print('V_transpose:\n', V_transpose)

U:
 [[-0.81741556 -0.57604844  0.          0.        ]
 [-0.57604844  0.81741556  0.          0.        ]
 [ 0.          0.          1.          0.        ]
 [ 0.          0.          0.          1.        ]]
Sigma:
 [5.4649857  0.36596619]
V_transpose:
 [[-0.40455358 -0.9145143 ]
 [-0.9145143   0.40455358]]

So the original matrix is the superposition of two outer products , The first outer product is ：

first_item = Sigma[0] * U[:, 0][:, None] @ V_transpose[0][None, :]
first_item

array([[1.80720735, 4.08528566],
       [1.27357371, 2.87897923],
       [0.        , 0.        ],
       [0.        , 0.        ]])

The second outer product is ：

second_item = Sigma[1] * U[:, 1][:, None] @ V_transpose[1][None, :]
second_item

array([[ 0.19279265, -0.08528566],
       [-0.27357371,  0.12102077],
       [ 0.        ,  0.        ],
       [ 0.        ,  0.        ]])

See if the result of addition is equal to the original ：

A == first_item + second_item

array([[ True,  True],
       [ True,  True],
       [ True,  True],
       [ True,  True]])

15.3

Compare the similarities and differences between singular value decomposition of matrix and diagonalization of symmetric matrix .

identical ：
Eigenvalues are required 、 Calculation of eigenvectors ;
Eigenvalues are nonnegative ;
The number of positive eigenvalues is equal to the rank of the original matrix ;
The eigenvectors corresponding to eigenvalues are orthogonal .

Different :
The eigenvalue eigenvector of singular value decomposition solution is not of the original matrix , But the symmetric matrix formed by the product of the original matrix and its transpose ;
The diagonalization of symmetric matrix only needs to find the eigenvalue eigenvector once , Singular value decomposition can only get part of the column vector on one side of the left or right singular matrix , You need to solve the eigenvalue eigenvector twice , Or by the correspondence between the column vectors of left and right singular matrices , Find the other side again , Finally, we need to find the standard orthogonal basis of zero space , To complete the left and right singular matrix ;
For singular value decomposition , There are certain degrees of freedom for matrices in zero space , So it makes U There may be non orthogonality between the rows of ,$V^T$ There may be non orthogonality between the columns of （ Of course, you can choose a more strictly orthogonal value ）. Diagonalization of symmetric matrices , It is orthogonal. .

15.4

Prove that any rank is 1 The matrix of can be written as the outer product of two vectors , And give an example .

Prove one :
If the rank of a matrix is 1, Then we can know from the knowledge of elementary transformation of linear algebra , There must be a column vector of a matrix , By multiplying by a certain coefficient , Equal to any other column , So you can subtract and eliminate other columns , That is to say, the column vector of the matrix is only a coefficient times of this column vector , Thus, the outer product of the column vector is a row vector corresponding to each column coefficient to obtain the matrix .（ Just scrape together examples ）
Proof II :
If the rank of the matrix is 1, Then the singular value decomposition diagonal matrix has only the first principal diagonal element ${\sigma }_1$ Not 0, The other elements are 0, be $A=U\Sigma V^T$ Turn into $A=u_1{\sigma }_1{v}_1^T$, among $u_1$ and $v_1^T$ by $U$ The first column and $V^T$ The first line of . Because the singular value decomposition of matrix must exist , At this time, the decomposition is the vector outer product , So the rank is 1 The matrix of must have the outer product form of two vectors .

15.5

Click data in search records query statements submitted by users during search , Click on the page URL, And the number of clicks , Form a bipartite graph , One of the node sets $\{q_i\}$ Represents a query , Another node set $\{u_j\}$ Express URL, The edge indicates the click relationship , The weight on the edge indicates the number of clicks . As shown in the following figure, click on the data example . Click data can be represented by matrix , Try singular value decomposition , And explain the contents of the three matrix representations .

#  Construct a data matrix 
A = np.array([[0, 20, 5, 0, 0],
              [10, 0, 0, 3, 0],
              [0, 0, 0, 0, 1],
              [0, 0, 1, 0, 0]])
U, Sigma, V_transpose = np.linalg.svd(A)
print('U:\n', U)
print('Sigma:\n', Sigma)
print('V_transpose:\n', V_transpose)

U:
 [[ 9.99930496e-01 -1.01352447e-16  0.00000000e+00 -1.17899939e-02]
 [ 0.00000000e+00  1.00000000e+00  0.00000000e+00 -8.65973959e-15]
 [ 0.00000000e+00  0.00000000e+00  1.00000000e+00  0.00000000e+00]
 [ 1.17899939e-02  8.65973959e-15  0.00000000e+00  9.99930496e-01]]
Sigma:
 [20.61695792 10.44030651  1.          0.97007522]
V_transpose:
 [[ 0.00000000e+00  9.70007796e-01  2.43073808e-01  0.00000000e+00
   0.00000000e+00]
 [ 9.57826285e-01 -2.31404926e-16  8.02571613e-16  2.87347886e-01
   0.00000000e+00]
 [-0.00000000e+00  0.00000000e+00  0.00000000e+00  0.00000000e+00
   1.00000000e+00]
 [-7.97105437e-16 -2.43073808e-01  9.70007796e-01  0.00000000e+00
   0.00000000e+00]
 [ 2.87347886e-01 -1.01402229e-16  2.10571835e-16 -9.57826285e-01
   0.00000000e+00]]

For the convenience of observation , give ：

explain ：
You can see that the first two singular values are much larger than the last two , Refer to above Mind mapping in , The geometric meaning of singular value decomposition and the physical meaning of outer product representation are described , It can be analyzed in this way . The main contribution of this clicked data matrix comes from the patterns corresponding to the first two singular values . For the first mode , see U The first column , The direction of its base is mainly in the first element , This is the original A The basis vector of the range space of a matrix , This vector corresponds to the largest singular value , Indicates that this base is query The main contributors to this model , And mainly from the original A The first contribution of the representation of the matrix , namely $q_1$ The contribution of , Then its corresponding $V^T$ The first line of , It said A The basis vector of the row space of , This basis vector is mainly in the original A The direction of the second coordinate under the representation , namely $u_2$, Explain that in this mode , stay url In the space $u_2$ Direction data , After linear transformation, it mainly becomes query In the space $q_1$ Direction data . Empathy , For the mode of the second singular value , Similar analysis can be obtained , stay url In the space $u_1$ Direction data , After linear transformation, it mainly becomes query In the space $q_2$ Direction data .
Sum up , You can get , This data matrix , The main contribution comes from two modes , The main contribution of the first model is $q_1$ To $u_2$, The main contribution of the second model is $q_2$ To $u_1$, Because this bipartite graph is not complicated , As you can see intuitively in the figure , The main mode is 20,10 Weighted ,20 The pattern of corresponds to $q_1$ To $u_2$,10 The pattern of corresponds to $q_2$ To $u_1$.

You can verify the above explanation ：

first_item = Sigma[0] * U[:, 0][:, None] @ V_transpose[0][None, :]
first_item

array([[ 0.        , 19.99721992,  5.01109415,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.23578349,  0.05908488,  0.        ,  0.        ]])

second_item = Sigma[1] * U[:, 1][:, None] @ V_transpose[1][None, :]
second_item[second_item<0.001] = 0
second_item

array([[ 0.,  0.,  0.,  0.,  0.],
       [10.,  0.,  0.,  3.,  0.],
       [ 0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.]])

third_item = Sigma[2] * U[:, 2][:, None] @ V_transpose[2][None, :]
third_item[third_item<0.001] = 0
third_item

array([[0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1.],
       [0., 0., 0., 0., 0.]])

fourth_item = Sigma[3] * U[:, 3][:, None] @ V_transpose[3][None, :]
fourth_item[fourth_item<0.001] = 0
fourth_item

array([[0.        , 0.00278008, 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.94091512, 0.        , 0.        ]])