View source for Regularization method

A method for constructing approximate solutions of [[Ill-posed problems|ill-posed problems]] in the following way: As approximate solution of an ill-posed problem (also called an incorrectly-posed problem) one takes the values of a regularizing operator with regard to the approximate nature of the initial data.

For the sake of being specific, consider the problem of finding the solution of a functional equation of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809301.png" />, in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809302.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809303.png" /> are elements of metric spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809304.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809305.png" /> with distance functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809306.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809307.png" />, respectively. If, for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809308.png" /> is a [[Completely-continuous operator|completely-continuous operator]], then the solution of such an equation need not be stable with respect to small changes of the right-hand side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r0809309.png" />. Suppose that, instead of the exact values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093010.png" /> of the initial data, approximations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093011.png" /> are given. In these circumstances one can only ask for approximations to the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093012.png" /> of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093013.png" />. As an approximate solution of an ill-posed problem of this type, with approximate initial data <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093014.png" />, one cannot take an exact solution of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093015.png" />, since such a solution need not exist, and even if it does, it need not be stable with respect to small changes of the initial data, so that such a  "solution"  may not admit a physical interpretation. In what follows, it is assumed for simplicity that only the right-hand side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093016.png" /> is approximate, and that the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093017.png" /> is specified exactly.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093018.png" /> be a bound on the deviation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093019.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093020.png" />, that is, on the distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093021.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093022.png" /> be a given class of possible solutions (comparison models). It is natural to search for approximate solutions of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093023.png" /> among the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093024.png" /> compatible with the initial data, that is, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093025.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093026.png" /> be the set of all such elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093027.png" />. If, in the chosen class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093028.png" /> of possible solutions, there are no elements (for example, functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093029.png" />) compatible with the initial data, then this means that the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093030.png" /> have an over-simplified (too rough) structure. In this case it is necessary to extend <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093031.png" /> by taking, if necessary, an increasing sequences of classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093032.png" /> until a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093033.png" /> is reached that contains elements (for example, functions) that are compatible with the initial data.

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093034.png" /> is not empty, then it may contain elements (functions) that are essentially different from one another. In such cases, the single requirement of compatibility of a possible solution with the initial data cannot serve as the only criterion for finding a well-defined approximate solution of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093035.png" />, as there are insufficient grounds for the choice of an approximate solution from among the compatible elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093036.png" />.

For stable solutions to be well-defined, one needs a certain principle for selecting solutions compatible with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093037.png" />. The formulation of this usually varies in accordance with the nature of the problem. Such a selection can be made, for example, on the principle of choosing an element (functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093038.png" />) that has minimal complexity. The notion of complexity of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093039.png" /> can be formalized, for example, using complexity functionals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093040.png" /> — continuous, non-negative functionals satisfying certain special requirements (see [[#References|[1]]]). As a measure of the complexity of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093041.png" /> one takes the value of the functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093042.png" />. Thus, if the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093043.png" /> are continuous functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093044.png" /> on an interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093045.png" /> and belong to the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093046.png" />, then one can take the complexity functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093047.png" /> to be

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093048.png" /></td> </tr></table>

The search for approximate solutions of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093049.png" /> among the simplest elements (functions) that are compatible with the initial data leads to the problem of finding an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093050.png" /> that minimizes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093051.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093052.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093053.png" /> is a linear operator and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093054.png" /> does not have local minima in its domain of definition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093055.png" />, then this problem can be reduced to that (see [[#References|[1]]] for some details) of finding an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093056.png" /> in the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093057.png" /> that minimizes the functional

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093058.png" /></td> </tr></table>

The value of the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093059.png" /> (the regularization parameter) must be chosen in accordance with the level of error in the initial data. For example, it can be defined in terms of discrepancy, that is, by the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093060.png" />, for a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093061.png" />. But there are other ways of determining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093062.png" /> (see [[#References|[1]]]). Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093063.png" /> may depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093064.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093066.png" />. The element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093067.png" /> is then taken as an approximate solution of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093068.png" />. This is also one of the forms of the regularization method developed in [[#References|[2]]], [[#References|[3]]]. In a similar way one can formulate approximate solutions of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093069.png" /> in case both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093070.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093071.png" /> are approximately given. In this case a functional of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093072.png" /> is minimized (see [[#References|[1]]], for example). There are other possible forms of the regularization method, and applications to other classes of problems (see [[#References|[1]]]). Regularization methods have also been developed for solving non-linear problems (see [[#References|[1]]], [[#References|[4]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.N. Tikhonov,   V.I. [V.I. Arsenin] Arsenine,   "Solution of ill-posed problems" , Wiley  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.N. Tikhonov,   "Solution of incorrectly formulated problems and the regularization method"  ''Soviet Math. Dokl.'' , '''4''' :  4  (1963)  pp. 1035–1038  ''Dokl. Akad. Nauk SSSR'' , '''151''' :  3  (1963)  pp. 501–504</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.N. Tikhonov,   "Regularization of incorrectly posed problems"  ''Soviet Math. Dokl.'' , '''4''' :  6  (1963)  pp. 1624–1627  ''Dokl. Akad. Nauk SSSR'' , '''153''' :  1  (1963)  pp. 49–52</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  M.M. [M.M. Lavrent'ev] Lavrentiev,   "Some improperly posed problems of mathematical physics" , Springer  (1967)  (Translated from Russian)</TD></TR></table>



====Comments====
For other regularization methods and their convergence properties see (the editorial comments to) [[Ill-posed problems|ill-posed problems]]. That article also contains a discussion of  "inverse problems"  arising in various applications giving rise to ill-posed problems, and many references. The spectral-theoretic methods discussed there also include some iterative methods. Another iterative method that can be considered as a regularization method is the conjugate gradient method (cf. [[Conjugate gradients, method of|Conjugate gradients, method of]]); it is discussed from this point of view in the articles by H. Brakhage and L. Louis in [[#References|[a2]]] (see also [[#References|[a6]]]). Convergence and convergence rates for Tikhonov regularization of non-linear ill-posed problems are considered in some papers in Volume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080930/r08093073.png" /> (1989) of the journal  "Inverse Problems" , which in general contains many articles about regularization methods.

A different approach to regularization is based on statistical considerations (see [[#References|[a1]]], [[#References|[a5]]]) and is rooted in the method of ridge regression, [[#References|[a4]]]. A well-known parameter choice strategy for statistical regularization is generalized cross-validation (see e.g. the article by G. Wahba in [[#References|[a2]]] and the references quoted there).

For the use of reproducing-kernel Hilbert spaces in regularization see [[#References|[a3]]] and [[#References|[a7]]]. A practical comparison of various regularization methods is made in [[#References|[a8]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Bertero,   G. Viano,   "On probabilistic methods for the solution of improperly posed problems"  ''Boll. Un. Mat. Ital.'' , '''15-B'''  (1978)  pp. 483–508</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H.W. Engl (ed.)  C.W. Groetsch (ed.) , ''Inverse and ill-posed problems'' , Acad. Press  (1987)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Hilgers,   "On the equivalence of regularization and certain reproducing kernel Hilbert space approaches for solving first kind problems"  ''SIAM J. Numer. Anal.'' , '''13'''  (1976)  pp. 172–184</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Hoerl,   R. Kennard,   "Ridge regression"  ''Technometrics'' , '''12'''  (1970)  pp. 55–82</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B. Hofmann,   "Regularization for applied inverse and ill-posed problems" , Teubner  (1986)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A.K. Louis,   "Inverse und schlecht gestellte Probleme" , Teubner  (1989)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  M.Z. Nashed,   G. Wahba,   "Convergence rates of approximate least squares solutions of linear integral and operator equations of the first kind"  ''Math. Comp.'' , '''28'''  (1974)  pp. 69–80</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J. Varah,   "A practical examination of some numerical methods for linear discrete ill-posed problems"  ''SIAM Rev.'' , '''21'''  (1979)  pp. 100–111</TD></TR></table>