Processing math: 6%

Singular Value Decompositions


Learning Objectives

Singular Value Decomposition

An m×n real matrix A has a singular value decomposition of the form

A=UΣVT

where

Σ=[σ1σs0000]when m>n,andΣ=[σ100σs00]whenm<n.

where s=min and σ1σ2σs0 are the square roots of the eigenvalues values of ATA. The diagonal entries are called the singular values of A.

Note that if , then and both have the same eigenvalues:

(left-multiply both sides by )

Time Complexity

The time-complexity for computing the SVD factorization of an arbitrary m×n matrix is proportional to , where the constant of proportionality ranges from 4 to 10 (or more) depending on the algorithm.

In general, we can define the cost as:

Reduced SVD

The SVD factorization of a non-square matrix A of size m×n can be represented in a reduced format:


The following figure depicts the reduced SVD factorization (in red) against the full SVD factorizations (in gray).

In general, we will represent the reduced SVD as:

where is a matrix, is a matrix, is a matrix, and .

Example: Computing the SVD

We begin with the following non-square matrix, A

A=[323882874187647]

and we will compute the reduced form of the SVD (where here ):

(1) Compute ATA:

(2) Compute the eigenvectors and eigenvalues of ATA:

(3) Construct VR from the eigenvectors of ATA:

VR=[0.5850510.7103990.3912120.6526480.1260680.7470980.4814180.6924150.537398].

(4) Construct ΣR from the square roots of the eigenvalues of ATA:

ΣR=[20.9160006.532070004.22807]

(5) Find U by solving UΣ=AV. For our reduced case, we can find UR=AVRΣR1. You could also find U by computing the eigenvectors of AAT.

We obtain the following singular value decomposition for A:

[323882874187647]A=[0.2153710.0303480.3054900.5194320.5037790.4191730.5342620.3110210.0117300.4387150.7878780.4313520.4537590.1667290.738082]U[20.9160006.532070004.22807]Σ[0.5850510.6526480.4814180.7103990.1260680.6924150.3912120.7470980.537398]VT

Recall that we computed the reduced SVD factorization (i.e. Σ is square, U is non-square) here.

Rank, null space and range of a matrix

Suppose is a matrix where (without loss of generality):

We can re-write the above as:

Furthermore, the product of two matrices can be written as a sum of outer products:

For a general rectangular matrix, we have:

where .

If has non-zero singular values, the matrix is full rank, i.e. .

If has non-zero singular values, and , the matrix is rank deficient, i.e. .

In other words, the rank of equals the number of non-zero singular values which is the same as the number of non-zero diagonal elements in .

Rounding errors may lead to small but non-zero singular values in a rank deficient matrix. Singular values that are smaller than a given tolerance are assumed to be numerically equivalent to zero, defining what is sometimes called the effective rank.

The right-singular vectors (columns of ) corresponding to vanishing singular values of span the null space of , i.e. null() = span{, , …, }.

The left-singular vectors (columns of ) corresponding to the non-zero singular values of span the range of , i.e. range() = span{, , …, }.

Example:

The rank of is 2.

The vectors and provide an orthonormal basis for the range of .

The vector provides an orthonormal basis for the null space of .

(Moore-Penrose) Pseudoinverse

If the matrix is rank deficient, we cannot get its inverse. We define instead the pseudoinverse:

For a general non-square matrix A with known SVD (A=UΣVT), the pseudoinverse is defined as:

For example, if we consider a full rank matrix where :

Euclidean norm of matrices

The induced 2-norm of a matrix can be obtained using the SVD of the matrix :

And hence,

In the above equations, all the notations for the norm refer to the Euclidean norm, and we used the fact that and are orthogonal matrices and hence .

Example:

We begin with the following non-square matrix :

The matrix of singular values, Σ, computed from the SVD factorization is:

Σ=[20.9160006.532070004.22807].

Consequently the 2-norm of A is

A2=20.916.

Euclidean norm of the inverse of matrices

Following the same derivation as above, we can show that for a full rank matrix we have:

where is the smallest singular value.

For non-square matrices, we can use the definition of the pseudoinverse (regardless of the rank):

where is the smallest non-zero singular value. Note that for a full rank square matrix, we have . An exception of the definition above is the zero matrix. In this case,

2-Norm Condition Number

The 2-norm condition number of a matrix A is given by the ratio of its largest singular value to its smallest singular value:

If the matrix is rank deficient, i.e. , then .

Low-rank Approximation

The best rank- approximation for a matrix , where , for some matrix norm , is one that minimizes the following problem:

Under the induced 2-norm, the best rank-k approximation is given by the sum of the first k outer products of the left and right singular vectors scaled by the corresponding singular value (where, σ1σs):

Observe that the norm of the difference between the best approximation and the matrix under the induced 2-norm condition is the magnitude of the (k+1)th singular value of the matrix:

Note that the best rank- approximation to can be stored efficiently by only storing the singular values , the left singular vectors , and the right singular vectors .

The figure below show best rank-k approximations of an image (you can find the code snippet that generates these images in the IPython notebook):

Review Questions

ChangeLog