Interactive Educational Modules in
Scientific Computing

Lower-Rank Approximation

This module demonstrates lower-rank approximation using the singular value decomposition (SVD) and its application to image processing. One way to express the SVD of a matrix is as a sum of rank-one outer products of left and right singular vectors, where each such outer product is multiplied by the corresponding singular value. A useful condensed approximation to the matrix can be obtained by omitting terms from this sum corresponding to the smaller singular values, since they have relatively little effect on the sum. For an m × n matrix, each outer product term requires only m+n+1 storage locations (for the left and right singular vectors and corresponding singular value), so if only the terms corresponding to the k largest singluar values are retained, then the total storage required is only k(m+n+1), which is a substantial savings compared with the mn locations required for the original matrix, assuming k is much smaller than m or n.

Lower-rank approximation is used in this module to provide a condensed approximation to digital images, where an image is represented by three matrices whose entries are intensities of red, green, and blue. The user can choose among several images provided. For a given image, the sliders are used to select the number of terms in the outer product summation, where the singular values are taken from largest to smallest. The red, green, and blue components of the color image are treated separately. In using the sliders, the arrow keys provide finer control to add one term at a time to the summation. The quality of the resulting image can be seen to improve as the rank increases. The corresponding storage required is shown, both as an absolute number of storage locations and as a percentage of the storage required for the original matrix. Note that the latter can exceed 100% for sufficiently large k. Ideally, a good approximation to the image can be obtained for k substantially smaller than m or n.

In addition to image compression, the SVD outer-product expansion can also be used for image enhancement, since noise or blur in an image tends to be carried by the smaller singular values, in which case a lower-rank approximation may look better than the original image because of the omission of the terms corresponding to the smaller singular values.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 3.6.1, especially Example 3.20.

Developers: Evan VanderZee and Michael Heath