Singular Value Decomposition (SVD)

CS 663

Ajit Rajwade

1

Singular value Decomposition

• For any m x n matrix A, the following decomposition always exists:

2

Diagonal matrix with non-negative entries on the diagonal – called singular values.

Singular value Decomposition

• For any m x n real matrix A, the SVD consists of matrices U,S,V which are always real – this is unlike eigenvectors and eigenvalues of A which may be complex even if A is real.

​

• The singular values are always non-negative, even though the eigenvalues may be negative.

​

• While writing the SVD, the following convention is assumed, and the left and right singular vectors are also arranged accordingly:

3

Singular value Decomposition

• If only r < min(m,n) singular values are non-zero, the SVD can be represented in reduced form as follows:

4

Singular value Decomposition

5

This m by n matrix u_i v^T_i is the product of a column vector u_i and the transpose of column vector v_i. It has rank 1. Thus A is a weighted summation of r rank-1 matrices.

​

Note: u_i and v_i are the i-th column of matrix U and V respectively.

Singular value decomposition

6

Application: SVD of Natural Images

• An image is a 2D array – each entry contains a grayscale value. The image can be treated as a matrix.
• It has been observed that for many image matrices, the singular values undergo rapid decay (note: they are always non-negative).
• An image can be approximated with the k largest singular values and their corresponding singular vectors:

​

7

Singular values of the Mandrill Image: notice the rapid exponential decay of the values! This is characteristic of MOST natural images.

9

Left to right, top to bottom:

Reconstructed image using the first i= 1,2,3,5,10,25,50,100,150 singular values and singular vectors.

Last image: original

​

10

Left to right, top to bottom, we display:

​

​

where i = 1,2,3,5,10,25,50,100,150.

Note each image is independently re-scaled to the 0-1 range for display purpose.

​

Note: the spatial frequencies increase as the singular values decrease

SVD: Use in Image Compression

• Instead of storing mn intensity values, we store (n+m+1)r intensity values where r is the number of stored singular values (or singular vectors). The remaining m-r singular values (and hence their singular vectors) are effectively set to 0.

​

• This is called as storing a low-rank (rank r) approximation for an image.

11

Properties of SVD: Best low-rank reconstruction

• SVD gives us the best possible rank-r approximation to any matrix (it may or may not be a natural image matrix).
• In other words, the solution to the following optimization problem:

​

is given using the SVD of A as follows:

​

12

Note: We are using the singular vectors corresponding to the r largest singular values.

This property of the SVD is called the Eckart Young Theorem.

Properties of SVD: Best low-rank reconstruction

13

Frobenius norm of the matrix (fancy way of saying you square all matrix values, add them up, and then take the square root!)

Why?

Geometric interpretation: Eckart-Young theorem

• The best linear approximation to an ellipse is its longest axis.
• The best 2D approximation to an ellipsoid in 3D is the ellipse spanned by the longest and second-longest axes.
• And so on!

14

Properties of SVD: Singularity

• A square matrix A is non-singular (i.e. invertible or full-rank) if and only if all its singular values are non-zero.
• The ratio σ₁/σ_n tells you how close A is to being singular. This ratio is called condition number of A. The larger the condition number, the closer the matrix is to being singular.

15

Properties of SVD: Rank, Inverse, Determinant

• The rank of a rectangular matrix A is equal to the number of non-zero singular values. Note that rank(A) = rank(S).
• SVD can be used to compute inverse of a square matrix:

​

​

​

• Absolute value of the determinant of square matrix A is equal to the product of its singular values.

​

​

16

Properties of SVD: Pseudo-inverse

• SVD can be used to compute pseudo-inverse of a rectangular matrix:

​

​

17

Properties of SVD: Frobenius norm

• The Frobenius norm of a matrix is equal to the square-root of the sum of the squares of its singular values:

18

Geometric interpretation of the SVD

• Any m x n matrix A transforms a hypersphere Q of unit radius (called as unit sphere) in Rⁿ into a hyperellipsoid in R^m (assume m >= n).

