In the early 1900's, Hadamard defined a problem as "ill-posed" if the solution of the problem either does not exist, is not unique, or if it is not a continuous function of the data. Such problems are extremely sensitive to perturbations (noise) in the data; that is, small perturbations of the data can lead to arbitrarily large perturbations in the solution. Contrary to Hadamard's belief, ill-posed problems arise naturally in many areas of science and engineering; one important example is image restoration, which is the process of minimizing or removing degradation (such as blur) from an observed image.

Many algorithms have been developed to compute approximate solutions of ill-posed problems, but they may differ in a variety of ways. For example, there are several different regularization methods one could use, and for each of these, various methods for choosing a regularization parameter.

An important tool in the development of regularization methods is the singular value decomposition (SVD). The difficulty in image processing applications is that the matrices are often very large. In this talk we illustrate the important role played by the SVD when analyzing and solving certain linear systems arising in image restoration. In addition, we consider some approaches that can be used to efficiently (with respect to speed and storage) compute the SVD of structured matrices that arise in these applications.