Optimization and Regularization for Computational Inverse Problems and Applications

Inverse problems, optimization, regularization and scientific computing as a multi-disciplinary subject are introduced in this introductory chapter.

In the present chapter, the basic conceptions of the theory of ill-posed problems and numerical methods for their solving under different a priori information are described. Hadamard’s definition of well-posedness and examples of ill-posed problems are given. Tikhonov’s definition of a regularizing algorithm and classification of mathematical problems are described. The main properties of ill-posed problems are discussed. As an example of a priori information application for constructing regularizing algorithms an operator equation in Hilbert spaces is considered. If it is known that the exact solution belongs to a compact set then the quasisolution method can be used. An error of an approximate solution can be calculated also. If it is known that there is an a priori information concerning sourcewise representability of an exact solution with a completely continuous operator then the method of extending compacts can be applied. There exists a possibility to calculate an a posteriori error of an approximate solution. If strong a priori constraints are not available then the variational approach based on minimization of the Tikhonov functional with a choice of a regularization parameter, e.g., according to the generalized discrepancy principle is recommended. It is formulated by an equivalence of the generalized discrepancy principle and the generalized discrepancy method resulting in a possibility of the generalized discrepancy principle modification for solving incompatible ill-posed problems. Possible approaches for solving nonlinear ill-posed problems and iterative methods are described briefly.

For the last thirty years in the theory of ill-posed problems the direction of investigations was formed that joins with solving the ill-posed problems with a priori information. This is the class of problems, for which, together with the basic equation, additional information about the solution to be found is known, and this information is given in the form of some relations and restrictions that contains important data about the object under consideration. Inclusion of this information into algorithm plays the crucial role in increasing the accuracy of solution of the ill-posed (unstable) problem. It is especially important in the case when solution is not unique, since it allows one to select a solution that corresponds to reality. In this work, the review of methods for solving such problems is presented. Though the author touches all approaches known to him in this scope, the main attention is paid to the methodology that is developed by the Author and based on iterative processes of the Fejér type, which give flexible and effective realization for a wide class of a priori restrictions. In the final section, description of several applied inverse problems with the a priori information and numerical algorithms for their solving are given.

The chapter is a survey on recently proposed technique for parameter identification in partial differential equations. This technique combines natural linearization of an identification problem with the Tikhonov scheme, where the regularization parameter is chosen adaptively by means of the so-called balancing principle. We describe the natural linearization approach and show how it can be treated within the framework of Tikhonov regularization as a problem with noisy operator and noisy data. Then the balancing principle is discussed in the context of such a problem. We demonstrate the performance of proposed technique in some typical parameter identification problems.

The numerical solution of inverse problems using Tikhonov’s regularization methods requires a huge amount of computations in iterative processes. It can employ extrapolation techniques to accelerate the convergence process or to improve accuracy of the regularized solution. This chapter aims to introduce some main extrapolation methods that have been studied for solving linear inverse problems in detail. Our emphasis is to discuss related technical problems, to propose a new extrapolation algorithm based on the Hermitian interpolation and to present results of numerical experiments for showing the merits of extrapolated regularization methods.

In this chapter, we propose a new regularization method for solving a linear operator equation when the operator and right hand term are both known approximately. The advantage of our method is that we just use the information about the error level instead of assuming the reliable bounds of the unknown solution. The algorithms are presented and the numerical simulation results show the efficiency of our method. As an application, we discuss the problem of reconstructing the Neumann-Dirichlet mapping from the discrete Neumann and Dirichlet data. The Neumann-Dirichlet mappings are used widely in the studying of inverse problems for partial differential equations.

The gradient method is one of the most simple methods for solving unconstrained optimization, it has the advantages of being easy to program and suitable for large scale problems. Different step-lengths give different gradient algorithms. In 1988, Barzilai and Borwein gave two interesting choices for the step-length and established superlinearly convergence results for two-dimensional convex quadratic problems. Barzilai and Borwein’s work triggered much research on the gradient method in the past two decades. In this chapter we investigate how the BB method can be further improved. We generalize the convergence result for the gradient method with retards. Our generalization allows more choices for the step-lengths. An intuitive analysis is given on the impact of the step-length for the speed of convergence of the gradient method. We propose a short BB step-length method. Numerical results on random generated problems are given to show that our short step technique can improve the BB method for large scale and ill-conditioned problems, particularly when high accurate solutions are needed.

Conjugate gradient methods are a class of important methods for unconstrained optimization and vary only with a scalar β _k . In this chapter, we analyze general conjugate gradient method using the Wolfe line search and propose a condition on the scalar β _k , which is sufficient for the global convergence. An example is constructed, showing that the condition is also necessary in some sense for the global convergence of general conjugate gradient method. To make better use of the condition, we introduce a new property for conjugate gradient methods. It is shown that many conjugate gradient methods have such property, including the FR, PRP, HS, and DY methods and the FR-PRP, and DY-HS hybrid methods. Consequently, convergence results are gained for these methods under mild assumptions. In addition, an analysis is also given to a new conjugate gradient method, which further demonstrates the usefulness of the condition and the new property. Some discussions about the bound in the hybrid conjugate gradient methods are also given.

