Applications of Singular-Value Decomposition (SVD)

Alkiviadis G. Akritas^{∗} and Gennadi I. Malaschonok^{†}

Summer 2002

Abstract

Let A be an m × n matrix with m ≥ n. Then one form of the singular-value decomposition of A is

A = U^{T} ΣV,

where U and V are orthogonal and Σ is square diagonal. That is, UU^{T} = I_{rank(A)}, V V^{T} = I_{rank(A)}, U is rank(A) × m, V is rank(A) × n and

Σ = ( \begin{matrix}σ_{1} & 0 & ⋯ & 0 & 0 \\ 0 & σ_{2} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & σ_{rank(A)−1} & 0 \\ 0 & 0 & ⋯ & 0 & σ_{rank(A)} \end{matrix} )

is a rank(A)×rank(A) diagonal matrix. In addition σ_{1} ≥ σ_{2} ≥ ⋯ ≥ σ_{rank(A)} > 0. The σ_{i}’s are called the singular values of A and their number is equal to the rank of A. The ratio \frac{σ_{1}}{σ_{rank(A)}} can be regarded as a condition number of the matrix A.

It is easily verified that the singular-value decomposition can be also written as

A = U^{T} ΣV = ∑_{i=1}^{rank(A)} σ_{i}u_{i}^{T} v_{i}.

The matrix u_{i}^{T} v_{i} is the outer product of the i-th row of U with the corresponding row of V. Note that each of these matrices can be stored using only m + n locations rather than mn locations.

The singular value decomposition is over a hundred years old. For the case of square matrices, it was discovered independently by Beltrami in 1873 and Jordan in 1874. The technique was extended to rectangular matrices by Eckart and Young in the 1930’s and its use as a computational tool dates back to the 1960’s. Gene Golub and van Loan demonstrated its usefulness and feasibility in a wide variety of applications.

Using both forms presented above—and following Jerry Uhl’s beautiful approach— we show how SVD can be used as a tool for teaching Linear Algebra geometrically, and then apply it in solving least-squares problems and in data compression.

∗University of Thessaly, Department of Computer and Communication Engineering, GR-38221 Volos, Greece

†Tambov University, Department of Mathematics,Tambov, Russia