The Singular Value Decomposition
# The Singular Value Decomposition

Applications of the Singular Value Decomposition in scientific computing
and digital signal processing is an ongoing research theme at
IMM, and the activities are lead by Prof.
Per Christian Hansen.

Singular vectors (click on image to see larger version).

The Singular Value Decomposition (SVD) of a rectangular matrix *A* is a
decomposition of the form

*A = U S V*^{T}
where *U* and *V* are orthogonal matrices, and *S* is a
diagonal matrix. The columns *u*_{i} and
*v*_{i} of *U* and *V* are called the
left and right singular vectors, respectively, and the diagonal elements
*s*_{i} of *S* are called the singular values.
The singular vectors form orthonormal bases, and the important relation
*A v*_{i} = s_{i} u_{i}
shows that each right singular vectors is mapped onto the corresponding
left singular vector, and the "magnification factor" is the corresponding
singular value.
The image on top of this page shows left singular vectors
*u*_{i} for *i* = 1,...,20 of a matrix arising from the
discretization of a Fredholm integral equation of the first kind
arising in light scattering.
The number of oscillations in *u*_{i} increases with *i*.

The SVD has a variety of applications in scientific computing,
signal processing, automatic control, and many other areas.
On this page we mention a few of these applications.

### Matrix Approximations

A principal image and a rank-4 matrix approximation.

Click on the image to see more principal images and matrix approximations.
By neglecting the small singular values in the "middle matrix" *S* in
the SVD, we can obtain matrix approximations whose rank equals the
number of remaining singular values.
Since the singular values appear in decreasing order, the formula for
the matrix approximation becomes

* A*_{k} = u_{1} s_{1} v_{1}^{T}
* + ... + u*_{k} s_{k} v_{k}^{T}
where *k* is the number of retained singular values.
The terms *u*_{i} s_{i} v_{i}^{T}
are called the principal images.
Often very good matrix approximations
can be obtaind with only a small fraction of the singular values.
To illustrate this point, we computed the SVD of a 32-times-32 digital
image *A*, and then we computed the matrix approximations
*A*_{k} for *k* = 1,...,8.
The image above shows
*u*_{4} s_{4} v_{4}^{T} (left)
together with the rank-4 approximation *A*_{4}.
Click on the image to see the principal images and matrix
approximations for *k* = 1,...,8.

### Truncated SVD Noise Reduction

(click on the image to see a larger version)
The SVD has also applications in digital signal processing, e.g.,
as a method for noise reduction.
The central idea is to let a matrix *A* represent the
noisy signal, compute the SVD, and then discard small singular
values of *A*.
It can be shown that the small singular values mainly represent the
noise, and thus the rank-*k* matrix *A*_{k}
represents a filtered signal with less noise.

The image above shows af GUI Matlab interface to this application
of the SVD, which is called Truncated SVD (TSVD) or Reduced-Rank Noise
Reduction. The software and
interface was constructed in an Informatics Project in 1998-99, and
the software is available as a compressed file
tsvd.exe for Windows.

Some wav-files with speech signals that can be loaded by Matlab
(use "wavread):
alone.wav,
clima.wav,
prices.wav,
speaker.wav.

### Other applications

The SVD is also an important analytical and computational tool in
connection with
regularization of inverse problems, with applications in,
e.g., computational tomography,
image deblurring, and geophysical inversion (seismology).

### References

- Per Christian Hansen,
*The truncated SVD as a method for regularization*,
BIT, 27 (1987), pp. 534-553.
- Per Christian Hansen and Søren Holdt Jensen,
*FIR filter representation of reduced-rank noise reduction*,
IEEE Trans. Signal Proc., 46 (1998), pp. 1737-1741.