Singular Value Decomposition

One of the most important matrix factorization techniques is the singular value decomposition most often abbreviated as SVD. The reason why is so popular lies on the fact that it is the foundation for many other computational techniques. For example, just to name a few:

  • Computing pseudo-inverses
  • Obtaining low-rank matrix approximations
  • Dynamic mode decomposition
  • Proper orthogonal ecomposition
  • Principal components analysis

For a complex matrix ACn×mA \in \mathbb{C}^{n\times m}, its SVD is

A=UΣVA = U\Sigma V^{*}

where VV^{*} is the complex conjugate transpose. Both UU and VV are unitary matrices that is the following holds

UU=UU=IUU^{*} = U^{*}U = I

In general, if a matrix WW is a real matrix i.e. its entries are real numbers, then W=WTW^{*} = W^T. Thus, if ARn×mA \in \mathbb{R}^{n \times m} the matrices UU and VV are real orthogonal matrices i.e.

UUT=UTU=IUU^{T} = U^{T}U = I

The matrix Σ\Sigma is a diagonal matrix with real and nonnegative entries on the diagonal. The entries Σii\Sigma_{ii} are called the singular values of AA. The number of the non-zero singular values corresponds to the rank of the matrix AA.

Given the popularity of the SVD method, it is not surpsising that most linear algebra libraries provide a way to perform it. The following script shows how to compute the SVD in Python using numpy

import numpy as np
X = np.random.rand(10 , 10)
U, S, V = np.linalg.svd(X, full_matrices=True)
# or doing economy SVD
U, S, V = np.linalg.svd(X, full_matrices=False)

You can find the documentation at numpy.linalg.svd. Similarly, using the Blaze C++ library

template< typename MT1, bool SO, typename VT, bool TF, typename MT2, typename MT3 >
void svd( const DenseMatrix<MT1,SO>& A, DenseMatrix<MT2,SO>& U,
          DenseVector<VT,TF>& s, DenseMatrix<MT3,SO>& V );

Overall, the SVD algorithm is a very important matrix decomposition technique used throughout numerical modeling control theory and system identification. We will see applications of the method in future posts.