In this chapter, we discuss about the full space and subspace methods for ill-posed image restoration problems. Image restoration refers to minimizing the degradation which is caused by sensing environment, say CCD camera misfocus, nonuniform motion, atmospheric aerosols and atmospheric turbulence. For image restoration problems, a key matter is to solve a quadratic programming problem. We study numerical solution methods in full space by limited memory of BFGS method and the subspace trust region method. We develop a novel approach for reducing the cost of sparse matrix-vector multiplication when applying the full space and subspace methods to atmospheric image restoration. Also the projection technique for the regularized convex quadratic functional is developed in the iteration for ensuring nonnegativity. Numerical experiments indicate that these methods are useful for large-scale image restoration problems.

Inverse scattering problems are one of the main research areas in the optimization techniques. The main purpose of inverse scattering problems is to detect the physical properties of an obstacle from some information related to the scattered waves of the obstacle for given incident wave. Generally, if the incident plane waves are given from the finite number of directions, which are indeed the practical situations, there is no uniqueness for reconstructing the obstacle properties such as the boundary shape. In these cases, the optimization techniques can be applied to reconstructing the obstacle approximately. That is, the obstacle shape is approximated by a minimizer of some cost functional which measures the defect between the measurement data of the scattered wave and the computational scattered wave related to the approximate obstacle. Of course, for this optimization problems in infinite dimensional space, some regularizing term should be introduced to the cost functional.

Although these general optimization techniques have been applied widely in the last century, they also suffer from many disadvantages theoretically and numerically. From the theoretical point of view, the lack of uniqueness makes the obtained approximate obstacle from the optimization procedure ambiguous, namely, we do not know whether or not the computational result indeed approximates the true one. From the numerical respects, such an optimization procedure needs to solve the direct scattering problem at each iteration step, which entails huge time cost. Moreover, to get the convergence of the iteration, a good initial guess is required. Even if in the case of convergence, the approximate sequence generally approaches to some local minimizer. These shortcomings of the direct optimizations used in inverse scattering problems cause some problems for the numerical reconstruction of the obstacles.

In recent years, some modified version of optimization algorithms based on the potential methods for inverse scattering problems are proposed, in the sense that the direct problems are not required to solve in the iteration procedures. On the other hand, some new schemes combining the advantages of optimizations with the exact reconstruction formulas have been developed for inverse scattering problems. In this chapter, we give an overview on these two directions. We begin with a brief introduction to the physical background to acoustic scattering problems as well as some well-known inverse scattering models. Then we review some classical and recently developed inversion methods for detecting the information about the unknown scatterer from a knowledge of the far-field pattern u ^∞ for one or several incident plane waves. For each method, the basic idea is described, and some main results are presented. To test their validity, the numerical implementation of all inversion methods needs to be studied. So we finally focus on the numerical realizations of these existing methods, pointing out the main difficulties encountered in numerical realization. In addition, the advantages and disadvantages of these methods are also analyzed.

There are considered ill-posed inverse problems which arise in molecular spectroscopy data processing. The main of them, the general inverse problem of structural chemistry for free molecules is nonlinear inverse problem of molecular vibrations. The modern view on this problem joins the study of molecular force field and geometry restoration using all available experimental data (vibrational (IR and Raman) spectroscopy, electron diffraction, etc.), a priori constraints and ab initio quantum mechanical calculations. The second inverse problem of determination of intermolecular potential from the second virial coefficient is also closely connected with molecular structure investigation.

Also there are presented stable numerical methods, based on Tikhonov’s regularization method for computing the force fields of polyatomic molecules from experimental data as well as some numerical illustrations using real data.

To estimate structural parameters and spectral component signatures of Earth surface cover type, quantitative remote sensing seems to be an appropriate way to deal with these problems. Since the real physical system that couples the atmosphere with the land surface is very complicated and should be continuous, sometimes it requires comprehensive parameters to describe such a system, so any practical physical model can only be approximated by a model which includes only a limited number of the most important parameters that capture the major variation of the real system.

The pivot problem for quantitative remote sensing is the inversion. Inverse problems are typically ill-posed. The ill-posed nature is characterized by (C1) the solution may not exist; (C2) the dimension of the solution space may be infinite; (C3) the solution is not continuous with the variation of the observed signals. These issues exist for all quantitative remote sensing inverse problems. For example, when sampling is poor, i.e., there are very few observations, or directions are poorly located, the inversion process would be underdetermined, which leads to the large condition number of the normalized systems and the significant noise propagation. Hence (C2) and (C3) would be the chief difficulties for quantitative remote sensing inversion.

This chapter will address the theory and methods from the viewpoint that the quantitative remote sensing inverse problems can be represented by kernel-based operator equations.