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 $A \in \mathbb{C}^{n\times m}$, its SVD is

$$A = U\Sigma V^{*}$$

where $V^{*}$ is the complex conjugate transpose. Both $U$ and $V$ are unitary matrices that is the following holds

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

In general, if a matrix $W$ is a real matrix i.e. its entries are real numbers, then $W^{*} = W^T$. Thus, if $A \in \mathbb{R}^{n \times m}$ the matrices $U$ and $V$ are real orthogonal matrices i.e.

$$UU^{T} = U^{T}U = I$$

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

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.