Linear Algebra for Data Science Using Python/

...

/

Singular Value Decomposition: SVD

Singular Value Decomposition: SVD

Learn one of the most important matrix decompositions, singular value decomposition.

We'll cover the following...

Definition

The Singular Value Decomposition (SVD) of an n×dn\times d matrix, AA, is the factorization of AA, multiplied by the product of three matrices: A=UΣVTA = U\Sigma V^T, where the matrices Un×nU_{n\times n} and Vd×dTV^T_{d\times d} are orthogonal and the matrix, Σn×d\Sigma_{n\times d}, is a generalized diagonalGeneralizedDiagonal with non-negative real entries.

SVD in numpy

We can compute SVD of a matrix, A, using U,S,Vt = numpy.linalg.svd(A), where S is an array containing diagonal entries of Σ\Sigma and Vt is VTV^T. The diag function in the implementation below converts the S array into the generalized diagonal matrix, Σ\Sigma. We’ve used the D variable to represent Σ\Sigma in the code.

Python 3.8
import  numpy as np
from numpy.linalg import svd
# Function to construct generalized diagonal matrix
def diag(S, m, n):
    D  = np.zeros((m, n))
    k = len(S)
    D[:k, :k]=np.diag(S)
    return D
m, n = 2, 3
A = np.random.rand(m, n)
# Compute SVD using numpy
U, S, Vt = svd(A)
# Compute Frobenius norm
frobNorm = np.linalg.norm(U.dot(diag(S, m, n)).dot(Vt)-A)
R = [0, frobNorm]
print(f'The Frobenius norm of UDV^T - A is {R[frobNorm>1e-10]}')
print(f'U^TU\n{abs(np.round(U.T.dot(U), 1))}')
print(f'V^TV\n{abs(np.round(Vt.dot(Vt.T), 1))}')

Singular values and vectors

  • The diagonal values of Σ\Sigma are the singular values of AA.
  • The columns of UU are the left singular vectors of AA.
  • The rows of VTV^T are the right singular vectors of AA.

We assume that the singular values in Σ\Sigma are in descending order. That’s how numpy.linalg.svd returns the values in S. We can arrange the values in any order if we’re provided the corresponding arrangement of the columns of UU and the rows of VTV^T.

Economic SVD

When Σ\Sigma has some zeros in the diagonal, we can drop them. We can also drop the corresponding columns in UU and the rows in VTV^T. If Σ^\hat \Sigma is the diagonal matrix with only non-zero singular values, and U^\hat U and V^\hat V are the matrices of the corresponding columns and rows in UU and VV, respectively, then

A=UΣVT=U^Σ^V^TA=U\Sigma V^T=\hat U \hat \Sigma \hat V^T ...