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₁ s₁ v₁^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₄ s₄ v₄^T (left) together with the rank-4 approximation A₄. 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.