SVD and CUR self summary

reference resources: https://www.cnblogs.com/endlesscoding/p/10033527.html https://blog.csdn.net/WangWeb1998/article/details/114376298

1. SVD (singular value decomposition)

• definition:

  There is one m × n m\times n m × The real matrix A of n, we want to decompose it into the following form:

  among U U U and V V V is the unit orthogonal matrix, i.e U U T = I UU^T=I UUT=I and V V T = I VV^T=I VVT=I， U U U is called left singular matrix, V V V is called a right singular matrix, Σ \Sigma Σ There is only a value on the main diagonal, which we call * * singular value * *, and other elements are 0. The dimensions of the above matrix are U ∈ R m × m , Σ ∈ R m × n , V ∈ R n × n U∈Rm×m, Σ∈Rm×n, V∈Rn×n U∈Rm × m, Σ ∈Rm × n,V∈Rn × n. Average Σ \Sigma Σ There are the following forms:

• Singular value solution

• Application in image compression:

  1. Read picture

     %matplotlib inline
     import matplotlib.pyplot as plt
     import matplotlib.image as mpimg
     import numpy as np
     
     img_eg = mpimg.imread("../img/beauty.jpg")
     print(img_eg.shape)
     

     The picture size is 600x400x3

  2. singular value decomposition

     img_temp = img_eg.reshape(600, 400 * 3)
     U,Sigma,VT = np.linalg.svd(img_temp)
     

     Let's turn the picture into 600 first × 1200, and then do singular value decomposition. The singular value sigma obtained from svd function is arranged from large to small

  3. Take the singular value of the first part to reconstruct the picture

     # Take the first 60 singular values
     sval_nums = 60
     img_restruct1 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
     img_restruct1 = img_restruct1.reshape(600,400,3)
     
     # Take the first 120 singular values
     sval_nums = 120
     img_restruct2 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
     img_restruct2 = img_restruct2.reshape(600,400,3)
     

     Compare the picture and see the effect:

     fig, ax = plt.subplots(1,3,figsize = (24,32))
     
     ax[0].imshow(img_eg)
     ax[0].set(title = "src")
     ax[1].imshow(img_restruct1.astype(np.uint8))
     ax[1].set(title = "nums of sigma = 60")
     ax[2].imshow(img_restruct2.astype(np.uint8))
     ax[2].set(title = "nums of sigma = 120")
     

     It can be seen that when we take the first 120 singular values to reconstruct the picture, we basically can't see how much difference it is from the original picture.

• Summary:

  It can be seen from the compression results of the above picture that the singular value can be regarded as the representative value of a matrix, or the singular value can represent the information of this matrix** When the singular value is larger, it represents more information** Therefore, we can basically restore the data itself by taking the first several largest singular values.

2. CUR (matrix decomposition)

When it comes to matrix decomposition, I believe the most familiar one must be SVD decomposition, but SVD decomposition has two disadvantages:

1. Poor interpretability: for SVD decomposition, it is generally understood that the left singular vector and the right singular vector are expanded into the column space and row space of the original matrix respectively, but there is no strong interpretability for the original matrix.

2. Too dense: even if the original matrix is a sparse matrix, the U and V matrices decomposed by the matrix are still highly dense, which is unacceptable in some application scenarios.
   Compared with SVD

3. The interpretability of CUR decomposition is greatly enhanced

1. CUR matrix decomposition:

For a matrix A, can we decompose it into a combination containing only some rows and columns in a?

More specifically, for a rank k matrix A, if we choose the column space in which k columns are expanded into matrix A and the row space in which k rows are expanded into matrix A, we should also be able to restore the original matrix by combining these linear mappings.

In order to more intuitively understand the decomposition of memory CUR matrix, you can look at the following figure

In the figure, red represents the selected column, blue represents the selected row, and U is the intersection of these rows and columns, which is represented by purple in the figure.

From the figure, we can see that CUR decomposition is like finding the "skeleton" of a matrix, which reflects the main information of the matrix.