You are here

Discrete Inverse Problems: Insight and Algorithms

Christian Hansen
Publication Date: 
Number of Pages: 
Fundamentals of Algorithms
[Reviewed by
John D. Cook
, on

Discrete Inverse Problems by Per Christian Hansen is concerned with the problem of computing the function f(t) that solves the integral equation

\int_0^1 K(s, t)\, f(t) \,dt = g(s)

This equation is known as the “Fredholm integral equation of the first kind.” The “forward” problem is to compute the function g(s) given the kernel K(s,t) and the function f(t). The more challenging inverse problem is to find f(t) given K(s,t) and g(s). The discrete problems studied in the book are not intrinsically discrete but rather are discretized forms of the continuous Fredhom problem.

The subtitle of Hansen’s book is “Insight and Algorithms.” True to the claim implicit in the subtitle, the book’s emphasis is evenly divided between exposition and algorithms. The book tells a story from beginning to end. Each chapter ends with a section entitled “The Story So Far” which recaps the progression of the book to that point. The narrative emphasis is not limited to these sections, but these sections emphasize the author’s intention to tell a story.

Inverse problems are inherently difficult because tiny changes in the input (e.g. due to finite numerical precision) can cause enormous changes in the solution. Smoothing kernels K(s,t) become “roughening” kernels when problems are inverted. In order to find practical solutions to inverse problems some sort of regularization is necessary. A major theme in the area of inverse problems, and in Hansen’s book in particular, is algorithms for regularization. Hansen summarizes

… what we would like is an efficient, robust, and reliable method for computing the regularization parameter from the given data,which does not require the computation of the SVD (which is infeasible for large problems) or any human inspection of the plot. Unfortunately, such a method has yet to be found …

Inverse problems arise in many practical applications. The book presents some of these applications, such as image deblurring and tomography. Because inverse problems are common in application, matters of scale, efficiency, and robustness are important. Dicrete Inverse Problems addresses these concerns as well as more purely mathematical issues. Hansen does not presume to exhaustively address discrete inverse problems in a book of only about 200 pages. However, he does give a thorough if brief introduction.

John D. Cook is a research statistician at M. D. Anderson Cancer Center and blogs daily at The Endeavour.

List of Symbols;
Chapter 1: Introduction and Motivation;
Chapter 2: Meet the Fredholm Integral Equation of the First Kind;
Chapter 3: Getting to Business: Discretizations of Linear Inverse Problems;
Chapter 4: Computational Aspects: Regularization Methods;
Chapter 5: Getting Serious: Choosing the Regularization Parameter;
Chapter 6: Toward Real-World Problems: Iterative Regularization;
Chapter 7: Regularization Methods at Work: Solving Real Problems;
Chapter 8: Beyond the 2-Norm: The Use of Discrete Smoothing Norms;
Appendix A: Linear Algebra Stuff;
Appendix B: Symmetric Toeplitz-Plus-Hankel Matrices and the DCT;
Appendix C: Early Work on “Tikhonov Regularization”;