19

Q

AQ

Geometric interpretation of the SVD

• But why does A transform the hypersphere into a hyperellipsoid?
• This is because A = USV^T.
• V^T transforms the hypersphere into another (rotated/reflected) hypersphere.
• S stretches the sphere into a hyperellipsoid whose semi-axes coincide with the coordinate axes as per V.
• U rotates/reflects the hyperellipsoid without affecting its shape.
• As any matrix A has an SVD decomposition, it will always transform the hypersphere into a hyperellipsoid.
• If A does not have full rank, then some of the semi-axes of the hyperellipsoid will have length 0!

​

20

Geometric interpretation of the SVD

• Assume A has full rank for now.
• The singular values of A are the lengths of the n principal semi-axes of the hyperellipsoid. The lengths are thus σ₁, σ ₂, …, σ _n.
• The n left singular vectors of A are the directions u₁, u₂, …, u_n (all unit-vectors) aligned with the n semi-axes of the hyperellipsoid.
• The n right singular vectors of A are the directions v₁, v₂, …, v_n (all unit-vectors) in hypersphere Q, which the matrix A transforms into the semi-axes of the hyperellipsoid, i.e.

​

21

Geometric interpretation of the SVD

• Expanding on the previous equations, we get the reduced form of the SVD

​

22

n x n diagonal matrix - S

m x n matrix (m >> n) with orthonormal columns - U

n x n orthonormal matrix V

Computation of the SVD

• We will not explore algorithms to compute the SVD of a matrix, in this course.
• SVD routines exist in the LAPACK library and are interfaced through the following MATLAB functions:

​

23

s = svd(X) returns a vector of singular values.

​

[U,S,V] = svd(X) produces a diagonal matrix S of the same dimension as X, with nonnegative diagonal elements in decreasing order, and unitary matrices U and V so that X = U*S*V'.

​

[U,S,V] = svd(X,0) produces the "economy size" decomposition. If X is m-by-n with m > n, then svd computes only the first n columns of U and S is n-by-n.

​

[U,S,V] = svd(X,'econ') also produces the "economy size" decomposition. If X is m-by-n with m >= n, it is equivalent to svd(X,0). For m < n, only the first m columns of V are computed and S is m-by-m.

s = svds(A,k) computes the k largest singular values and associated singular vectors of matrix A.

SVD Uniqueness

• If the singular values of a matrix are all distinct, the SVD is unique – up to a multiplication of the corresponding columns of U and V by a sign factor.
• Why?

24

SVD Uniqueness

• A matrix is said to have degenerate singular values, if it has the same singular value for 2 or more pairs of left and right singular vectors.
• In such a case any normalized linear combination of the left (right) singular vectors is a valid left (right) singular vector for that singular value.

25

Any other applications of SVD?

• Face recognition – the popular eigenfaces algorithm can be implemented using SVD too!
• Point matching: Consider two sets of points, such that one point set is obtained by an unknown rotation of the other. Determine the rotation!
• Structure from motion: Given a sequence of images of a object undergoing rotational motion, determine the 3D shape of the object as well as the 3D rotation at every time instant!

26

PCA Algorithm using SVD

1. Compute the mean of the given points:

​

​

• Deduct the mean from each point:

​

• Compute the covariance matrix of these mean-deducted points:

​

PCA Algorithm using SVD

4. Instead of finding the eigenvectors of C, we find the left singular vectors of X and its singular values

​

​

5. Extract the k eigenvectors in U corresponding to the k largest singular values to form the extracted eigenspace:

​

​

​

There is an implicit assumption here that the first k indices indeed correspond to the k largest eigenvalues. If that is not true, you would need to pick the appropriate indices.

U,S,V are obtained by computing the SVD of X.

References

• Scientific Computing, Michael Heath
• Numerical Linear Algebra, Treftehen and Bau
• http://en.wikipedia.org/wiki/Singular_value_decomposition

29