The temperature–emissivity separation (TES) problem bedevils any attempt to extract spectral information from remote sensing in the thermal infrared. Numerous methods have been proposed for handling TES.18.104.22.168.22.214.171.124.10.11.12.13.14.15.16.–17 In this letter we investigate the application of simulated annealing to a MAP solution of the TES problem. The approach is an extension of earlier work on Bayesian TES.3,5 Simulated annealing cannot give a unique solution to this problem, but we shall show that the average of a large number of simulated annealing TES solutions converges almost surely to a unique TES estimate.
Simulated annealing has traditionally been regarded as a preferred method of global solution for combinatorial optimization problems, such as the traveling salesman. In this letter, we adapt the Metropolis algorithm1819.–20 to an optimization problem that lacks a unique global optimal solution: TES. The underdetermined TES problem, notoriously,126.96.36.199.188.8.131.52.10.11.12.13.14.15.16.–17 has a continuous infinity of solutions that yield the identical optimum value for any cost or payoff function one cares to choose.
A key part of any simulated annealing algorithm is the choice of an annealing schedule that causes the posterior probabilities to transition from nearly uniform to very tight in such a way as to evade the risk of the MAP search from converging to a local, rather than a global, optimum. Factors that enter into the choice of the annealing schedule are described in Refs. 19 and 20. In what follows, we shall stipulate that a suitable annealing schedule has been supplied and shall concern ourselves with the existence of a solution to the simulated annealing TES problem.
Simulated Annealing and the Temperature–Emissivity Separation Problem
Metropolis Algorithm Search for MAP Solution
Suppose that we have in our possession prior knowledge that a target patch, forming part of the lower boundary of the atmosphere, is composed of an intimate mixture of spectral endmembers at temperature . The label may, depending upon context, refer to the wavenumber or to a finite number of wavenumber-averaged spectral bands.
For the development that follows, it is desirable to restate some of the main definitions used in spectral mixing theory using language borrowed from topology.21,22 Let distinct points in be chosen so that the vectors are linearly independent. Then the set
A spectral mixture amounts to a mapping into a geometric -simplex, whose vertices have spectral endmembers at a stipulated temperature for “coefficients.” A mixture with stipulated weights corresponds to the vector
In the case , a familiar example of a 2-simplex is the ternary diagram used to classify phreatic igneous rocks. The double three-component diagram used in the quartz, alkali feldspar, plagioclase, feldspathoid classification23 scheme is a union of two 2-simplices, and is an example of a “simplicial complex.”
For present purposes, the ’th pure endmember for the ’th trial is assigned to the ’th vertex of
It is necessary to account for surface temperature in a somewhat different way. Let the minimum and maximum physically admissible surface temperatures be and , respectively. Then the temperature of our target patch is given as
We score trial mixtures by that we most wish to maximize; the posterior probability for the observed spectral radiance to originate from a surface patch with temperature and spectral emissivity . A standard argument3,5 gives the posterior probability in terms of a MAXENT estimator24 Equation (15) is evaluated with the aid of the prior probability for the surface to be at temperature and has spectral emissivity , given available knowledge 5
Each trial is thus scored according to the joint posterior probability for observed spectral radiance to result from surface temperature and spectral emissivity18,20
We now examine the question of convergence. Corresponding to the sequence of -simplices, , as the number of trials increases without bound is a sequence of trials with associated loci .
As a closed bounded subset of , is a compactum. Therefore, as , the sequence of trials contains a convergent subsequence, whatever the value of . Correspondingly, the sequence of posterior probabilities likewise has a convergent subsequence that, by construction, tends to the maximum value of the posterior probability, i.e., to an MAP solution for and .
Consider the map given by
The mapping of Eq. (19) generates a sequence of trials for which is nondecreasing. By Zorn’s lemma, the set comprised of all admissible trials has at least one element with a maximal value of . We note that maximizing also maximizes the information-theoretic entropy by Eq. (12). According to the usual statement of the second law, the state of maximum entropy is one of thermodynamic equilibrium. We may, in view of the thermodynamic analogy underlying the Metropolis algorithm, therefore call the limit Eq. (22) an equilibrium point.
This nomenclature is attractive for another reason. In the limit, Eq. (22) amounts to a fixed point of Eq. (19). Ordinary fixed-point theorems are inapplicable to Eq. (19) because it is neither continuous nor semicontinuous: It can map an open set to a singleton . We can, however, adapt the celebrated construction introduced by Nash25 to prove the existence of a fixed (equilibrium) point of an equivalent self-mapping.
In fact, we shall prove a somewhat stronger result. Consider
Equation (24) is continuous and maps points into a convex compactum . A fixed point
The mapping Eq. (19) generates a sequence of trials for which is nondecreasing and gives the maximal value of in the limit, while Eq. (27) demonstrates the existence of a trial for which cannot be made greater. In view of the ensemble-theoretic freedom to choose , we may identify the limit in Eq. (22) with the fixed point in Eq. (27). Therefore, a convergent subsequence of annealing trials exists that tends to an equilibrium point. Moreover, Eq. (27) demonstrates that the annealing search can, in principle, find in a finite number of trials. We conclude that, granted a suitable annealing schedule, there exists at least one convergent sequence of trials that tends to MAP surface temperature and spectral emissivity estimates consistent with observed spectral radiances .
Sequential compactness guarantees the existence of a convergent subsequence of trials. In practice, we must expect that there will be more than one such sequence. The nonuniqueness of solutions to the TES problem suggests that there will be a continuous infinity of possible trials that yield any stipulated value for the posterior probability. In any realizable search strategy, however, we need only contend with a countable set of convergent subsequences. Among these, there will be one for which the posterior probability is greatest. Its limit will be the closest approach to the MAP solution achieved by simulated annealing. In the nature of things, more than one convergent subsequence may be expected to exist that yields this same maximal estimate, with the same asymptotic annealing temperature . We ignore all subsequences except these maximal ones.
In Refs. 5 and 3, expectation values for and over the the posterior probability [Eq. (15)] were shown to give good estimates for physical surface temperatures and emissivities. We claim that the mean of a large number of subsequences that converge to the limiting MAP value will tend to the expectation values for and with respect to Eq. (15).
The MAXENT estimator is constructed from the posterior probability of noise power in a spectral bin. For the sake of simplicity, we assume identical noise power in each bin. (This assumption is inessential and may be relaxed.) A fully annealed MAP estimate may be thought of as an individual Bernoulli trial drawn from the likelihood function for . By construction, all such trials are independent and identically distributed with bounded expectation values. Moments over Eq. (15) are bounded despite bad behavior of the Jeffreys prior at , because of the rapid decay of the exponentials away from the MAP solution, as L’Hôpital’s rule demonstrates.
Reliance on the mixing hypothesis in the form given by Eq. (10), however, brings with it the concern that the relevant covariance matrix might be singular. In that event, the strong law of large numbers26,27 ensures
To the extent that the estimator used in the simulated annealing search is zero-mean error, we conclude the estimates yield accurate values for the physical values of and . As the spectral weights , lying as they do between zero and unity, possess bounded moments, this conclusion applies to the limiting mean values of as well.
The practical utility of the mathematical development in this letter may be questioned. We briefly address two possible concerns.
A legitimate concern is that the spectral emissivity of natural ground covers in the wild will seldom be known to the level of accuracy found in Ref. 28. While true in general, this concern has not dissuaded other researchers from relying upon spectral unmixing.
While convergence of the algorithm has been proved to our satisfaction, we have no equally satisfactory estimates of the rate of convergence, with the consequence that the choice of annealing schedule remains a matter of trial and error. In response to this concern, the availability of massively parallel computation made possible by the ready availability of cheap graphics processing unit arrays means that massive processing requirements need not preclude the use of a resource-hungry algorithm if that algorithm can provide a performance not attainable by other approaches.
In this letter, the Metropolis algorithm has been adapted to formulate a simulated annealing approach to the TES problem for a spectral mixture. We have presented a proof of convergence of simulated annealing searches for candidate MAP TES solutions. We have additionally shown that the average of a large number of these candidate MAP solutions converges almost surely to a unique estimate of surface temperature and spectral emissivity that, given a forward model leading to an unbiassed estimator for and , closely approximates the true values of these quantities.
The simulated annealing approach to TES by spectral unmixing offers something that other TES algorithms do not. By construction, it gives (in the limit) the unique best estimate in an MAP sense, for the remote determination of surface temperature and spectral emissivity of a patch of ground that is known to be comprised of a spectral mixture of a stipulated set of spectral end members.
Support from the Aerospace Corporation Technical Investment Program under USAF Contract No. FA8802-14-C-0001 is acknowledged.