818 Chapter 18.Integral Equations and Inverse Theory (Don't let this notation mislead you into inverting the full matrix W(z)+AS.You only need to solve for some y the linear system (W(z)+AS).y =R,and then substitute y into both the numerators and denominators of 18.6.12 or 18.6.13.) Equations(18.6.12)and (18.6.13)have a completely different character from the linearly regularized solutions to(18.5.7)and(18.5.8).The vectors and matrices in (18.6.12)all have size N,the number of measurements.There is no discretization of the underlying variable z,so M does not come into play at all.One solves a different N x N set of linear equations for each desired value of z.By contrast,in(18.5.8), one solves an M x M linear set,but only once.In general,the computational burden of repeatedly solving linear systems makes the Backus-Gilbert method unsuitable 81 for other than one-dimensional problems. How does one choose A within the Backus-Gilbert scheme?As already mentioned,you can (in some cases should)make the choice before you see any actual data.For a given trial value of A.and for a sequence of x's,use equation(18.6.12) to calculate q();then use equation(18.6.6)to plot the resolution functions 6(,' as a function of x'.These plots will exhibit the amplitude with which different underlying values z'contribute to the point ()of your estimate.For the same value of A,also plot the function Var()]using equation (18.6.8).(You need an estimate of your measurement covariance matrix for this. As you change A you will see very explicitly the trade-off between resolution and stability.Pick the value that meets your needs.You can even choose A to be a function of A =A(x),in equations (18.6.12)and (18.6.13),should you desire to do so.(This is one benefit of solving a separate set of equations for each z.)For the chosen value or values of A,you now have a quantitative understanding of your 三兰号∽6 inverse solution procedure.This can prove invaluable if-once you are processing OF SCIENTIFIC real data-you need to judge whether a particular feature,a spike or jump for example,is genuine,and/or is actually resolved.The Backus-Gilbert method has found particular success among geophysicists,who use it to obtain information about the structure of the Earth(e.g.,density run with depth)from seismic travel time data 、复公 CITED REFERENCES AND FURTHER READING: Backus,G.E.,and Gilbert,F.1968,Geophysical Journal of the Royal Astronomical Society, vol.16,pp.169-205.I1) Numerica 10621 Backus,G.E..and Gilbert,F.1970,Philosophical Transactions of the Royal Society of London 431 A,vol.266,pp.123-192.2 Recipes Parker,R.L.1977,Annual Review of Earth and Planetary Science,vol.5,pp.35-64.[3] Loredo,T.J.,and Epstein,R.I.1989,Astrophysical Journal,vol.336,pp.896-919.[4] (outside Software. 18.7 Maximum Entropy Image Restoration Above.we commented that the association of certain inversion methodsbreak with Bayesian arguments is more historical accident than intellectual imperative. Maximum entropy methods,so-called,are notorious in this regard;to summarize these methods without some,at least introductory,Bayesian invocations would be to serve a steak without the sizzle,or a sundae without the cherry.We should
818 Chapter 18. Integral Equations and Inverse Theory Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). (Don’t let this notation mislead you into inverting the full matrix W(x) + λS. You only need to solve for some y the linear system (W(x) + λS) · y = R, and then substitute y into both the numerators and denominators of 18.6.12 or 18.6.13.) Equations (18.6.12) and (18.6.13) have a completely different character from the linearly regularized solutions to (18.5.7) and (18.5.8). The vectors and matrices in (18.6.12) all have size N, the number of measurements. There is no discretization of the underlying variable x, so M does not come into play at all. One solves a different N × N set of linear equations for each desired value of x. By contrast, in (18.5.8), one solves an M ×M linear set, but only once. In general, the computational burden of repeatedly solving linear systems makes the Backus-Gilbert method unsuitable for other than one-dimensional problems. How does one choose λ within the Backus-Gilbert scheme? As already mentioned, you can (in some cases should) make the choice before you see any actual data. For a given trial value of λ, and for a sequence of x’s, use equation (18.6.12) to calculate q(x); then use equation (18.6.6) to plot the resolution functions δ (x, x ) as a function of x . These plots will exhibit the amplitude with which different underlying values x contribute to the point u(x) of your estimate. For the same value of λ, also plot the function Var[u(x)] using equation (18.6.8). (You need an estimate of your measurement covariance matrix for this.) As you change λ you will see very explicitly the trade-off between resolution and stability. Pick the value that meets your needs. You can even choose λ to be a function of x, λ = λ(x), in equations (18.6.12) and (18.6.13), should you desire to do so. (This is one benefit of solving a separate set of equations for each x.) For the chosen value or values of λ, you now have a quantitative understanding of your inverse solution procedure. This can prove invaluable if — once you are processing real data — you need to judge whether a particular feature, a spike or jump for example, is genuine, and/or is actually resolved. The Backus-Gilbert method has found particular success among geophysicists, who use it to obtain information about the structure of the Earth (e.g., density run with depth) from seismic travel time data. CITED REFERENCES AND FURTHER READING: Backus, G.E., and Gilbert, F. 1968, Geophysical Journal of the Royal Astronomical Society, vol. 16, pp. 169–205. [1] Backus, G.E., and Gilbert, F. 1970, Philosophical Transactions of the Royal Society of London A, vol. 266, pp. 123–192. [2] Parker, R.L. 1977, Annual Review of Earth and Planetary Science, vol. 5, pp. 35–64. [3] Loredo, T.J., and Epstein, R.I. 1989, Astrophysical Journal, vol. 336, pp. 896–919. [4] 18.7 Maximum Entropy Image Restoration Above, we commented that the association of certain inversion methodsbreak with Bayesian arguments is more historical accident than intellectual imperative. Maximum entropy methods, so-called, are notorious in this regard; to summarize these methods without some, at least introductory, Bayesian invocations would be to serve a steak without the sizzle, or a sundae without the cherry. We should
18.7 Maximum Entropy Image Restoration 819 also comment in passing that the connection between maximum entropy inversion methods,considered here,and maximum entropy spectral estimation,discussed in $13.7,is rather abstract.For practical purposes the two techniques,though both named maximum entropy method or MEM,are unrelated. Bayes'Theorem,which follows from the standard axioms of probability,relates the conditional probabilities of two events,say A and B: Prob(AIB)=Prob(A)Prob(BA) (18.7.1) Prob(B) Here Prob(A B)is the probability of A given that B has occurred,and similarly for Prob(BA),while Prob(A)and Prob(B)are unconditional probabilities. 超君 "Bayesians"(so-called)adopt a broader interpretation of probabilities than do so-called "frequentists."To a Bayesian,P(A|B)is a measure of the degree of plausibility of A(given B)on a scale ranging from zero to one.In this broader view, ICAL A and B need not be repeatable events;they can be propositions or hypotheses. The equations of probability theory then become a set of consistent rules for RECIPES conducting inference [1,2].Since plausibility is itself always conditioned on some, perhaps unarticulated,set of assumptions,all Bayesian probabilities are viewed as 9 conditional on some collective background information 7. Suppose H is some hypothesis.Even before there exist any explicit data, a Bayesian can assign to H some degree of plausibility Prob(HI),called the "Bayesian prior.Now,when some data Di comes along,Bayes theorem tells how to reassess the plausibility of H, Prob(HDI)=Prob(HI Prob(D1lHI) Prob(D1|I) (18.7.2) 6 The factor in the numerator on the right of equation(18.7.2)is calculable as the probability of a data set given the hypothesis(compare with"likelihood"in 815.1). The denominator,called the "prior predictive probability"of the data,is in this case merely a normalization constant which can be calculated by the requirement that the probability of all hypotheses should sum to unity.(In other Bayesian contexts, Numerica 10621 the prior predictive probabilities of two qualitatively different models can be used to assess their relative plausibility. 431 If some additional data D2 comes along tomorrow,we can further refine our Recipes estimate of H's probability.as Prob(HDaD)=Prob(HD)Prob(DaD:1) Prob(D2 HDI) (18.7.3) Using the product rule for probabilities,Prob(ABC)=Prob(A|C)Prob(BAC), we find that equations (18.7.2)and (18.7.3)imply naD,D0=naap% (18.7.4) which shows that we would have gotten the same answer if all the data DiD2 had been taken together
18.7 Maximum Entropy Image Restoration 819 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). also comment in passing that the connection between maximum entropy inversion methods, considered here, and maximum entropy spectral estimation, discussed in §13.7, is rather abstract. For practical purposes the two techniques, though both named maximum entropy method or MEM, are unrelated. Bayes’ Theorem, which follows from the standard axioms of probability, relates the conditional probabilities of two events, say A and B: Prob(A|B) = Prob(A) Prob(B|A) Prob(B) (18.7.1) Here Prob(A|B) is the probability of A given that B has occurred, and similarly for Prob(B|A), while Prob(A) and Prob(B) are unconditional probabilities. “Bayesians” (so-called) adopt a broader interpretation of probabilities than do so-called “frequentists.” To a Bayesian, P(A|B) is a measure of the degree of plausibility of A (given B) on a scale ranging from zero to one. In this broader view, A and B need not be repeatable events; they can be propositions or hypotheses. The equations of probability theory then become a set of consistent rules for conducting inference [1,2]. Since plausibility is itself always conditioned on some, perhaps unarticulated, set of assumptions, all Bayesian probabilities are viewed as conditional on some collective background information I. Suppose H is some hypothesis. Even before there exist any explicit data, a Bayesian can assign to H some degree of plausibility Prob(H|I), called the “Bayesian prior.” Now, when some data D1 comes along, Bayes theorem tells how to reassess the plausibility of H, Prob(H|D1I) = Prob(H|I) Prob(D1|HI) Prob(D1|I) (18.7.2) The factor in the numerator on the right of equation (18.7.2) is calculable as the probability of a data set given the hypothesis (compare with “likelihood” in §15.1). The denominator, called the “prior predictive probability” of the data, is in this case merely a normalization constant which can be calculated by the requirement that the probability of all hypotheses should sum to unity. (In other Bayesian contexts, the prior predictive probabilities of two qualitatively different models can be used to assess their relative plausibility.) If some additional data D2 comes along tomorrow, we can further refine our estimate of H’s probability, as Prob(H|D2D1I) = Prob(H|D1I) Prob(D2|HD1I) Prob(D2|D1I) (18.7.3) Using the product rule for probabilities, Prob(AB|C) = Prob(A|C)Prob(B|AC), we find that equations (18.7.2) and (18.7.3) imply Prob(H|D2D1I) = Prob(H|I) Prob(D2D1|HI) Prob(D2D1|I) (18.7.4) which shows that we would have gotten the same answer if all the data D1D2 had been taken together
820 Chapter 18.Integral Equations and Inverse Theory From a Bayesian perspective,inverse problems are inference problems [3,4].The underlying parameter set u is a hypothesis whose probability,given the measured data values c,and the Bayesian prior Prob(uI)can be calculated.We might want to report a single"best"inverse u,the one that maximizes rob(u Prob(ulcI)=Prob(clul) Prob(c|I) (18.7.5) over all possible choices of u.Bayesian analysis also admits the possibility of reporting additional information that characterizes the region of possible u's with high relative probability,the so-called "posterior bubble"in u. 81 The calculation of the probability of the data c,given the hypothesis u proceeds exactly as in the maximum likelihood method.For Gaussian errors,e.g.,it is given by 鱼君 Prob(cul)）=exp(-2X2)△u1△2…△uM (18.7.6) 、三 3 where x2 is calculated from u and c using equation (18.4.9),and the Au's are constant,small ranges of the components of u whose actual magnitude is irrelevant, RECIPES because they do not depend on u (compare equations 15.1.3 and 15.1.4). 9 In maximum likelihood estimation we,in effect,chose the prior Prob(u)to be constant.That was a luxury that we could afford when estimating a small number of parameters from a large amount of data.Here,the number of "parameters" (components of u)is comparable to or larger than the number of measured values (components of c);we need to have a nontrivial prior,Prob(u),to resolve the degeneracy of the solution. 8S孕是g合 In maximum entropy image restoration,that is where entropy comes in.The entropy of a physical system in some macroscopic state,usually denoted S.is the logarithm of the number of microscopically distinct configurations that all have 6 the same macroscopic observables(i.e.,consistent with the observed macroscopic state).Actually,we will find it useful to denote the negative of the entropy,also called the negentropy,by H=-S(a notation that goes back to Boltzmann).In situations where there is reason to believe that the a priori probabilities of the microscopic configurations are all the same (these situations are called ergodic),then the Bayesian prior Prob(u)for a macroscopic state with entropy S is proportional Numerica 10.621 to exp(S)or exp(-H). 43106 MEM uses this concept to assign a prior probability to any given underlying Recipes function u.For example [5-7],suppose that the measurement of luminance in each pixel is quantized to (in some units)an integer value.Let M North U=up (18.7.7) =1 be the total number of luminance quanta in the whole image.Then we can base our "prior"on the notion that each luminance quantum has an equal a priori chance of being in any pixel.(See [8]for a more abstract justification of this idea.)The number of ways of getting a particular configuration u is Ul u2.…!exp 空+(-刃 187.8
820 Chapter 18. Integral Equations and Inverse Theory Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). From a Bayesian perspective, inverse problems are inference problems [3,4]. The underlying parameter set u is a hypothesis whose probability, given the measured data values c, and the Bayesian prior Prob(u|I) can be calculated. We might want to report a single “best” inverse u, the one that maximizes Prob(u|cI) = Prob(c|uI) Prob(u|I) Prob(c|I) (18.7.5) over all possible choices of u. Bayesian analysis also admits the possibility of reporting additional information that characterizes the region of possible u’s with high relative probability, the so-called “posterior bubble” in u. The calculation of the probability of the data c, given the hypothesis u proceeds exactly as in the maximum likelihood method. For Gaussian errors, e.g., it is given by Prob(c|uI) = exp(−1 2 χ2)∆u1∆u2 ··· ∆uM (18.7.6) where χ2 is calculated from u and c using equation (18.4.9), and the ∆u µ’s are constant, small ranges of the components of u whose actual magnitude is irrelevant, because they do not depend on u (compare equations 15.1.3 and 15.1.4). In maximum likelihood estimation we, in effect, chose the prior Prob(u|I) to be constant. That was a luxury that we could afford when estimating a small number of parameters from a large amount of data. Here, the number of “parameters” (components of u) is comparable to or larger than the number of measured values (components of c); we need to have a nontrivial prior, Prob(u|I), to resolve the degeneracy of the solution. In maximum entropy image restoration, that is where entropy comes in. The entropy of a physical system in some macroscopic state, usually denoted S, is the logarithm of the number of microscopically distinct configurations that all have the same macroscopic observables (i.e., consistent with the observed macroscopic state). Actually, we will find it useful to denote the negative of the entropy, also called the negentropy, by H ≡ −S (a notation that goes back to Boltzmann). In situations where there is reason to believe that the a priori probabilities of the microscopic configurations are all the same (these situations are called ergodic), then the Bayesian prior Prob(u|I) for a macroscopic state with entropy S is proportional to exp(S) or exp(−H). MEM uses this concept to assign a prior probability to any given underlying function u. For example [5-7], suppose that the measurement of luminance in each pixel is quantized to (in some units) an integer value. Let U = M µ=1 uµ (18.7.7) be the total number of luminance quanta in the whole image. Then we can base our “prior” on the notion that each luminance quantum has an equal a priori chance of being in any pixel. (See [8] for a more abstract justification of this idea.) The number of ways of getting a particular configuration u is U! u1!u2! ··· uM ! ∝ exp − µ uµ ln(uµ/U) + 1 2 lnU − µ ln uµ (18.7.8)
18.7 Maximum Entropy Image Restoration 821 Here the left side can be understood as the number of distinct orderings of all the luminance quanta,divided by the numbers of equivalent reorderings within each pixel,while the right side follows by Stirling's approximation to the factorial function.Taking the negative of the logarithm,and neglecting terms of order log U in the presence of terms of order U,we get the negentropy M H(u)-∑4uln(uμ/U) (18.7.9) H=1 三 From equations (18.7.5).(18.7.6).and (18.7.9)we now seek to maximize Prob(ue)x exp expf-H(u)l (18.7.10) ICAL or,equivalently, RECIPES M minimize: -in[Pro(1)-Xu+H)回-2Xu+∑ulne,/U 9 =1 (18.7.11) This ought to remind you ofequation(18.4.11),or equation(18.5.6),or in fact any of our previous minimization principles along the lines ofA+AB,where AB=H(u) 日是。会 is a regularizing operator.Where is A?We need to put it in for exactly the reason discussed following equation(18.4.11):Degenerate inversions are likely to be able to achieve unrealistically small values of x2.We need an adjustable parameter to bring x2 into its expected narrow statistical range of N+(2N)1/2.The discussion at the beginning of $18.4 showed that it makes no difference which term we attach the A to.For consistency in notation,we absorb a factor 2 into A and put it on the entropy 家 term.(Another way to see the necessity of an undetermined A factor is to note that it is necessary if our minimization principle is to be invariant under changing the units in which u is quantized,e.g.,if an 8-bit analog-to-digital converter is replaced by a 12-bit one.)We can now also put"hats"back to indicate that this is the procedure Recipes Numerica 10.621 for obtaining our chosen statistical estimator: 43106 (outside Recipes M minimize::A+AB=X2向+H(O=X2向+入>立.ln(位) (18.7.12) =1 North (Formally,we might also add a second Lagrange multiplier AU,to constrain the total intensity U to be constant.) It is not hard to see that the negentropy,H(u),is in fact a regularizing operator, similar to u.(equation 18.4.11)or u.H.u (equation 18.5.6).The following of its properties are noteworthy: 1.When U is held constant,H(u)is minimized for =U/M constant,so it smooths in the sense of trying to achieve a constant solution,similar to equation (18.5.4).The fact that the constant solution is a minimum follows from the fact that the second derivative of u ln u is positive
18.7 Maximum Entropy Image Restoration 821 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). Here the left side can be understood as the number of distinct orderings of all the luminance quanta, divided by the numbers of equivalent reorderings within each pixel, while the right side follows by Stirling’s approximation to the factorial function. Taking the negative of the logarithm, and neglecting terms of order log U in the presence of terms of order U, we get the negentropy H(u) = M µ=1 uµ ln(uµ/U) (18.7.9) From equations (18.7.5), (18.7.6), and (18.7.9) we now seek to maximize Prob(u|c) ∝ exp −1 2 χ2 exp[−H(u)] (18.7.10) or, equivalently, minimize: − ln [ Prob(u|c)]= 1 2 χ2[u] + H(u) = 1 2 χ2[u] + M µ=1 uµ ln(uµ/U) (18.7.11) This ought to remind you of equation (18.4.11), or equation (18.5.6), or in fact any of our previous minimization principles along the lines of A + λB, where λB = H(u) is a regularizing operator. Where is λ? We need to put it in for exactly the reason discussed following equation (18.4.11): Degenerate inversions are likely to be able to achieve unrealistically small values of χ2. We need an adjustable parameter to bring χ2 into its expected narrow statistical range of N ±(2N)1/2. The discussion at the beginning of §18.4 showed that it makes no difference which term we attach the λ to. For consistency in notation, we absorb a factor 2 into λ and put it on the entropy term. (Another way to see the necessity of an undetermined λ factor is to note that it is necessary if our minimization principle is to be invariant under changing the units in which u is quantized, e.g., if an 8-bit analog-to-digital converter is replaced by a 12-bit one.) We can now also put “hats” back to indicate that this is the procedure for obtaining our chosen statistical estimator: minimize: A + λB = χ2[u] + λH(u) = χ2[u] + λ M µ=1 uµ ln(uµ) (18.7.12) (Formally, we might also add a second Lagrange multiplier λ U, to constrain the total intensity U to be constant.) It is not hard to see that the negentropy, H(u), is in fact a regularizing operator, similar to u · u (equation 18.4.11) or u · H · u (equation 18.5.6). The following of its properties are noteworthy: 1. When U is held constant, H(u) is minimized for uµ = U/M = constant, so it smooths in the sense of trying to achieve a constant solution, similar to equation (18.5.4). The fact that the constant solution is a minimum follows from the fact that the second derivative of u ln u is positive.
822 Chapter 18.Integral Equations and Inverse Theory 2.Unlike equation (18.5.4),however,H(u)is local,in the sense that it does not difference neighboring pixels.It simply sums some function f,here f(u)=ulnu (18.7.13) over all pixels;it is invariant,in fact,under a complete scrambling of the pixels in an image.This form implies that H(u)is not seriously increased by the occurrence of a small number of very bright pixels(point sources)embedded in a low-intensity smooth background. 3.H(u)goes to infinite slope as any one pixel goes to zero.This causes it to 8 enforce positivity of the image,without the necessity ofadditional deterministic constraints. 4.The biggest difference between H(u)and the other regularizing operators that we have met is that H(u)is not a quadratic functional of u,so the equations obtained by varying equation(18.7.12)are nonlinear.This fact is itself worthy ICAL of some additional discussion. Nonlinear equations are harder to solve than linear equations.For image RECIPES processing,however,the large number of equations usually dictates an iterative solution procedure,even for linear equations,so the practical effect ofthe nonlinearity is somewhat mitigated.Below,we will summarize some of the methods that are successfully used for MEM inverse problems. For some problems,notably the problem in radio-astronomy of image recovery from an incomplete set of Fourier coefficients,the superior performance of MEM inversion can be,in part,traced to the nonlinearity of H(u).One way to see this [51 9么 is to consider the limit of perfect measurements o:0.In this case the x2 term in the minimization principle(18.7.12)gets replaced by a set of constraints,each with its own Lagrange multiplier,requiring agreement between model and data;that is, minimize: ∑y5-∑n +H() (18.7.14) 写曼⊙ (cf.equation 18.4.7).Setting the formal derivative with respect toto zero gives Numerica 10.621 ∂H =f(位)=∑Rr (18.7.15) 43126 or defining a function G as the inverse function of f', (18.7.16) This solution is only formal,since the Ai's must be found by requiring that equation (18.7.16)satisfy all the constraints built into equation(18.7.14).However,equation (18.7.16)does show the crucial fact that ifG is linear,then the solution ucontains only a linear combination of basis functions Rj corresponding to actual measurements j.This is equivalent to setting unmeasured ci's to zero.Notice that the principal solution obtained from equation (18.4.11)in fact has a linear G
822 Chapter 18. Integral Equations and Inverse Theory Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machinereadable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 2. Unlike equation (18.5.4), however, H(u) is local, in the sense that it does not difference neighboring pixels. It simply sums some function f, here f(u) = u ln u (18.7.13) over all pixels; it is invariant, in fact, under a complete scrambling of the pixels in an image. This form implies that H(u) is not seriously increased by the occurrence of a small number of very bright pixels (point sources) embedded in a low-intensity smooth background. 3. H(u) goes to infinite slope as any one pixel goes to zero. This causes it to enforce positivity of the image, without the necessity of additional deterministic constraints. 4. The biggest difference between H(u) and the other regularizing operators that we have met is that H(u) is not a quadratic functional of u, so the equations obtained by varying equation (18.7.12) are nonlinear. This fact is itself worthy of some additional discussion. Nonlinear equations are harder to solve than linear equations. For image processing, however, the large number of equations usually dictates an iterative solution procedure, even for linear equations, so the practical effect of the nonlinearity is somewhat mitigated. Below, we will summarize some of the methods that are successfully used for MEM inverse problems. For some problems, notably the problem in radio-astronomy of image recovery from an incomplete set of Fourier coefficients, the superior performance of MEM inversion can be, in part, traced to the nonlinearity of H(u). One way to see this [5] is to consider the limit of perfect measurements σi → 0. In this case the χ2 term in the minimization principle (18.7.12) gets replaced by a set of constraints, each with its own Lagrange multiplier, requiring agreement between model and data; that is, minimize: j λj cj − µ Rjµuµ + H(u) (18.7.14) (cf. equation 18.4.7). Setting the formal derivative with respect to u µ to zero gives ∂H ∂uµ = f (uµ) = j λjRjµ (18.7.15) or defining a function G as the inverse function of f , uµ = G j λjRjµ (18.7.16) This solution is only formal, since the λj ’s must be found by requiring that equation (18.7.16) satisfy all the constraints built into equation (18.7.14). However, equation (18.7.16) does show the crucial fact that ifGislinear, then the solution ucontains only a linear combination of basis functions Rjµ corresponding to actual measurements j. This is equivalent to setting unmeasured cj ’s to zero. Notice that the principal solution obtained from equation (18.4.11) in fact has a linear G.