{'fraction_non_alphanumeric': 0.038572541115030466, 'fraction_numerical': 0.012345961793943837, 'mean_word_length': 4.224243149455546, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Statistical mechanics of image restoration and error-correcting codes

We develop a statistical-mechanical formulation for image restoration and error-correcting codes. These problems are shown to be equivalent to the Ising spin glass with ferromagnetic bias under random external fields. We prove that the quality of restoration/decoding is maximized at a specific set of parameter values determined by the source and channel properties. For image restoration in mean-field system a line of optimal performance is shown to exist in the parameter space. These results are illustrated by solving exactly the infinite-range model. The solutions enable us to determine how precisely one should estimate unknown parameters. Monte Carlo simulations are carried out to see how far the conclusions from the infinite-range model are applicable to the more realistic two-dimensional case in image restoration.


I. INTRODUCTION
Information is usually transmitted through noisy channels. One therefore has to devise a method to retrieve the original information from the output of a noisy channel. Let us suppose that the original information is represented as a sequence of bits. The idea of errorcorrecting codes [1] is to introduce redundancy into the bit sequence to be fed into the noisy channel, so that this additional information is helpful to retrieve (decode) the original bit sequence from the corrupted output of the channel. An example is the parity-check code in which the parities of appropriate blocks of bits are sent through the channel in addition to the original source sequence. The receiver checks the consistency between the information bits and parity bits and takes appropriate actions if an inconsistency is found.
The problem of image restoration [2] is similar to the error-correcting code, in the sense that an image represented by a set of pixels (corresponding to the bit sequence in errorcorrecting codes) is corrupted by noise and the receiver tries to retrieve the original image out of the noisy, corrupted one. A major difference is that in the image restoration problem, one is usually given only the corrupted image, not other additional redundant information. One thus relies on some a priori knowledge about images in general to remove noise. A simple instance is the assumption of smoothness in real-world images; for example, one may wish to suppress an isolated white pixel among black ones because such a configuration is likely to have been caused by noise rather than to have existed in the original image of the real world.
A general strategy common in error-correcting codes and image restoration is to use the Bayes formula on the a posteriori probability (posterior) of an output sequence, given the input sequence. One then often accepts the sequence (image) which maximizes the posterior as the decoded/restored result. This method is called the maximum a posteriori probability (MAP) estimate.
Sourlas [3] pointed out that the problem of error-correcting codes can be written in terms of the theory of spin glasses. The idea is first to represent the bit sequence as an Ising spin configuration and then to form a set of exchange interactions as the products of appropriate sets of spins, which can be considered as a generalization of the Mattis model of spin glasses [4]. The set of interactions, instead of the spin configuration, is fed into the channel, in which noise causes the signs of interactions to flip with some probability. At the receiving end, one forms the Ising model Hamiltonian from the corrupted exchange interactions, the ground state of which is accepted as the decoded information. This process is equivalent to the MAP estimate. Sourlas used this formulation to show that there exists a family of codes which are asymptotically error-free and saturate the bound on the code rate (the number of information bits divided by the number of transmitted bits) derived by Shannon [5].
Ruján [6] subsequently proposed to carry out the decoding procedure not at the ground state but at a finite temperature corresponding to the Nishimori temperature found in the theory of spin glasses [7]. The finite-temperature decoding is effective because the correct original bit sequence has a higher energy than the ground state if the exchange interactions are corrupted and thus are deviated from the Mattis type. His proposal was supported by one of the authors [8] who proved that when the decoding temperature is varied, the average error per bit in the decoded sequence becomes smallest at the Nishimori temperature. Sourlas [9] used the Bayes formula to rederive the finite-temperature decoding of Ruján under more general conditions. A recent development along this line is the contribution by Kabashima and Saad [10] who used a diluted many-spin interacting model of spin glasses to show that this system asymptotically saturates the Shannon bound with the code rate kept finite.
Analogy with statistical mechanics has also been a useful guide to develop a variety of techniques in the image restoration problem [11][12][13]. Most of the efforts, however, have been devoted to the development of efficient methods to search for the ground state of appropriate statistical mechanical systems (the MAP restoration) using simulated annealing [11], meanfield annealing [12] or the cluster variation methods [13]. An interesting exception is the work of Pryce and Bruce [2] who pointed out that under a certain criterion, the MAP estimate is outperformed by the thresholded posterior mean (TPM) estimate [14], which is actually equivalent to a finite-temperature decoding method.
It is therefore natural to formulate the problems of error-correcting codes and image restoration within a unified theoretical framework and apply various techniques developed in the theory of disordered systems like spin glasses and the random-field Ising model. In this paper, we study the choice of parameters for optimal performance with this approach. For illustration, we introduce the infinite-range model, by which it becomes possible to discuss analytically the parameter dependence of the performance.
In Sec. II we give the basic formulation of the problem for the binary symmetric and Gaussian channels. The posterior for the output of a noisy channel is interpreted as the Boltzmann factor of a statistical-mechanical system, namely the Ising spin glass with ferromagnetic bias under random fields. Important quantities in the theory of errorcorrecting codes and image restoration are represented in terms of thermal averages of the Ising model at finite temperatures. We derive an upper bound on the overlap between the decoded/restored result with the original sequence/image using the statistical-mechanical formulation. The problem of image restoration is treated in Sec. III in detail where we derive a line of optimal performance in mean-field systems, find the exact solution for the infiniterange model, and present simulation results for the two-dimensional case. The infinite-range model is shown to work as a good guide to the description of qualitative behavior of the two-dimensional problem. Explicit examples of images are displayed to clarify what happens under various conditions. The problem of error-correcting codes is analyzed in Sec. IV. We solve the infinite-range model explicitly using the replica method. Compact expressions of the overlap and other order parameters enable us to discuss various aspects of error-correcting codes quantitatively. The final section is devoted to discussions.

II. GENERAL FORMULATION
Consider an information source which generates a bit sequence represented by a set of Ising spins {ξ i }, where ξ i = ±1 and i = 1, · · · , N, with the source probability P s ({ξ i }) (the prior). The sequence {ξ i } is coded as the products of r spins J 0 i 1 ···ir = ξ i 1 · · · ξ ir for appropriately chosen sets of indices {i 1 · · · i r }. The Sourlas code [3] is equivalent to the infinite-range model in which all possible combinations of r sites are chosen from N sites. In general we consider several different r's in a single code, such as in the case of the Viterbi code [6] which has r = 2 and 3. The problem of image restoration can be regarded as a special case of r = 1, in which case J i corresponds to the state of the ith pixel in the corrupted (noisy) image. A "bit" in error-correcting codes should thus be identified with a "pixel" in image restoration, a "bit sequence" with an "image", and "decoding" with "restoration" whenever necessary in the following arguments.
When the signal is transmitted through a noisy channel, the output consists of the sets {J i 1 ···ir } for various values of r, which are the corrupted versions of J 0 i 1 ···ir . Two kinds of noisy channels are considered in this paper: the binary symmetric channel (BSC) and the Gaussian channel (GC).

A. Binary symmetric channel
In the binary symmetric channel, the output J i 1 ···ir is equal to ∓J 0 i 1 ···ir with probabilities p r and 1 − p r respectively, where p r is the error rate of the BSC for transmission of J 0 i 1 ···ir . The error probabilities of flipping the signal +1 to −1 and −1 to +1 are the same. This output probability can be written in a compact form as where β r = 0 if the code in consideration does not include the set {J i 1 ···ir } and otherwise. The second summation in the exponent of Eq. (1) extends over an appropriate set of the indices (i 1 , · · · , i r ), the choice of which determines the type of the code, and N r is the number of terms appearing in this summation. Note that N r = 0 if β r = 0. Each index i may appear in a number of r-spin terms in the exponential expression; the number of times of appearance is called the valency z r . The procedure of decoding/restoration proceeds as follows. According to the Bayes formula and Eq. (1), the posterior probability that the source sequence is {σ}, given the output {J}, is proportional to the Boltzmann factor of an Ising model multiplied by the prior: Note that we use the symbol {σ} for the decoded/restored result which is in general different from the original set {ξ}. For simplicity, we restrict ourselves to the case of a single non-vanishing β r (≡ β J ) with r ≥ 2 and β 1 (≡ β τ ). Following the convention of separating the interaction terms and local field terms in statistical mechanics, we write J i as τ i for r = 1 terms, and Eq. (3) becomes Similarly, we will use p J , p τ to represent p r , p 1 respectively. It often happens that the receiver at the end of the noisy channel does not have precise information on β J , β τ or P s . One has to estimate these so-called hyperparameters, which is one of the major topics in this field (see for example [15]). If the receiver estimates β for β J and h for β τ , and uses a model (guess) P m ({σ}) of the source prior P s ({ξ}), then the mean of the posterior distribution of σ i is equal to the thermal average where the Hamiltonian is given by One then regards sgn σ i as the ith bit of the decoded/restored information with finite β and h in the finite-temperature process, or with their ratio kept finite when their magnitudes approach infinity in the MAP method.
In the context of image restoration, one often considers patterns with non-trivial structures. Therefore they are assumed to be generated by a non-uniform source prior P s ({ξ}). When we do not have any information on the source prior, we have to represent our a priori knowledge on general images in the model prior P m ({ξ}). A natural choice often used as a generic form of the prior is the Boltzmann factor of the ferromagnetic Ising model where Z(β m ) is the partition function at the inverse temperature β m , ij represents interacting sites, and z is the valency of each site. The summation usually extends over neighboring sites on a two-dimensional lattice. This prior is natural because it suppresses different states of neighboring sites, enhancing a smooth structure. In this paper we consider priors with general connections.
To proceed further, we have to assume some explicit form of the source prior P s ({ξ}). To develop a general theory, we adopt the Boltzmann factor of the Ising model which has the same form as Eq. (7) but with a different inverse temperature. Thus the original images correspond to snapshots of equilibrium Monte Carlo simulations of the ferromagnetic Ising model. Comparison of Eqs. (4), (5) and (6) implies that the Bayes result (4) specifies the inverse temperature β to β J , the field strength h to β τ and the model prior P m to P s . Nevertheless it is useful to keep β, h and P m as adjustable parameters and investigate how precisely we should estimate the hyperparameters and tune the adjustable parameters for optimal decoding/restoration. Our statistical-mechanical formulation is particularly useful to investigate this problem both qualitatively and quantitatively.
The decoding/restoration procedure reduces to the method of Ruján in the situation of error-correcting codes (i.e. h = 0 and P s = P m =const) when β = β J , in which case the noise temperature 1/β J is equal to the Nishimori temperature, which is known to play an interesting role in the theory of spin glasses [7]. Pryce and Bruce [2] called the same method the TPM in the image restoration situation, in which one sets h = β τ in the absence of the interaction term in Eq. (6).
The finite-temperature method with appropriate parameters (β = β J , h = β τ , P m = P s ) is known to give the sequence of most probable bits both in error-correcting codes and image restoration [2,8,9,14]. The MAP estimate, on the other hand, chooses the sequence which gives the largest value of the posterior (4), corresponding to the ground state of the Ising model. The result of finite-temperature decoding/restoration gives a lower value of the posterior (4) than the MAP result. However, there appear very many states with almost the same value of the posterior if we generate finite-temperature states by Eq. (4), and thus after weighted by the number of such similar states, finite-temperature states outweigh the MAP counterpart. In other words, if we take into account the entropy effects, the finite-temperature method becomes the natural choice. This corresponds to the free-energy minimization rather than the energy minimization as in usual statistical-mechanical systems at finite temperatures.

B. Gaussian channel
In the Gaussian channel, the output J i 1 ···ir is a Gaussian random variable with appropriate mean a r J 0 i 1 ···ir and variance J 2 r . Hence for a given sequence {ξ i }, the Gaussian channel is given as where, again following the statistical mechanics convention, we have used J 0 , J, a, τ to represent a r , J r , a 1 , J 1 respectively. Similarity of Eqs. (4) and (10) implies that the output probability distribution for BSC and GC can be written in the same form, where β J = J 0 /J 2 and β τ = a/τ 2 for GC. F r and F 1 are functions independent of {ξ i }. For BSC, For GC,

C. Overlap
The most important quantity in the present problem is the overlap of the decoded/restored bit sgn σ i and the original bit ξ i averaged over the output probability. We may express this overlap as This expression (16) should be further averaged over the possible sequences of source bits represented by the prior P s ({ξ}). The final expression of the overlap M is then The dependence of M on β, h and P m exists in the thermal average σ i . The average of any other quantity f (σ) is calculated similarly: The outer brackets [· · ·] in Eq. (18) denote the averages over {ξ}, {J} and {τ } with the weight P s P out .
The following inequality on the overlap is very useful in discussions on the decoding/restoration performance, and the proof is outlined in Appendix A: This inequality means that the overlap becomes largest when β = β J , h = β τ and P m = P s . In this sense the performance of the MAP corresponding to the limit β, h → ∞ cannot exceed that of the finite-temperature decoding/restoration at β J and β τ . This inequality was known in error-correcting codes [8,9], and equivalent statements were given also in the image restoration problem [14] although not in the explicit form given here. One of the contributions of the present paper is that we have generalized the inequalities to the case where two different types of terms are present, one with r ≥ 2 and the other with r = 1. Similar inequalities can be easily derived for the more general case of several different r's in Eq. (1).

III. IMAGE RESTORATION
A. Line of optimal performance in mean-field models In conventional image restoration problems, the output of the transmission channel only consists of the set of pixels {τ i } (corrupted image in the usual sense), but not the set of exchange interactions {J ij } (the corrupted version of {J 0 ij = ξ i ξ j }). In this case the following inequality applies to images with extensive valency. Mean-field results are exact when each pixel interacts extensively with other pixels in the source and model prior distributions (8) and (7). These include the infinite-range model, in which all pixels interact with each other, its randomly diluted version with infinite valency in the thermodynamic limit (N → ∞), or finite-dimensional models with long-range interactions. Mean-field approximations also work well for finite but large valencies when the temperature is not too low. The following inequality derived in Appendix B is useful in finding the optimal restoration performance, for arbitrary values of s > 0. Here m 0 and m are the (self-averaging) thermal averages of the source pixels ξ i and model pixels σ i respectively, for those sites i which interact with a given site, say site 1, which however is removed from the thermal process. Note that the derivation only makes use of the self-averaging nature of the mean-field quantities, and does not rely on any connection topology of the sites (except for the mean-field requirement). No particular techniques such as the replica method are employed. Hence the inequality applies to mean-field systems in general.
Since m 0 and m are functions of β s , β m and h, Eq. (20) defines the line of optimal performance in the space of h and β m : In particular, when s = 1, h = β τ , β m = β s and m = m 0 , Eq. (21) reduces to the point of optimal performance predicted by Eq. (19). On the other hand, if the field h is different from β τ , then the source and model temperatures have to be rescaled by the magnetization of the respective systems. When s → ∞, we obtain the zero-temperature restoration, i.e. the MAP estimate. Hence the MAP estimate is also optimal, provided that the correct ratio of h/β m is used (although this choice can only be determined iteratively).

B. The infinite-range model
Let us now suppose that we are given the corrupted version of the set of pixels {τ i } and, in addition, the exchange interactions {J ij }, the latter being the corrupted version of the Mattis-type interactions {ξ i ξ j }. The additional contribution from the exchange term enables us to formulate the image restoration and error-correcting code problems on the same footing and at the same time investigate the extent to which the additional information {J ij } enhances the performance. The restoration process is carried out at the inverse temperature β and the field h using Eqs. (5) and (6) with r = 2. Though the inequalities (19) and (20) give a bound on the overlap M, they do not reveal the explicit dependence of M on the parameters β, h, β m and β τ , which is necessary for studying the tolerance of the restoration results against uncertainties in the estimation of the hyperparameters. The infinite-range model serves as a useful test ground for this purpose. Of course the infinite-range model is not useful for restoration of a real two-dimensional image since all pixels are neighbors of each other and hence the spatial structure is ignored. However, we may reasonably expect from experience in statistical mechanics of many-body systems that the behavior of macroscopic quantities (such as the overlap M) of realistic problems are at least qualitatively well predicted by the infinite-range model.
We therefore suppose that the summation in the prior (8) extends over all possible pairs of sites and similarly for the model prior P m . We also assume that the two-body exchange interactions for all pairs of sites are included in the given information, or equivalently Eq. (6) with r = 2 and the summation extending over all pairs of sites, and that the channel is Gaussian.
We thus have to evaluate the following averaged replicated partition function The standard replica calculation with the replica symmetric ansatz [16] leads to the expressions of the order parameters: where The overlap is a function of these order parameters An example of the dependence of M on the model prior temperature T m ≡ β −1 m is shown in Fig. 1 for conventional image restoration (without the exchange term, β = 0). The parameters are T s = 0.9 and a = τ = 1. The usual practice in image restoration is to use a Hamiltonian with a fixed ratio of h/β m , and then to use β m as an adjustable parameter for simulated annealing. Hence we consider the behavior as a function of β m when h/β m is kept constant to the optimal value β τ /β s (the curve marked 'Opt h'), to 0.9 times the optimal value ('Opt*0.9'), or to 1.1 times the optimal value ('Opt*1.1'). In the curve marked 'h = 1', h itself is kept constant to 1. The ground-state limit T m → 0 gives the MAP restoration. The maximum is at T m = 0.9(= T s ) for the optimal choice of h = 1(= β τ β m /β s ), as predicted by Eq. (19). This figure indicates that one does not have to approach the zero temperature limit as in MAP in the search of the best restored image by such a process as simulated annealing.
For the curves Opt*0.9 and Opt*1.1, the location of the largest M is not at T m = 0.9. However, the maximum value coincides with the best value as predicted by Eq. (20). This fact can easily be verified by differentiating Eq. (26) with respect to β m . The optimal parameter is β m = β s m 0 h/β τ m, agreeing with Eq. (21).
The line of optimal performance in the space of T m and h is obtained by combining Eqs. (21) and (24), yielding When h → 0, T m approaches the limit (T m ) max = 1 + aβ τ /β s . This is the temperature above which the maximum overlap cannot be achieved.
In the low temperature limit, h → ∞ and the ratio h/β m approaches a constant Hence the maximum overlap is achievable for any temperature below (T m ) max . The zerotemperature restoration (the MAP estimate) is potentially as optimal as the finite temperature procedure determined by Eq. (19) in mean-field systems, although it can only be achieved at the correct ratio h/β m given by Eq. (28). Figure 2 shows the line of optimal performance for the parameters used in Fig. 1. The hyperbolas T m h = 0.9, 0.81 and 0.99 correspond to the lines of operation Opt h, Opt*0.9 and Opt*1.1 of Fig. 1 respectively. Where they intersect the line of optimal performance, the overlap reaches a maximum.
In realistic image restoration, the precision in the estimation of hyperparameters is an important issue. One can see that the three lines of operation follow the general trend of the optimal curve. Hence they are much more error-tolerant than other curves, say, h = 1. Furthermore, if a line of operation intersects the line of optimal performance with a small angle between the tangents, then the overlap M is very near to its optimum for a wide range of parameters along the line of operation, and the procedure has a high tolerance for parameter uncertainties. Among the three lines of operation in Fig. 2, T m h = 0.99 has the highest tolerance. In fact, if one uses T m h = 1.0267 according to Eq. (28), then it has the widest range of tolerance in the low temperature region. Figure 3 shows the effects of introducing the exchange term. It depicts M as a function of the inverse exchange temperature β in Eq. (23) with the other parameters set to the optimal values T s = T m = 0.9, a = h = 1.0 and with J 0 = 2.0 in the unit J = τ = 1. The axis β = 0 corresponds to the optimum point T m = 0.9 of Fig. 1. The introduction of the exchange term is seen to sharply improve the performance. The maximum of M is located at β = 2.0(= J 0 ) as required, and M stays close to the maximum value beyond β = 2.0. The combination of the ideas of error-correcting code (the β-term) and image restoration (the β m and h terms) leads to a remarkable improvement in the quality of restored image.
Two remarks are in order in relation to Fig. 3. First, the amount of information conveyed by the set {J ij } may seem exceedingly large compared to that by {τ i } because the number of elements in the former set is N(N − 1)/2 while it is N in the latter. This fact may be mistaken as the reason of the improved result in Fig. 3 for finite β. However, since each J ij (∼ O(1/ √ N )) is much smaller in magnitude than τ i (∼ O(1)), the contribution of each J ij is very small. Such a situation is characteristic of the infinite-range model. The equivalent situation in the finite-dimensional case is that the number of exchange interactions is of the same order as that of sites. For example, there are 2N nearest neighbor interactions for N sites on the square lattice. Therefore, the increase in the amount of information by the introduction of the set {J ij } should be of order unity, not infinitely large. Secondly, as the exchange term is seen to increase the overlap very sharply, even the information from a fraction of the exchange interactions may be useful to improve the restoration result. For example, one may choose a small fraction of pairs of sites (either randomly or not) and use the corrupted, noisy version of these exchange interactions to restore the image to obtain a better result. This method should be useful when the bandwidth (the amount of information to be carried by the channel) is limited.

C. Simulations
It is difficult to investigate the more realistic case of two-dimensional images by analytical methods. We therefore have carried out Monte Carlo simulations to confirm the qualitative pictures obtained by the exact solution of the infinite-range model. To generate the source image, we have used the prior (8) with T s = 2.15 which is slightly lower than the critical point 2.269 of the two-dimensional Ising model on the square lattice. The error probability was set to p J = p τ = 0.1 for BSC, corresponding to β J = β τ = 1.0986 by Eq. (2). Averages over 5 samples (Fig. 4, size 400 × 400) or 10 samples (Fig. 5, size 100 × 100) were taken at each data point. Figure 4 shows the overlap M as a function of T m when β = 0 and h is chosen so that h/β m is fixed to the optimum value β τ /β s . The overlap should have a maximum at T m = T s = 2.15 in Fig. 4 according to Eq. (19) although it is not very clearly seen due to statistical uncertainties. It is at least true that M does not change significantly below T m = 2.15. It is therefore unnecessary to lower the temperature than T s = 2.15 to obtain a better result.
The effects of exchange interactions have been taken into account in Fig. 5 where T m and h are fixed to the optimal values 2.15(= T s ) and 1.0986(=β τ ) respectively. The overlap is seen to increase quite significantly as a function of β. The axis β = 0 corresponds to the optimal point of T m = 2.15 in Fig. 4. The overlap reaches its maximum at around β = β J = 1.0986 as it should and decreases slowly as β is further increased.
Respectively, Figs. 4 and 5 are qualitatively similar to Opt h in Fig. 1, and Fig. 3, for the infinite-range model, implying the usefulness of the infinite-range model as an approximation of the two-dimensional problem.
Let us show an explicit example of the actual image restoration. Figure 6 represents the situations of Figs. 4 and 5 with the size 100 × 100. We have generated a pattern by the prior (8) with T s = 2.15 to obtain (a) and have added noise with probability p τ = 0.1, resulting in (b) [17]. To obtain the restored images (c) and (d) only the corrupted image (b) was used without extra information on exchange interactions (β = 0). Restoration was tried at temperatures T m = 0.5 for (c) resulting in M = 0.888 and at T m = 2.15 for (d) with M = 0.892. It is clearly recognized that the optimal temperature T m = 2.15 (d) has a better restored image than (c). The low-temperature process (c) suppresses small structures which were actually present in the original image. The low temperature result is close to the MAP estimate (T m = 0) which would further suppress small structures. It should be noticed that the difference in M in these two restored results (c) and (d) is very small (which is also seen in Fig. 4) but the intuitive impressions on similarity to the original image (a) are rather different. The reason is that the small structures do not contribute significantly to the value of M although such structures have strong influence on intuitive impressions. Therefore we should keep in mind that the overlap M alone does not represent all aspects of the quality of restored images.
We next consider the effects of the additional information of exchange interactions among nearest neighbors. The same corrupted image (b) has been used to obtain the restored image (e). The parameters T m , h and β were fixed to the optimal values 2.15(= T s ), 1.0986(= β τ ) and 1.0986(= β J ) respectively, resulting in an overlap of M = 0.986. Fine structures are remarkably well restored in the result (e). Thus the additional information of exchange interactions is very effective to restore images faithfully.

IV. ERROR-CORRECTING CODES
The infinite-range model has the same significance in error-correcting codes as in the image restoration problem; namely, an exactly solvable model which describes more realistic situations at least qualitatively. The difference is that we consider a general value of r in error-correcting codes, instead of only r = 2 in the case of image restoration. We therefore calculate the overlap M and related quantities explicitly assuming that the set {i 1 , · · · , i r } in Eq. (6) extends over all possible combinations of indices.
We consider the Gaussian channel, and the source and model distributions are both assumed to be uniform, P s = P m = 2 −N , as is customary in the theory of error-correcting codes [3,6,[8][9][10]. ¿From Eqs. (17) and (9), the overlap is given by The normalizations of J and j 0 are different from Eq. (9) and follow the convention of the infinite-range model of spin glasses so that the limit r → ∞ yields meaningful results [16].
We may change the signs of integration variables in Eq. (29) appropriately (J i 1 ···ir → J i 1 ···ir ξ i i · · · ξ ir , τ i → τ i ξ i , σ i → σ i ξ i ) which allows us to drop ξ's from the integrand (the ferromagnetic gauge). Then the problem becomes the standard mean-field theory of spin glasses with r-spin interactions under external random fields, and we can apply the wellestablished replica method [16]. Standard replica calculations under the replica-symmetric (RS) ansatz lead to the following set of equations of state for the spin glass order parameter q, ferromagnetic order parameter m and the overlap M: where Dx is the Gaussian measure and The corresponding free energy is The present system with j 0 = 0 is known to have a spin glass phase with a singlestep replica-symmetry breaking (1RSB) at a low temperature when r ≥ 3 [18]. This spin glass phase with 1RSB is replaced by a full-step replica-symmetry breaking at a still lower temperature. It is therefore necessary to study replica-symmetry breaking solutions following Refs. [18,19]. The stability condition of the RS solution (the AT line) is found to be The free energy with 1RSB (h = 0 for simplicity) is where The self-consistent equations for the order parameters are obtained by extremization of Eq.
We do not write out the explicit form for the equation of x 0 because the formula is not very instructive. The AT stability of this 1RSB solution is The phase diagram in the case of r = 3 and h = 0 is shown in Fig. 7. Retrieval is not possible unless the ferromagnetic phase is at least locally stable. The hatched region satisfies this condition. The ferromagnetic phase is stable in the replica symmetric ansatz for sufficiently strong bias j 0 and high temperature T . For T /J above and below 0.651, it is respectively replaced by the paramagnetic and spin glass phases through first-order phase transitions when j 0 decreases. These three phases coexist at the triple point (TP). The ferromagnetic phase remains metastable down to the spinodal line shown as a dotted curve. The replica symmetric solution of the ferromagnetic phase becomes unstable below the AT line (35) shown by the dash-dotted curve.
Also shown in Fig. 7 are the spin glass phases, which exist at lower values of the bias j 0 . Spin glass with a single-step replica symmetry breaking is stable for T /J between 0.651 and 0.240. At lower temperatures, it is replaced by a full replica symmetry breaking spin glass phase.
Investigation of the properties of the mixed phase M (such as distinction between 1RSB and full RSB), as well as the deatils of the spin glass phase, are interesting future problems, which we do not pursue here since they are not directly relevant to our problem of errorcorrecting codes around the optimum temperature T = J 2 /2j 0 shown dashed in Fig. 7. We have not shown the structure of the phase diagram at very low temperatures for this reason. Figure 8 shows the dependence of the overlap M on the decoding temperature T = β −1 with r = 3 and j 0 /J = 0.77. The line j 0 /J = 0.77 lies slightly to the right of the triple point TP in Fig. 7. The maximum performance is achieved at T = J 2 /2j 0 = 0.649. This result is consistent with the argument in Sec. II C: if we repeat the proof of Eq. (19) with the external field neglected and P s = P m = 2 −N , we obtain the inequality M(β) ≤ M(2j 0 /J 2 ).
The optimum condition T = J 2 /2j 0 coincides with the Nishimori line shown dashed in the phase diagram (Fig. 7). This curve crosses the phase boundary and the spinodal line at the points where j 0 takes the smallest values in the ferromagnetic stable and metastable phases respectively (marked by black and white circles). It can be shown that the spinodal line, the Nishimori line and the AT line are concurrent for any values of r. Hence the AT line terminates at the triple point. Since the Nishimori line lies in the replica symmetric phase, the replica symmetric argument would be sufficient to clarify the behavior of the overlap around its maximum. The lower temperature properties, including the possibility of a reentrant spin glass phase, may be affected by replica symmetry breaking. Figure 9 shows the dependence of M on the random field strength h at the optimal temperature T = 0.649 with r = 3, j 0 /J = 0.77 and a = 1. The axis h = 0 corresponds to the conventional Sourlas code without the field term, which is the maximum point in Fig.  8. It is observed that the overlap M increases sharply as the field is introduced, reaching the maximum at h = 1, in agreement with the theoretical prediction h opt = a/τ 2 .

V. DISCUSSIONS
We have formulated the problems of image restoration and error-correcting codes in a unified framework using statistical mechanics. We have derived an upper bound on the overlap M between the restored/decoded image/sequence and the original image/sequence. The maximum of M is achieved when the restoring/decoding temperature and field strength match the corresponding temperature and field strength characteristic of the source and channel properties. This result comes as a natural generalization of the previously known inequalities for image restoration [14] and error-correcting codes [8]. The formulation and the proof of the inequality have a formal similarity to the theory of spin glasses, in particular the one using gauge symmetry [7]. One should note however that we have not used gauge symmetry in the present paper. The variables {ξ i } in Eq. (18), playing a central role in the spin glass theory [7], come naturally in the present problem whereas they emerged as a result of gauge transformation in the spin glass theory.
The infinite-range model has been solved exactly both in the image restoration and error-correcting code situations. The results made it possible to reveal the dependence of the overlap M on various parameters. Simulations for image restoration have confirmed that the results for the infinite-range model remain qualitatively valid in two dimensions.
For image restoration in mean-field systems, we have found a line of optimal performance along which the overlap M takes the same maximum value. The line contains the point of optimal performance predicted by the inequality (19), but extends also to the zerotemperature limit. This indicates that optimal (or quasi-optimal) performance is far more accessible than previously thought. It remains to study the extent to which the picture is applicable to finite-dimensional systems where the mean-field theory is only approximate. In this respect, it is interesting to note that a ridge of nearly optimal overlap has already been observed in early literature, such as Fig. 2 of [14] and Fig. 8 of [2]. Naturally, one is led to expect that a narrow but extended region of optimal (or near-optimal) performance spans the parameter space.
By comparing the optimal line and the operation lines on which h/β m is kept constant, we have studied the tolerance towards uncertainties in parameter estimation. Apparently the zero-temperature restoration (the MAP estimate) is most robust. Furthermore, if the MAP estimate is approached by simulated annealing, it may be more effective to consider rescaling the field strength while lowering the temperature at the same time.
However, we have a few remarks of caution about the MAP estimate. (a) The zerotemperature restoration is optimal only when the correct ratio h/β m is used, which can only be found self-consistently in realistic situations; if the incorrect ratio is used, the performance will be sub-optimal. (b) The existence of the line of optimal performance in finite-dimensional systems remains an open issue. Simulations in two dimensions seem to show that the MAP estimate is sub-optimal, although most likely it is still nearly optimal. On the other hand, the optimal point predicted by Eq. (19) is guaranteed to be the best in general cases. (c) The present result applies to the equilibrium state of the system, and the dynamics remains an open issue. It may happen that the approach to equilibrium at a low temperature is much slower, or is more prone to being trapped by local minima.
We have also considered the inclusion of exchange interactions as extra information in image restoration. Explicit examples of images in two dimensions show that the fine structures are remarkably well restored. We remark that the exchange interactions have some similarities with "line processes", which has been proposed to improve the quality of images [11]. If the line variables were quenched, they are equivalent to binary and multiple interactions among neighboring sites. However, a major difference is that the line variables are dynamical in the process of image restoration, whereas the exchange interactions considered here are quenched.
A comment is in order on the amount of information carried by the channel of the infiniterange model. The signal amplitude of the exchange term in Eq. (29) is j 0 r!/N r−1 . The channel noise causes fluctuations in the output with the standard deviation J(r!/N r−1 ) 1/2 , which is much larger than the signal itself when N ≫ 1. This corresponds to an extremely low signal-to-noise ratio, yet the output still contains significant information of the original message. This demonstrates the power of the infinite-range decoding scheme in extremely noisy situations, although in practice such extremes do not occur frequently.
Finally, we mention briefly the idea of selective freezing [20]. The Ising spins keep moving under thermal agitation when we employ the process of finite-temperature restoration. Some spins have smaller thermal fluctuations than the others, resulting in larger local magnetic moments. It may thus be interesting to fix (freeze) those relatively stable spins to ±1 according to the sign of σ i and repeat the finite-temperature decoding/restoration process for the other less stable degrees of freedom. We call this idea the selective freezing, which turns out to enhance tolerance against uncertainties in parameter estimation. The details will be presented in a forthcoming paper [21].

ACKNOWLEDGMENTS
One of the authors (H. N.) thanks Department of Physics, Hong Kong University of Science and Technology, for hospitality. He is also indebted to Prof. Kazuyuki Tanaka for a comprehensive tutorial on the theory of image restoration and to Prof. Shun-ichi Amari for useful comments. We thank Dr. Domenico Carlucci for an observation leading to the discovery of the line of optimal performance, Dr. David Saad for drawing our attention to Ref. [2], and Prof. David Sherrington for discussions. This work is partially supported by a grant from the Research Grant Council of Hong Kong.

APPENDIX A: THE INEQUALITY FOR GENERAL DECODING AND RESTORATION
To prove the inequality (19), we first note that the argument of the summation in the definition (17) is bounded by its absolute value: where |sgn σ i | has been replaced with 1. Using the identity |x| = x sgnx, we get .

(A2)
Thus the right hand side can be interpreted as the average of the product of ξ i and sgn σ i at the optimal parameter values β = β J , h = β τ and P m = P s , yielding Eq. (19).

APPENDIX B: THE INEQUALITY FOR MEAN-FIELD IMAGE RESTORATION
To derive the inequality (20), we start with the definition (17). Substituting Eqs. (11), (8) and (7) we obtain, for i = 1 in the average, In the exponential argument of the Boltzmann factor containing {ξ}, ξ 1 only appears in the expression z −1 β s 1j ξ 1 ξ j + β τ τ 1 ξ 1 . Hence if we multiply and divide this expression by the partition function of {ξ i } excluding site 1, we have where · · · H(βs,βτ ) \1 represents the thermal average taken over the Hamiltonian with inverse temperature β s and random field strength β τ , excluding site 1. Similar arguments can be applied to the argument of the sign function in (B1), yielding For mean-field systems, 1j η j and 1j σ j are self-averaging quantities [22], and the thermal average of the hyperbolic sine functions can be replaced by a single function of the thermal averaged argument. Thus M(h, β m ) reduces to For mean-field systems with large valency, the averaging over the neighbors of site 1 reduces to the disordered average. Consider [ η j \1 ], which is the thermal and disordered average of η j taken over the Hamiltonian H(β s , β τ ) \1 , After canceling terms in the denominator and numerator, we arrive at which reduces to [ ξ j \1 ] = m 0 , namely the magnetization in the prior distribution. Similarly, [ σ j \1 ] = m, which is the magnetization in the model distribution. Substituting these results, and using the normalization of the probability The rest of the proof is similar to Appendix A. Noting that the integrand of τ is bounded by its absolute value, we have M(h, β m ) ≤ 2Z(β s ) \1 Z(β s ) dτ F 1 (τ ) sinh (β s m 0 + β τ τ ) sgn (β s m 0 + β τ τ ) .