Information Theoretic Proofs of Entropy Power Inequalities Olivier Rioul, Member, IEEE

Abstract-While most useful information theoretic inequalities can be deduced from the basic properties of entropy or mutual information, up to now Shannon's entropy power inequality (EPI) is an exception: Existing information theoretic proofs of the EPI hinge on representations of differential entropy using either Fisher information or minimum mean-square error (MMSE), which are derived from de Bruijn's identity. In this paper, we first present an unified view of these proofs, showing that they share two essential ingredients: 1) a data processing argument applied to a covariancepreserving linear transformation; 2) an integration over a path of a continuous Gaussian perturbation. Using these ingredients, we develop a new and brief proof of the EPI through a mutual information inequality, which replaces Stam and Blachman's Fisher information inequality (FII) and an inequality for MMSE by Guo, Shamai, and Verdú used in earlier proofs. The result has the advantage of being very simple in that it relies only on the basic properties of mutual information. These ideas are then generalized to various extended versions of the EPI: Zamir and Feder's generalized EPI for linear transformations of the random variables, Takano and Johnson's EPI for dependent variables, Liu and Viswanath's covariance-constrained EPI, and Costa's concavity inequality for the entropy power.

Index Terms-Data processing inequality, de Bruijn's identity, differential entropy, divergence, entropy power inequality (EPI), Fisher information, Fisher information inequality (FII), minimum mean-square error (MMSE), mutual information, relative entropy.

I. INTRODUCTION

I N his 1948 historical paper, Shannon proposed the entropy power inequality (EPI) [START_REF] Shannon | A mathematical theory of communication[END_REF]Thm. 15], which asserts that the entropy power of the sum of independent random vectors is at least the sum of their entropy powers; equality holds iff 1 the random vectors are Gaussian with proportional covariances. The EPI is one of the deepest inequalities in information theory, and has a long history. Shannon gave a variational argument [START_REF] Shannon | A mathematical theory of communication[END_REF]App. 6] to show that the entropy of the sum of two independent random vectors of given entropies has a stationary point where the two random vectors are Gaussian with proportional covariance matrices, but this does not exclude the possibility that the stationary point is not a global minimum. Stam [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] credits de Bruijn with a first rigorous proof of the EPI in the case where at most one of the random vectors is not Gaussian, using a relationship between differential entropy and Fisher information Manuscript received April 13, 2007; now known as de Bruijn's identity. A general proof of the EPI is given by Stam [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] (see also Blachman [3]), based on a related Fisher information inequality (FII). Stam's proof is simplified in [START_REF] Dembo | Information theoretic inequalities[END_REF] and [START_REF] Carlen | Entropy production by block variable summation and central limit theorems[END_REF]. Meanwhile, Lieb [START_REF] Lieb | Proof of an entropy conjecture of Wehrl[END_REF] proved the EPI via a strengthened Young's inequality from functional analysis. While Lieb's proof does not use information theoretic arguments, Dembo, Cover, and Thomas [START_REF] Dembo | Information theoretic inequalities[END_REF] showed that it can be recast in a unified proof of the EPI and the Brunn-Minkowski inequality in geometry (see also [START_REF] Costa | On the similarity of the entropy power inequality and the Brunn-Minkowski inequality[END_REF] and [START_REF] Guleryuz | Information-theoretic inequalities for contoured probability distributions[END_REF]), which was included in the textbook by Cover and Thomas [START_REF] Cover | Elements of Information Theory[END_REF]Sec. 17.8]. Recently, Guo, Shamai, and Verdú [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF] found an integral representation of differential entropy using minimum mean-square error (MMSE), which yields another proof of the EPI [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF], [START_REF] Guo | Proof of entropy power inequalities via MMSE[END_REF]. A similar, continuous-time proof via causal MMSE was also proposed by Binia [START_REF] Binia | On divergence-power inequalities[END_REF]. The original information theoretic proofs (by Stam and Blachman, and by Verdú, Guo, and Shamai) were first given for scalar random variables, and then generalized to the vector case either by induction on the dimension [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF], [START_REF] Blachman | The convolution inequality for entropy powers[END_REF] or by extending the required tools [START_REF] Dembo | Information theoretic inequalities[END_REF], [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF].

The EPI is used to bound capacity or rate-distortion regions for certain types of channel or source coding schemes, especially to prove converses of coding theorems in the case where optimality cannot be resolved by Fano's inequality alone. Shannon used the EPI as early as his 1948 paper [START_REF] Shannon | A mathematical theory of communication[END_REF] to bound the capacity of non-Gaussian additive noise channels. Other examples include Bergmans' solution [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF] to the scalar Gaussian broadcast channel problem, generalized to the multiple-input multiple-output (MIMO) case in [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multiple-output broadcast channel[END_REF] and [START_REF] Mohseni | A proof of the converse for the capacity of Gaussian MIMO broadcast channels[END_REF]; Leung-Yan Cheong and Hellman's determination of the secrecy capacity of the Gaussian wire-tap channel [START_REF] Leung-Yan-Cheong | The Gaussian wire-tap channel[END_REF], extended to the multiple access case in [START_REF] Tekin | The Gaussian multiple access wire-tap channel with collective secrecy constraints[END_REF] and [START_REF] Tekin | The Gaussian multiple access wire-tap channel[END_REF]; Costa's solution to the scalar Gaussian interference channel problem [START_REF] Costa | On the Gaussian interference channel[END_REF]; Ozarow's solution to the scalar Gaussian source two-description problem [START_REF] Ozarow | On a source-coding problem with two channels and three receivers[END_REF], extended to multiple descriptions at high resolution in [START_REF] Zamir | Gaussian codes and Shannon bounds for multiple descriptions[END_REF]; and Oohama's determination of the rate-distortion regions for various multiterminal Gaussian source coding schemes [START_REF] Oohama | Gaussian multiterminal source coding[END_REF]- [START_REF] Oohama | Gaussian multiterminal source coding with several side informations at the decoder[END_REF]. It is interesting to note that in all the above applications, the EPI is used only in the case where all but one of the random vectors in the sum are Gaussian. The EPI for general independent random variables, as well as the corresponding FII, also find application in blind source separation and deconvolution in the context of independent component analysis (see, e.g., [START_REF] Donoho | On minimum entropy deconvolution[END_REF]- [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF]), and is instrumental in proving a strong version of the central limit theorem with convergence in relative entropy [START_REF] Carlen | Entropy production by block variable summation and central limit theorems[END_REF], [START_REF] Barron | Entropy and the central limit theorem[END_REF]- [START_REF] Johnson | Fisher information inequalities and the central limit theorem[END_REF].

It appears that the EPI is perhaps the only useful information theoretic inequality that is not proved through basic properties of entropy or mutual information. In this paper, we fill the gap by providing a new proof, with the following nice features: 0018-9448/$26.00 © 2010 IEEE

• it hinges solely on the elementary properties of Shannon's mutual information, sidestepping both Fisher's information and MMSE. Thus, it relies only on the most basic principles of information theory; • it does not require scalar or vector identities such as de Bruijn's identity, nor integral representations of differential entropy; • the vector case is handled just as easily as the scalar case, along the same lines of reasoning; and • it goes with a mutual information inequality (MII), which has its own interest. Before turning to this proof, we make a detailed analysis of the existing information theoretic proofs2 of the EPI. The reasons for this presentation are as follows:

• it gives some idea of the level of difficulty that is required to understand conventional proofs. The new proof presented in this paper is comparatively simpler and shorter; • it focuses on the essential ingredients common to all information theoretic proofs of the EPI, namely data processing inequalities and integration over a path of continuous Gaussian perturbation. This serves as a insightful guide to understand the new proof which uses the same ingredients, though in an more expedient fashion; • it simplifies some of the conventional argumentation and provides intuitive interpretations for the Fisher information and de Bruijn's identity, which have their own interests and applications. In particular, a new, simple proof of a (generalized) de Bruijn's identity, based on a well-known estimation theoretic relationship between relative entropy and Fisher information, is provided; • it offers a unified view of the apparently unrelated existing proofs of the EPI. They do not only share essentials, but can also be seen as variants of the same proof; and • it derives the theoretical tools that are necessary to further discuss the relationship between the various approaches, especially for extended versions of the EPI. The EPI has been generalized in various ways. Costa [START_REF] Costa | A new entropy power inequality[END_REF] (see also [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF]) strengthened the EPI for two random vectors in the case where one of these vectors is Gaussian, by showing that the entropy power is a concave function of the power of the added Gaussian noise. Zamir and Feder [START_REF] Zamir | A generalization of the entropy power inequality with applications[END_REF]- [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF] generalized the scalar EPI by considering the entropy power of an arbitrary linear transformation of the random variables. Takano [START_REF] Takano | The inequalities of Fisher information and entropy power for dependent variables[END_REF] and Johnson [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF] provided conditions under which the original EPI still holds for two dependent variables. Recently, Liu and Viswanath [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF], [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] generalized the EPI by considering a covariance-constrained optimization problem motived by multiterminal coding problems. The ideas in the new proof of the EPI presented in this paper are readily extended to all these situations. Again, in contrast to existing proofs, the obtained proofs rely only on the basic properties of entropy and mutual information. In some cases, further generalizations of the EPI are provided.

The remainder of this paper is organized as follows. We begin with some notations and preliminaries. Section II surveys earlier information theoretic proofs of the EPI and presents a unified view of the proofs. Section III gives the new proof of the EPI, along with some discussions and perspectives. The reader may wish to skip directly to the proof in this section, which does not use the tools presented earlier. Section IV extends the new proof to Zamir and Feder's generalized EPI for arbitrary linear transformations of independent variables. Section V adapts the new proof to the case of dependent random vectors, generalizing the results of Takano and Johnson. Section VI generalizes the new proof to an explicit formulation of Liu and Viswanath's EPI under a covariance constraint, based on the corresponding MII. Section VII gives a proof of the concavity of the entropy power (Costa's EPI) based on the MII, which relies only on the properties of mutual information. Section VIII concludes this paper with some open questions about a recent generalization of the EPI to arbitrary subsets of independent variables [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF]- [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] and a collection of convexity inequalities for linear "gas mixtures."

A. Notations

In this paper, to avoid factors in the derivations, information quantities are measured in nats-we shall use only natural logarithms and exponentials. Random variables or vectors are denoted by upper case letters, and their values denoted by lower case letters. The expectation is taken over the joint distribution of the random variables within the parentheses. The covariance matrix of a random (column) -vector is , and its variance is the trace of the covariance matrix:

. We also use the notation for the variance per component. We say that is white if its covariance matrix is proportional to the identity matrix, and standard if it has unit covariance matrix . With the exception of the conditional mean , which is a function of , all quantities in the form used in this paper imply expectation over , following the usual convention for conditional information quantities. Thus the conditional covariance matrix is , and the conditional variance is , that is, the MMSE in estimating given the observation , achieved by the conditional mean estimator . The diagonal matrix with entries is denoted by . We shall use the partial ordering between real symmetric matrices where means that the difference is positive semidefinite, that is, for any real vector . Clearly implies for any symmetric matrix , and if and are invertible and is positive semidefinite.

Given a function denotes the gradient, a (column) vector of partial derivatives , and denotes the Hessian, a matrix of second partial derivatives . We shall use Landau's notations (a function which is negligible compared to in the neighborhood of some limit value of ) and (a function which is dominated by in that neighborhood).

B. Definition of the Differential Entropy

Let be any random -vector having probability density (with respect to the Lebesgue measure). Its (differential) entropy is defined by [START_REF] Shannon | A mathematical theory of communication[END_REF] provided that this integral exists in the generalized sense-that is, the positive and negative parts of this integral are not both infinite. Thus we may have if and

; and if and , where we have noted and . The differential entropy is not always well defined. Take, for example, for and , and otherwise. In this case it is easy to check that both positive and negative parts of the integral are infinite. In spite of that differential entropy is frequently encountered in the literature, the author was unable to find simple, general conditions under which it is well defined. An exception is [START_REF] Vajda | Theory of Statistical Inference and Information[END_REF] which gives the sufficient condition that is Lebesgue-integrable for any in the range where . The following result may be more useful for practical considerations.

Proposition 1 (Well-Defined Entropy): If is finite, in particular if has finite first or second moments, then is well defined and is such that . Proof: It is sufficient to prove that the positive part of (1) is finite. Let be the Cauchy density defined by [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] Since for all , we have

(3a) (3b) (3c) (3d)
which is finite by assumption.

It is easy to adapt the proof in the particular case where or is finite by letting be an exponential Laplacian or normal Gaussian distribution, respectively. The proof can also be shorten slightly by applying the theorem of Gel'fand-Yaglom-Perez [50, ch. 2] to the relative entropy , which is finite because is absolutely continuous with respect to the measure defined by density .

In the situation of Proposition 1 it is sometimes convenient to extend the definition by setting when does not admit a density with respect to the Lebesgue measure-in particular, when the distribution of has a probability mass assigned to one or more singletons in (see, e.g., [START_REF] Costa | A new entropy power inequality[END_REF] and [51, p. 6]). This convention can be justified by a limiting argument in several cases. Another justification appears in Lemma 1.

C. EPI

The entropy power of a random -vector with (differential) entropy is [START_REF] Shannon | A mathematical theory of communication[END_REF] (4)

In the following, we assume that entropies are well defined, possibly with value or . The scaling properties [START_REF] Carlen | Entropy production by block variable summation and central limit theorems[END_REF] where

, follow from the definitions by a change of variable argument.

Suppose has finite covariances. The non-Gaussianness of is the relative entropy (divergence) with respect to a Gaussian random vector with identical second moments [START_REF] Lieb | Proof of an entropy conjecture of Wehrl[END_REF] where . With the convention of the preceding section, one has if . Since ( 6) is nonnegative and vanishes iff is Gaussian, the entropy power (4) satisfies [START_REF] Costa | On the similarity of the entropy power inequality and the Brunn-Minkowski inequality[END_REF] with equality in the first inequality iff is Gaussian, and in the second iff is white. In particular, is the power of a white Gaussian random vector having the same entropy as .

From these observations, it is easily found that Shannon's EPI can be given several equivalent forms.

Proposition 2 (Equivalent EPIs):

The following inequalities, each stated for finitely many independent random vectors with finite differential entropies, and real-valued coefficients , are equivalent.

(

) (8b) (8c) 8a
where the are independent Gaussian random vectors with proportional covariances (e.g., white) and corresponding entropies . We have presented weighted forms of the inequalities to stress the similarity between (8a)-(8c). Note that by ( 5), the normalization is unnecessary for (8a) and (8b). The proof is given in [START_REF] Dembo | Information theoretic inequalities[END_REF] and is also partly included in [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF] in the scalar case. For completeness we include a short proof 3 .

Proof: That (8a), (8b) are equivalent follows from the equalities . To prove that (8c) is equivalent to (8a) we may assume that . Taking logarithms of both sides of (8a), inequality (8c) follows from the concavity of the logarithm. Conversely, taking exponentials of both sides of (8c), inequality (8a) follows provided that the have equal entropies. But the latter condition is unnecessary because if (8a) is satisfied for the random vectors of equal entropies, then upon modification of the coefficients it is also satisfied for the .

Inequality (8a) is equivalent to the classical formulation of the EPI [START_REF] Shannon | A mathematical theory of communication[END_REF] by virtue of the scaling property [START_REF] Carlen | Entropy production by block variable summation and central limit theorems[END_REF]. Inequality (8b) is implicit in [START_REF] Shannon | A mathematical theory of communication[END_REF]App. 6], where Shannon's line of thought is to show that the entropy of the sum of independent random vectors of given entropies has a minimum where the random vectors are Gaussian with proportional covariance matrices. It was made explicit by Costa and Cover [START_REF] Costa | On the similarity of the entropy power inequality and the Brunn-Minkowski inequality[END_REF]. Inequality (8c) is due to Lieb [START_REF] Lieb | Proof of an entropy conjecture of Wehrl[END_REF] and is especially interesting since all available proofs of the EPI are in fact proofs of this inequality. It can be interpreted as a concavity property of entropy [START_REF] Dembo | Information theoretic inequalities[END_REF] under the covariancepreserving transformation [START_REF] Cover | Elements of Information Theory[END_REF] Interestingly, (8c) is most relevant in several applications of the EPI. Although the preferred form for use in coding applications [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF]- [START_REF] Oohama | Gaussian multiterminal source coding with several side informations at the decoder[END_REF] is , where is Gaussian independent of , Liu and Viswanath [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF], [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] suggest that the EPI's main contribution to multiterminal coding problems is for solving optimization problems of the form , whose solution is easily determined from the convexity inequality (8c) as shown in Section VI. Also, (8c) is especially important for solving blind source separation and deconvolution problems, because it implies that negentropy satisfies the requirements for a "contrast function" [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF] which serves as an objective function to be maximized in such problems [START_REF] Donoho | On minimum entropy deconvolution[END_REF]- [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF]. Finally, the importance of the EPI for proving strong versions of the central limit theorem is through (8c) interpreted as a monotonicity property of entropy for standardized sums of independent variables [START_REF] Barron | Entropy and the central limit theorem[END_REF], [START_REF] Artstein | On the rate of convergence in the entropic central limit theorem[END_REF].

II. EARLIER PROOFS REVISITED

A. Fisher Information Inequalities (FII)

Conventional information theoretic proofs of the EPI use an alternative quantity, the Fisher information (or a disguised version of it), for which the statements corresponding to [START_REF] Guleryuz | Information-theoretic inequalities for contoured probability distributions[END_REF] are easier to prove. The Fisher information matrix of a random -vector with density is [START_REF] Dembo | Information theoretic inequalities[END_REF], [START_REF] Cover | Elements of Information Theory[END_REF] (11)

where the zero-mean random variable (log-derivative of the density) [START_REF] Guo | Proof of entropy power inequalities via MMSE[END_REF] is known as the score. The Fisher information is the trace of ( 11) [START_REF] Binia | On divergence-power inequalities[END_REF] In this and the following subsections, we assume that probability densities are sufficiently smooth with sufficient decay at infinity so that Fisher informations exist, possibly with the value . The scaling properties [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF] follow from the definitions by a change of variable argument.

Note that if has independent entries, then is the diagonal matrix . It is easily seen that the score is a linear function of iff is Gaussian. Therefore, a measure of non-Gaussianness of is the mean-square error of the score with respect to the (linear) score of a Gaussian random vector with identical second moments: [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multiple-output broadcast channel[END_REF] where . Since ( 15) is nonnegative and vanishes iff is Gaussian, the Fisher information (13) satisfies the inequalities [START_REF] Mohseni | A proof of the converse for the capacity of Gaussian MIMO broadcast channels[END_REF] The first inequality (an instance of the Cramér-Rao inequality) holds with equality iff is Gaussian, while the second inequality (a particular case of the Cauchy-Schwarz inequality on the eigenvalues of ) holds with equality iff is white. In particular, is the power of a white Gaussian random vector having the same Fisher information as .

Proposition 3 (Equivalent FIIs): The following inequalities, each stated for finitely many independent random vectors with finite Fisher informations, and real-valued coefficients , are equivalent:

(17a) (17b) (17c)
where the are independent Gaussian random vectors with proportional covariances (e.g., white) and corresponding Fisher informations . There is a striking similarity with Proposition 2. The proof is the same, with the appropriate changes-the convexity of the hyperbolic is used in place of the concavity of the logarithm-and is omitted. Inequality (17c) is due by Stam and its equivalence with (17a) was pointed out to him by de Bruijn [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF]. It can be shown [START_REF] Papathanasiou | Some characteristic properties of the Fisher information matrix via Cacoullos-type inequalities[END_REF], [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] that the above inequalities also hold for positive semidefinite symmetric matrices, where Fisher informations ( 13) are replaced by Fisher information matrices [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF].

Similarly as for (8c), inequality (17c) can be interpreted as a convexity property of Fisher information [START_REF] Dembo | Information theoretic inequalities[END_REF] under the covariance-preserving transformation ( 9), or as a monotonicity property for standardized sums of independent variables [START_REF] Barron | Entropy and the central limit theorem[END_REF], [START_REF] Johnson | Fisher information inequalities and the central limit theorem[END_REF].

It implies that the Fisher information satisfies [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF], and therefore, can be used as a contrast function in deconvolution problems [START_REF] Donoho | On minimum entropy deconvolution[END_REF]. The FII has also been used to prove a strong version of the central limit theorem [START_REF] Carlen | Entropy production by block variable summation and central limit theorems[END_REF], [START_REF] Barron | Entropy and the central limit theorem[END_REF]- [START_REF] Johnson | Fisher information inequalities and the central limit theorem[END_REF] and a characterization of the Gaussian distribution by rotation [START_REF] Papathanasiou | Some characteristic properties of the Fisher information matrix via Cacoullos-type inequalities[END_REF], [START_REF] Itoh | An application of the convolution inequality for the Fisher information[END_REF].

B. Data Processing Inequalities for Least Squares Estimation 4

Before turning to the proof the FII, it is convenient and useful to make some preliminaries about data processing inequalities for Fisher information and MMSE. In estimation theory, the importance of the Fisher information follows from the Cramér-Rao bound (CRB) [START_REF] Cover | Elements of Information Theory[END_REF] on the mean-squared error of an estimator of a parameter from a measurement . In this context, is a random -vector whose density depends on , and the (parametric) Fisher information matrix is defined by [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] (18

)
where is the (parametric) score function [START_REF] Tekin | The Gaussian multiple access wire-tap channel[END_REF] In some references, the parametric Fisher information is defined as the trace of ( 18)

In the special case where is a translation parameter: , we recover the earlier definitions ( 11)-( 13):

, and . More generally, it is easily checked that for any

(21a) (21b)
The optimal unbiased estimator of given the observation , if it exists, is such that the mean-square error meets the CRB (reciprocal of the Fisher information) [START_REF] Cover | Elements of Information Theory[END_REF]. Such an optimal estimator is easily seen to be a linear function of the score [START_REF] Tekin | The Gaussian multiple access wire-tap channel[END_REF]. Thus it may be said that the score function represents the optimal least squares estimator of . When the estimated quantity is a random variable (i.e., not a parameter), the optimal estimator is the conditional mean estimator and the corresponding minimum mean-square error (MMSE) is the conditional variance . In both cases, there is a data processing theorem [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] relative to a transformation in a Markov chain , that is, for which given is independent of . The emphasize the similarity between these data processing theorems and the corresponding quantities of Fisher information and MMSE, we first prove the following "chain rule," which states that the optimal estimation given of results from the optimal estimation given of the optimal estimation given of . Proof: In the nonparametric case the Markov chain condition can written as . Multiplying by gives , which integrating over and yields (22a). In the parametric case the Markov chain condition can be written as where the distribution is independent of . Differentiating with respect to gives ; dividing by and applying Bayes' rule yields , which integrating over yields (22b).

From Proposition 4 we obtain a unified proof of the corresponding data processing inequalities for least squares estimation, which assert that the transformation reduces information about , or in other words, that no clever transformation can improve the inferences made on the data measurements: compared to , the observation yields a worse estimation of . where in deriving (27a) we have also used [START_REF] Oohama | Gaussian multiterminal source coding with several side informations at the decoder[END_REF] for . Since covariance matrices are positive semidefinite, this proves (23a), (23b), and (24a), (24b) follow by taking the trace. Equality holds in (23a), (24a), or in (23b), (24b) iff or is a deterministic function of , which by Proposition 4 is equivalent to (25a) or (25b), respectively.

Stam [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] mentioned that (24b) is included in the original work of Fisher, in the case where is a deterministic function of . A different proof of (23b) is provided by Zamir [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF]. The above proof also gives, via (27a), (27b) or the corresponding identities for the variance, explicit expressions for the information "loss" due to processing. The equality conditions correspond to the case where the optimal estimators given or are the same. In particular, it is easily checked that (25b) is equivalent to the fact that (in this order) also form a Markov chain, that is, is a "sufficient statistic" relative to [START_REF] Cover | Elements of Information Theory[END_REF].

As a consequence of Proposition 5, we obtain a simple proof of the following relation between Fisher information and MMSE in the case where estimation is made in Gaussian noise.

Proposition 6 (Complementary Relation between Fisher Information and MMSE):

If is Gaussian independent of , then [START_REF] Bercher | Estimating the entropy of a signal with applications[END_REF] In particular, if is white Gaussian [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF] Proof: Apply (27b) to the Markov chain , where and are independent of and of each other. Since , we have . Therefore, (27b) reads Noting that , one has and (28) follows upon multiplication by . For white Gaussian , (29) follows by taking the trace.

As noted by Madiman and Barron [START_REF] Madiman | Generalized entropy power inequalities and monotonicity properties of information[END_REF], [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF] is known in Bayesian estimation (average risk optimality): see [START_REF] Lehmann | Theory of Point Estimation[END_REF]Th. 4.3.5] in the general situation where is replaced any variable such that belongs to an exponential family parameterized by . It was rediscovered independently by Budianu and Tong [START_REF] Budianu | Channel estimation under asynchronous packet interference[END_REF], and by Guo, Shamai, and Verdú [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF], [START_REF] Guo | Mutual information and MMSE in Gaussian channels[END_REF]. Relation [START_REF] Bercher | Estimating the entropy of a signal with applications[END_REF] was also rederived by Palomar and Verdú [START_REF] Palomar | Gradient of mutual information in linear vector Gaussian channels[END_REF] as a consequence of a generalized de Bruijn's identity (Corollary 1). Other existing proofs are by direct calculation. The above proof is simpler and offers an intuitive alternative based on the data processing theorem.

To illustrate [START_REF] Bercher | Estimating the entropy of a signal with applications[END_REF], consider the case where and are zeromean Gaussian. In this case, the conditional mean estimator is linear of the form , where is given by the Wiener-Hopf equations . Therefore, . This gives, after some calculations, . But this expression is also an immediate consequence of ( 28) since one has simply . For standard Gaussian , (29) reduces to the identity , which constitutes a simple complementary relation between Fisher information and MMSE. The estimation of from the noisy version is all the more better as the MMSE is lower, that is, as has higher Fisher information. Thus Fisher information can be interpreted a measure of least squares (nonparametric) estimation's efficiency, when estimation is made in additive Gaussian noise.

C. Proofs of the FII via Data Processing Inequalities

Three distinct proofs of the FII (17c) are available in the literature. In this section, we show that these are in fact variations on the same theme: thanks to the presentation of Section II-B, each proof can be easily interpreted as an application of the data processing theorem to the (linear) deterministic transformation given by ( 9), or in parametric form (30)

1) Proof via the Data Processing Inequality for Fisher Information: This is essentially Stam's proof [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] (see also Zamir [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] for a direct proof of (17a) by this method). Simply apply (24b) to the transformation (30) [START_REF] Brown | A proof of the central limit theorem motivated by the Cramér-Rao inequality[END_REF] From (21b), the FII (17c) follows.

2) Proof via Conditional Mean Representations of the Score: This proof is due to Blachman [START_REF] Blachman | The convolution inequality for entropy powers[END_REF] in the scalar case . His original derivation is rather technical, since it involves a direct calculation of the convolution of the densities of independent random variables and to establish that for any , followed by an application of the Cauchy-Schwarz inequality. The following derivation is simpler and relies on the data processing theorem: By Proposition 4 applied to [START_REF] Barron | Entropy and the central limit theorem[END_REF] which from (21a) gives the following conditional mean representation of the score: [START_REF] Johnson | Entropy inequalities and the central limit theorem[END_REF] This representation includes Blachman's as a special case (for two variables and ). The rest of Blachman's argument parallels the above proof of the data processing inequality for Fisher information (Proposition 5): His application of the Cauchy-Schwarz inequality [START_REF] Blachman | The convolution inequality for entropy powers[END_REF] is simply a consequence of the law of total variance . Indeed, taking , and using [START_REF] Johnson | Entropy inequalities and the central limit theorem[END_REF], the inequality reduces to the FII (17c). Thus we see that, despite appearances, the above two proofs of Stam and Blachman are completely equivalent.

3) Proof via the Data Processing Inequality for MMSE: This proof is due to Verdú and Guo [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF], which use MMSE in lieu of Fisher's information. Apply (24a) to the transformation [START_REF] Cover | Elements of Information Theory[END_REF], in which each is replaced by , where the are i.i.d. white Gaussian of variance . Noting , this gives [START_REF] Johnson | Entropy and random vectors[END_REF] where is also white Gaussian of variance . By the complementary relation ( 29) (Proposition 6), this inequality is equivalent to the FII and letting gives (17c) 5 . Again this proof is equivalent to the preceding ones, by virtue of the complementary relation between Fisher information and MMSE.

4) Conditions for Equality in the FII:

The case of equality in (17c) was settled by Stam [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] and Blachman [START_REF] Blachman | The convolution inequality for entropy powers[END_REF]. In Stam's approach, by Proposition 5, (25b), equality holds in [START_REF] Brown | A proof of the central limit theorem motivated by the Cramér-Rao inequality[END_REF] iff , that is, using (

This equality condition is likewise readily obtained in Blachman's approach above. Obviously, it is satisfied only if all scores for which are linear functions, which means that equality holds in the FII only if the corresponding random vectors are Gaussian. In addition, replacing the scores by their expressions for Gaussian random -vectors in [START_REF] Artstein | On the rate of convergence in the entropic central limit theorem[END_REF], it follows easily by identification that these random vectors have identical covariance matrices. Thus equality holds in (17c) iff all random vectors such that are Gaussian with identical covariances.

Verdú and Guo do not derive the case of equality in [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF]. From the preceding remarks, however, it follows that equality holds in [START_REF] Johnson | Entropy and random vectors[END_REF] only if the for which are Gaussian-and, therefore, the corresponding are themselves Gaussian. This result is not evident from estimation-theoretic properties alone in view of the equality condition (25a) in the data processing inequality for the MMSE.

D. De Bruijn's Identity

1) Background: De Bruijn's identity is the fundamental relation between differential entropy and Fisher information, and as such, is used to prove the EPI (8c) from the corresponding FII (17c). This identity can be stated in the form [START_REF] Dembo | Information theoretic inequalities[END_REF] ( [START_REF] Johnson | Fisher information inequalities and the central limit theorem[END_REF] where is standard Gaussian, independent of the random -vector . It is proved in the scalar case in [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF], generalized to the vector case by Costa and Cover [START_REF] Costa | On the similarity of the entropy power inequality and the Brunn-Minkowski inequality[END_REF] and to nonstandard Gaussian by Johnson and Suhov [START_REF] Johnson | Entropy and random vectors[END_REF], [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF]. The conventional, technical proof of de Bruijn's identity relies on a diffusion equation satisfied by the Gaussian distribution and is obtained by integrating by parts in the scalar case and invoking Green's identity in the vector case. We shall give a simpler and more intuitive proof of a generalized identity for arbitrary (not necessarily Gaussian) .

Proposition 7 (De Bruijn's Identity): For any two independent random -vectors and such that exists and has finite covariances (36a)

In particular, if is white or has i.i.d. entries (36b)

2) A Simple Proof of De Bruijn's Identity: The proof is based on the following observation. Setting , (36a) can be rewritten as a first-order Taylor expansion in [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF] Now, there is a well known, similar expansion of relative entropy (divergence) [START_REF] Zamir | A generalization of the entropy power inequality with applications[END_REF] in terms of parametric Fisher information [START_REF] Tekin | The Gaussian multiple access wire-tap channel with collective secrecy constraints[END_REF], for a parameterized family of densities . Indeed, since the divergence is nonnegative and vanishes for , its second-order Taylor expansion takes the form [START_REF] Kullback | Information Theory and Statistics[END_REF] (39) where is the positive semidefinite Hessian matrix of the divergence, that is, , which is easily seen to coincide with definition (18) 6 . In view of the similarity between ( 37) and ( 39), the following proof of de Bruijn's identity is almost immediate.

Proof of Proposition 7:

Let and write mutual information as a conditional divergence:

. Making the change of variable gives , where is the parameterized family of densities of a random variable , and . Therefore, by [START_REF] Zamir | A generalization of the entropy power inequality with applications to linear transformation of a white-noise[END_REF] for scalar [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF] where is the parametric Fisher information of about , which is easily determined as follows. 6 Even though the divergence is not symmetric in (; ), it is locally symmetric in the sense that ( 39) is also the second-order Taylor expansion for

D (p kp ).
Expanding about gives , and, therefore, , where the limit for and the expectation have been exchanged, due to Lebesgue's convergence theorem and the fact that has finite covariances. It follows that so that the (parametric) score of for is where is the (nonparametric) score of . Therefore, . Plugging this expression into [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF] gives [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF] as required.

In exploiting the parallelism between ( 37) and [START_REF] Zamir | A generalization of the entropy power inequality with applications to linear transformation of a white-noise[END_REF], this proof explains the presence of the factor in de Bruijn's identity: this is merely a second-order Taylor expansion factor due to the definition of Fisher information as the second derivative of divergence. Besides, it is mentioned in [START_REF] Dembo | Information theoretic inequalities[END_REF] that [START_REF] Johnson | Fisher information inequalities and the central limit theorem[END_REF] holds for any random vector whose first four moments coincide with those of the standard Gaussian; here we see that it is sufficient that this condition hold for the second centered moments . Also note that it is not required that have a density. Thus, (36) also holds for a discrete valued perturbation .

3) The Gaussian Case: When is Gaussian, de Bruijn's identity [START_REF] Costa | A new entropy power inequality[END_REF] is readily extended to positive values of . Simply substitute for , where is independent of with the same distribution. By the stability property of the Gaussian distribution under convolution, and are identically distributed, and, therefore (41a) For white , this reduces to (41b) Such a generalization cannot be established for non-Gaussian , because the Gaussian distribution is the only stable distribution with finite covariances. Using the complementary relation [START_REF] Bercher | Estimating the entropy of a signal with applications[END_REF] of Proposition 6 and making the change of variable , it is a simple matter of algebra to show that (41a) is equivalent to (42a)

Since

, this alternative identity also generalizes (36a) (with and interchanged). For white , it reduces to (42b)

The latter two identities were thoroughly investigated by Guo, Shamai, and Verdú [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF]. The above proof, via de Bruijn's identity and Kullback's expansion [START_REF] Zamir | A generalization of the entropy power inequality with applications to linear transformation of a white-noise[END_REF], is shorter than the proofs given in [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF], and also has an intuitive interpretation, as shown next.

4) Intuitive Interpretations: Expansions ( 37) and ( 39) can be given similar interpretations. In [START_REF] Zamir | A generalization of the entropy power inequality with applications to linear transformation of a white-noise[END_REF], has local parabolic behavior at vertex with curvature , which means that for a given (small) value of divergence, is known all the more precisely as Fisher information is large (see Fig. 1). This confirms that is a quantity of "information" about . Similarly, [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF] shows that the mutual information between the noisy version of and the noise , seen as a function of the noise amplitude, is locally parabolic about with curvature . Hence for a given (small) value of noise amplitude , the noisy variable is all the more dependent on the noise as is higher (see Fig. 2). Therefore, de Bruijn's identity merely states that Fisher information measures the sensitivity to an arbitrary additive independent noise, in the sense that a highly "sensitive" variable, perturbed by a small additive noise, becomes rapidly noise-dependent as the amplitude of the noise increases. This measure of sensitivity of depends the noise covariances but is independent of the shape of the noise distribution otherwise, due to the fact that de Bruijn's identity remains true for non-Gaussian . Also, by the Cramér-Rao inequality ( 16), a Gaussian variable has lowest sensitivity to an arbitrary additive noise . Thus the saddlepoint property of mutual information , classically established for Gaussian [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Borden | Some information theoretic saddlepoints[END_REF], [START_REF] Diggavi | The worst additive noise under a covariance constraint[END_REF] (see also Proposition 8), is seen to hold to the first order of for an arbitrary additive noise . A dual interpretation is obtained by exchanging the roles of and in (36a) or [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF] to obtain an asymptotic formula for the input-output mutual information in a (non-Gaussian) additive noise channel for small signal-to-noise ratio (SNR). In particular, for i.i.d. input entries or if the channel is memoryless, either or is proportional to the identity matrix and, therefore Thus, as has been observed in, e.g., [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF], [START_REF] Lapidoth | Fading channels: How perfect need "perfect side information" be?[END_REF], and [START_REF] Guo | Additive non-Gaussian noise channels: Mutual information and conditional mean estimation[END_REF], the rate of increase of mutual information per unit SNR is equal to in the vicinity of zero SNR, regardless of the shape of the input distribution (see Fig. 3). In the case of a memoryless channel, it is also insensitive to input memory, since in this case [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] still holds for correlated inputs. Again by the Cramér-Rao inequality ( 16), the Gaussian channel exhibits a minimal rate of increase of mutual information, which complies with the wellknown fact that non-Gaussian additive noise channels cannot have smaller capacity than that of the Gaussian channel.

5) Applications: Apart from its role in proving the EPI, de Bruijn's identity (Proposition 7) has found many applications in the literature, although they were not always recognized as such. The Taylor expansion for non-Gaussianness corresponding to [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF] in the scalar case is mentioned, albeit in a disguised form, by Linnik [START_REF] Linnik | An information-theoretic proof of the central limit theorem with the Lindeberg condition[END_REF] who used it to prove the central limit theorem. Itoh [START_REF] Itoh | The information theoretic proof of Kac's theorem[END_REF] used Linnik's expansion to characterize the Gaussian distribution by rotation. Similar expansions have been derived by Prelov and others (see, e.g., [START_REF] Pinsker | Information rates in certain stationary non-Gaussian channels in weak-signal transmission[END_REF], [START_REF] Prelov | Asymptotic behavior of the capacity of a continuous channel with a large amount of noise[END_REF]- [START_REF] Prelov | Second-order asymptotics of mutual information[END_REF]) to investigate the behavior of the capacity or mutual information in additive Gaussian or non-Gaussian noise channels under various asymptotic scenarios. In particular, [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] was apparently first stated explicitly by Pinsker, Prelov and van der Meulen [START_REF] Pinsker | Information rates in certain stationary non-Gaussian channels in weak-signal transmission[END_REF]. A similar result was previously published by Verdú [START_REF] Verdú | On channel capacity per unit cost[END_REF] (see also [START_REF] Verdú | Spectral efficiency in the wideband regime[END_REF]) who used Kullback's expansion [START_REF] Zamir | A generalization of the entropy power inequality with applications to linear transformation of a white-noise[END_REF] to lower bound the capacity per unit SNR for non-Gaussian memoryless additive noise channels, a result which is also an easy consequence of [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF]. Motivated by the blind source separation problem, Pham [START_REF] Pham | Entropy of a variable slightly contaminated with another[END_REF] (see also [START_REF] Pham | Local minima of information-theoretic criteria in blind source separation[END_REF] and [START_REF] Vrins | Mixing and non-mixing local minima of the entropy contrast for blind source separation[END_REF]) investigated the first-and secondorder expansions in of entropy for non-Gaussian perturbation (not necessarily independent of ) and recovers de Bruijn's identity as a special case. Similar first-and second-order expansions for mutual information in non-Gaussian additive noise channels were derived by Guo, Shamai, and Verdú [START_REF] Guo | Additive non-Gaussian noise channels: Mutual information and conditional mean estimation[END_REF], yielding (43) as a special case.

6) Generalized De Bruijn's Identity: Palomar and Verdú [START_REF] Palomar | Gradient of mutual information in linear vector Gaussian channels[END_REF] proposed a matrix version of de Bruijn's identity by considering the gradient of with respect to the noise covariance matrix for Gaussian . We call attention that this is a simple consequence of (36a); the generalization to non-Gaussian is as follows.

Corollary 1: [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] where we have noted .

Proof 7 : By (36a), we have the following expansion:

where denotes the Fröbenius norm of . But this is of the form of a first-order Taylor expansion of a function with respect to a matrix 8 : and (44) follows by identifying the gradient matrix.

7) Relationship Between the Cramér-Rao Inequality and a Saddlepoint Property of Mutual Information:

The following saddle point property of mutual information, which was proved in [START_REF] Ihara | On the capacity of channels with additive non-Gaussian noise[END_REF] using a result of Pinsker [START_REF] Pinsker | Calculation of the rate of information production by means of stationary random processes and the capacity of stationary channel[END_REF], states that the worst possible noise distribution in a additive noise channel is the Gaussian distribution.

Proposition 8: Let be any random vector, and let be a Gaussian random vector with identical second moments. For any Gaussian random vector independent of and ( 45) Proof (Following [START_REF] Diggavi | The worst additive noise under a covariance constraint[END_REF]): Noting that has identical second moments as , we have . The result follows by the data processing inequality for divergence, applied to the transformation .

This proof, in contrast with that given in [START_REF] Cover | Elements of Information Theory[END_REF] and [START_REF] Borden | Some information theoretic saddlepoints[END_REF] for scalar variables, does not require the EPI, and is through a much less involved argument.

Interestingly, by virtue of de Bruijn's identity, it can be shown that ( 45) is equivalent to the famous Cramér-Rao inequality 9 [START_REF] Madiman | The monotonicity of information in the central limit theorem and entropy power inequalities[END_REF] To see this, divide both sides of (45) by the entries of and let . By Corollary 1, this gives . Conversely, integrating the relation using de Bruijn's identity [START_REF] Takano | The inequalities of Fisher information and entropy power for dependent variables[END_REF] readily gives [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF].

E. Earlier Proofs of the EPI

All available information theoretic proofs of the EPI use de Bruijn's identity to integrate the FII (or the corresponding inequality for MMSE) over the path of a continuous Gaussian perturbation. To simplify the presentation, we first consider a path of the form where is assumed standard Gaussian. The derivations in this section are readily extended to the case where is arbitrary Gaussian, by means of the corresponding generalized FII and de Bruijn's identity. 9 This follows from the relation J(X)0J(X ) = (S(X)0S (X)) 0, where S (X) is defined as in [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multiple-output broadcast channel[END_REF].

( (0) 1 K ) = k (0).

1) Basic Proof:

The following is a simplified version of Stam's proof [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF]. Apply the FII (17c) to the random vectors , where the are independent and standard Gaussian. This gives , where is also standard Gaussian. By de Bruijn's identity (41b), it follows that is a nonincreasing function of . But tends to as (see Lemma 3 below). Therefore, , which is the EPI (8c). Note that the case of equality in (8c) is easily determined by this approach, since it reduces to the case of equality in the corresponding FII (see Section II-C-4). Namely, equality holds in the EPI (8c) iff all random vectors for which are Gaussian with identical covariances. It follows that equality holds in the classical form of the EPI (8a) iff all random vectors for which are Gaussian with proportional covariances.

2) Integral Representations of Differential Entropy: In the above proof, de Bruijn's identity can be rewritten as an integral representation of entropy. To see this, introduce an auxiliary Gaussian random vector , and rewrite de Bruijn identity (41b) in the form 10 . Since as , we may integrate from to to obtain as the integral of . If, for example, is chosen standard, one obtains the integral representation [START_REF] Madiman | The monotonicity of information in the central limit theorem and entropy power inequalities[END_REF] (47a)

In view of this identity, the EPI (8c) immediately follows from the corresponding FII (17c).

3) Other Paths of Integration: Several variants of the above proof were published, either in differential or integral form. Dembo, Cover, and Thomas [START_REF] Dembo | Information theoretic inequalities[END_REF] and Carlen and Soffer [START_REF] Carlen | Entropy production by block variable summation and central limit theorems[END_REF] use a path connecting to of the form . The argument leading to the EPI is the same up to an appropriate change of variable. The corresponding integral representation (47b) was first used by Barron [30] to prove a strong version of the central limit theorem. Verdú and Guo [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF] used the path and replaced Fisher information by MMSE. They used (42b) to integrate inequality [START_REF] Johnson | Entropy and random vectors[END_REF] over this path. Their proof is completely equivalent to Stam's proof above, by means of the complementary relation [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF] of Proposition 6 and the change of variable . The corresponding integral representation becomes [START_REF] Guo | Mutual information and minimum mean-square error in Gaussian channels[END_REF]- [START_REF] Guo | Proof of entropy power inequalities via MMSE[END_REF] (47c) 10 When X is chosen such that (X ) = (X), the identity relates nonnegative "non-Gaussiannesses" ( 6) and ( 15). Yet another possibility is to take the path connecting to , leading to the following integral representation: (47d) All the above representations for entropy are equivalent through appropriate changes of variable inside the integrals.

III. A NEW PROOF OF SHANNON'S EPI

A. A Mutual Information Inequality (MII)

From the analysis made in Section II, it is clear that earlier information theoretic proofs of the EPI can be seen as variants of the same proof, with the following common ingredients:

1) a data processing inequality applied to the linear transformation (9). 2) an integration over a path of a continuous Gaussian perturbation. While step 1) uses the data processing theorem in terms of either parametric Fisher information or MMSE, step 2) uses de Bruijn's identity, which relates Fisher information or MMSE to entropy or mutual information. This suggests that it should be possible to prove the EPI via a data processing argument made directly on the mutual information. The interest is twofold: First, compared to the data processing theorem for Fisher information, the corresponding theorem for Shannon's mutual information is presumably more familiar to the readers of this journal. Second, this approach sidesteps both Fisher information and MMSE and avoids the use of de Bruijn's identity (41b) or (42b).

We shall prove a stronger statement than the EPI, namely, that the difference between both sides of (8c) decreases as independent Gaussian noise is added. Since for any independent of (see Lemma 1), we write this statement in terms of mutual information as follows.

Theorem 1 (Mutual Information Inequality (MII)):

For finitely many independent random -vectors with finite covariances, any real-valued coefficients normalized such that , and any Gaussian -vector independent of [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] Furthermore, this inequality implies the EPI (8c).

The MII [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] can be interpreted as a convexity property of mutual information under the covariance-preserving transformation [START_REF] Cover | Elements of Information Theory[END_REF]. As we shall see, the crucial step in the proof of Theorem 1 is the data processing inequality for mutual information [START_REF] Cover | Elements of Information Theory[END_REF]. We also need the following technical lemmas. In order to be mathematically correct throughout we first establish some basic properties of mutual information and entropy.

Lemma 1: Let be any random -vector and be any Gaussian -vector independent of . Then has a density, exists and is finite. In addition, if exists, the identity always holds.

Proof: Let be the characteristic function of ; that of is where . Since characteristic functions are bounded continuous and has rapid decay (faster than any inverse of a polynomial) at infinity, it follows that is integrable. Therefore, admits a bounded density 11 , such that where is some positive constant. The negative part of the integral is , which is bounded. Hence exists and is finite. If exists, then either admits a density or it does not. In the former case also admits a density and the identity is well known. In the latter case we have put (see Section I-B). Since is not absolutely continuous with respect to the Lebesgue measure, there exists a set of zero measure such that . Then has zero Lebesgue measure and . Since is also of zero measure with respect to the product probability measure with density , it follows that is not absolutely continuous with respect to this product measure. Therefore, by the theorem of Gel'fand-Yaglom-Perez [50, ch. 2], one has and the identity still holds.

In the same way one can prove that the identity always holds for any . The following inequality [START_REF] Vajda | Theory of Statistical Inference and Information[END_REF] was proved for two variables by Sato [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF] who used it to derive an outer bound to the capacity region of broadcast channels. A similar inequality appears in [START_REF] Gallager | Information Theory and Reliable Communication[END_REF]Th. 4.2.1] and in [START_REF] Mceliece | The Theory of Information and Coding, ser. Encyclopedia of Mathematics and its Applications[END_REF]Th 1.9].

Lemma 2 (Sato's Inequality):

If the random vectors are independent of and of each other, then [START_REF] Vajda | Theory of Statistical Inference and Information[END_REF] Proof: Let for all . By the chain rule for mutual information [50, ch. 3], one has 11 This density is in fact indefinitely differentiable and strictly positive, and all its derivatives are bounded and tend to zero at infinity. An alternative proof in the case where admits a density, is as follows. Define the multi-information between the components of by the divergence [START_REF] Johnson | Information Theory and The Central Limit Theorem[END_REF] From the definitions it is obvious that . The result follows since and .

(50a) (50b) (50c) (50d) (50e)
Lemma 3: If and are independent random -vectors with finite covariances and differential entropies, then [START_REF] Papathanasiou | Some characteristic properties of the Fisher information matrix via Cacoullos-type inequalities[END_REF] If, in addition, is differentiable at , then for any real constant [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] where is a function defined for all such that as . Proof: To prove (52), let . Taking characteristic functions, as . Therefore in distribution. Let and be Gaussian -vectors have identical covariances as and , respectively. Likewise in distribution. By the lower semicontinuity of divergence (see [START_REF] Pinsker | Information and Information Stability of Random Variables and Processes[END_REF]Sec. 2.4] and [89, Th. 1]), we have [START_REF] Itoh | An application of the convolution inequality for the Fisher information[END_REF] The following quantities are all finite.

(55a) (55b) An easy calculation for Gaussian vectors gives . Therefore (54) reduces to [START_REF] Budianu | Channel estimation under asynchronous packet interference[END_REF] This combined with nonnegativity of mutual information proves [START_REF] Papathanasiou | Some characteristic properties of the Fisher information matrix via Cacoullos-type inequalities[END_REF]. Now suppose is differentiable at . Since , for any and tend toward the same limit as . This reduces to [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF].

Note that neither Lemma 2 nor Lemma 3 requires to be Gaussian. The following lemma gives an important situation where the differentiability assumption of Lemma 3 is met. integral representations [START_REF] Madiman | Generalized entropy power inequalities and monotonicity properties of information[END_REF]. Also Lemma 3 is an easy consequence of de Bruijn's identity, since by [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF], both sides of ( 53) are equal to . The originality here lies in the above proof of Theorem 1 and the EPI, which in contrast to existing proofs, requires neither de Bruijn's identity nor the notions of Fisher information or MMSE.

The new proof shares common ingredients with earlier proofs of the EPI, namely items 1) and 2) listed at the beginning of this section. The difference is that they are used directly in terms of mutual information. As in Section II-E-3, other paths of continuous Gaussian perturbation could very well be used, through suitable changes of variable.

One may wonder if mutual informations in the form rather than could be used in the above derivation of Theorem 1, particularly in inequalities [START_REF] Pinsker | Information rates in certain stationary non-Gaussian channels in weak-signal transmission[END_REF]. This would offer a dual proof, in the same way as Verdú and Guo's proof is dual to Stam and Blachman's original proof of the EPI, as explained in Section II. But a closer look at the above proof reveals that the dual approach would amount to prove [START_REF] Diggavi | The worst additive noise under a covariance constraint[END_REF], whose natural proof using the data processing inequality is through [START_REF] Pinsker | Information rates in certain stationary non-Gaussian channels in weak-signal transmission[END_REF]. Thus, it turns out that the two approaches amount to the same.

Also note that by application of de Bruijn's identity, inequality (60) reduces to the FII (17c). Thus the MII [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] implies both the EPI (8c) and the FII (17c).

2) The Equality Case: Our method does not easily settle the case of equality in the MII. By the preceding remark, however, equality in [START_REF] Kullback | Information Theory and Statistics[END_REF] implies equality in the FII (17c), which was determined in Section II-C-4. It follows that equality holds in the MII [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] if and only if all random vectors such that are Gaussian with identical covariances. This result implies the corresponding necessity condition of equality in the EPI, but is not evident from the properties of mutual information alone.

3) On the Gaussianness of : It is interesting to note that from [START_REF] Kullback | Information Theory and Statistics[END_REF], the MII holds up to first order of the noise variance, regardless of whether is Gaussian or not. However, the stability property of the Gaussian distribution under convolution was crucial in the next step of the proof, because the Gaussian perturbation can be made to affect the random vectors independently. In fact, the MII can be easily rewritten as [START_REF] Lapidoth | Fading channels: How perfect need "perfect side information" be?[END_REF] where for all , the being independent copies of . This does not hold in general for non-Gaussian random vectors . To see this, choose themselves Gaussian with identical covariances. Then the left-hand side (LHS) of ( 63) is zero, and by the necessity of the condition for equality in the EPI, the RHS is positive, as soon as is non-Gaussian for some such that . Therefore, in this case, the opposite inequality is obtained. In other words, adding non-Gaussian noise may increase the difference between both sides of the EPI (8c), in accordance with the fact that this difference is zero for Gaussian random vectors.

4) On the Finite Second-Order Moment Assumption: To prove Theorem 1 we have assumed for simplicity that the have finite covariances so that differential entropies are well defined and the lower semicontinuity argument in Lemma 3 applies. However, it would be possible to weaken this condition to first-order finite moment or even to the condition of Proposition 1 by considering divergences with respect to probability distributions other than Gaussian, e.g., exponential or Cauchy distributions as in the proof of Proposition 1. The details are left to the reader.

5) On the Use of Sato's Inequality: Sato used (49) and the data processing inequality to derive his cooperative outer bound to the capacity region of two-user broadcast channels [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF]. This bound was used to determine the capacity of a two-user MIMO Gaussian broadcast channel [START_REF] Caire | On the achievable throughput of a multiantenna Gaussian broadcast channel[END_REF]. Sato's bound was later replaced by the EPI to generalize Bergmans' solution to an arbitrary multiuser MIMO Gaussian broadcast channel using the notion of an "enhanced" channel [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multiple-output broadcast channel[END_REF]. In the present paper, the EPI itself is proved using Sato's inequality and the data processing inequality. This suggests that for proving converse coding theorems, a direct use of the EPI may be avoided by suitable inequalities for mutual information. A similar remark goes for the generalization of Ozarow's solution to vector Gaussian multiple descriptions [START_REF] Wang | Vector Gaussian multiple description with individual and central receivers[END_REF].

6) Relationship Between Various Data Processing Theorems: Proposition 5 enlightens the connection between two estimation theoretic data processing inequalities: parametric (Fisher information) and nonparametric (MMSE). While these were applied in earlier proofs of the EPI, the new proof uses the same data processing argument in terms of mutual information: any transformation in a Markov chain reduces information about . This can also be given a parametric form using divergence [START_REF] Zamir | A generalization of the entropy power inequality with applications[END_REF]. Thus, if form a Markov chain, then (64a) (64b) As in Proposition 5, the first data processing inequality involves a random variable , while the second considers as a parameter. The proof is immediate from the chain rules and where by the Markov chain condition, and , respectively. Comparing the various proofs of the EPI presented above, it is clear that, as already suggested in Zamir's presentation [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF], estimation theoretic and information theoretic data processing inequalities are strongly related. Also note that in view of [START_REF] Zamir | A generalization of the entropy power inequality with applications to linear transformation of a white-noise[END_REF], the lesser known data processing inequality for Fisher information (23b) is an immediate consequence of the corresponding inequality for divergence (64b). Indeed, dividing both sides of (64b) by and letting gives (23b). It would be interesting to see if the various data processing inequalities (for mutual information, divergence, MMSE, and Fisher information) can be further unified and given a common viewpoint, leading to new insights and applications.

7) On the EPI for Discrete Variables: The above proof of the MII does not require the to be random vectors with densities. Therefore, it also holds when the random vectors are discrete (finitely or countably) valued. In fact, Verdú and Guo [START_REF] Verdú | A simple proof of the entropy-power inequality[END_REF] used [10, Lemma 6, App. VII] to show that the EPI (8c) also holds in this case, where differential entropies are replaced by entropies. We call attention that this is in fact a immediate consequence of the stronger inequality for any independent discrete random vectors and any real-valued coefficients , which is easily obtained by noting that for all . Note, however, that the classical EPI in the form does not hold in general for discrete random vectors-a simple counterexample is obtained by taking deterministic for all . There also exist may discrete analogs to the entropy power inequality, either in the form (8a) or (8c). A first set of results [START_REF] Wyner | A theorem on the entropy of certain binary sequences and applications: Part I[END_REF]- [START_REF] Shamai | A binary analog to the entropy-power inequality[END_REF] were derived for binary random vectors where addition is replaced by modulo-2 addition. The corresponding inequalities are quite different from [START_REF] Guleryuz | Information-theoretic inequalities for contoured probability distributions[END_REF] and apparently unrelated to the contributions of this paper.

More recent results involve random variables taking integer values. In this case, the role of the Gaussian distribution and it stability property under convolution is played by the Poisson distribution. An analog of the FII [START_REF] Leung-Yan-Cheong | The Gaussian wire-tap channel[END_REF] was proposed by Kagan [START_REF] Kagan | A discrete version of the Stam inequality and a characterization of the Poisson distribution[END_REF] and a similar, alhtough different, version of discrete Fisher information was used in [START_REF] Kontoyiannis | Entropy and the law of small numbers[END_REF] in connection with the convergence of the (usual) sum of independent binary random variables toward the Poisson distribution. A discrete analog to (8a) was proved for binomial distributions [START_REF] Harremoës | An entropy power inequality for the binomial family[END_REF], and a discrete analog to (8c) was recently established by Yu and Johnson [START_REF] Yu | Concavity of entropy under thinning[END_REF] for positive random variables having ultra-log-concave distributions. It would be desirable to unify the different approaches for integer-valued random variables to see whether the method of this paper contributes to what is known in this case.

IV. ZAMIR AND FEDER'S EPI FOR LINEAR TRANSFORMATIONS

A. Background

Zamir and Feder [START_REF] Zamir | A generalization of the entropy power inequality with applications[END_REF]- [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF] generalized the scalar EPI by extending the linear combination of random variables to an arbitrary linear transformation , where is the random vector of independent entries and is a rectangular matrix. They showed that the resulting inequality cannot be derived by a straightforward application of the vector EPI of Proposition 2. They also noted that it becomes trivial if is row-rank deficient. Therefore, in the following, we assume that has full row rank.

Zamir and Feder's generalized EPI (ZF-EPI) has been used to derive results on closeness to normality after linear transformation of a white random vector in the context of minimum entropy deconvolution [START_REF] Zamir | A generalization of the entropy power inequality with applications[END_REF] and analyze the rate-distortion performance of an entropy-coded dithered quantization scheme [START_REF] Zamir | Rate-distortion performance in coding bandlimited sources by sampling and dithered quantization[END_REF]. It was also used as a guide to extend the Brunn-Minkowski inequality in geometry [START_REF] Zamir | A matrix form of the Brunn-Minkowski inequality[END_REF], [START_REF] Zamir | On the volume of the Minkowski sum of line sets and the entropy-power inequality[END_REF], which can be applied to the calculation of lattice quantization bit rates under spectral constraints.

The equivalent forms of the ZF-EPI corresponding to those given in Proposition 2 are the following.

Proposition 9 (Equivalent ZF-EPIs): The following inequalities, each stated for any random (column) vector of inde-pendent entries with densities and real-valued rectangular full row rank matrix , are equivalent.

(65a) (65b) (65c)
where is the number of rows in , and the components of are independent Gaussian random variables of entropies . The proof of Proposition 9 is a direct extension of that of Proposition 2. That (65a), (65b) are equivalent follows immediately from the equalities . The implication (65c) (65a) is proved in [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF], and the equivalence (65b) (65c) is proved in detail in [START_REF] Guo | Proof of entropy power inequalities via MMSE[END_REF]. Similarly as for (8c), inequality (65c) can be interpreted as a concavity property of entropy under the variance-preserving12 transformation [START_REF] Itoh | The information theoretic proof of Kac's theorem[END_REF] and is the golden door in the route of proving the ZF-EPI. The conventional techniques presented in Section II generalize to the present situation. One has the following Fisher information matrix inequalities analogous to (65):

(67a) (67b) (67c)
where the components of are independent Gaussian variables with Fisher informations for all . The first inequality (67a) was derived by Papathanasiou [START_REF] Papathanasiou | Some characteristic properties of the Fisher information matrix via Cacoullos-type inequalities[END_REF] and independently by Zamir and Feder [START_REF] Zamir | A generalization of the entropy power inequality with applications[END_REF], [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF], who used a generalization of the conditional mean representation of score (see Section II-C-2); their proof is simplified in [START_REF] Vignat | Matrix Fisher inequalities for non-invertible linear systems[END_REF] and [START_REF] Vignat | On Fisher information inequalities and score functions in non-invertible linear systems[END_REF]. Later, Zamir [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] provided an insightful proof of (67) by generalizing Stam's approach (see Section II-C-1) and also determined the case of equality [START_REF] Vignat | Matrix Fisher inequalities for non-invertible linear systems[END_REF], [START_REF] Zamir | A Necessary and Sufficient Condition for Equality in the Matrix Fisher-Information-Inequality Dept[END_REF]. Taking the trace in both sides of (67c) gives [START_REF] Prelov | Asymptotic behavior of the capacity of a continuous channel with large nonadditive noise[END_REF] which was used by Zamir and Feder [START_REF] Zamir | A generalization of information theoretic inequalities to linear transformations of independent vector[END_REF], [START_REF] Zamir | A proof of the Fisher information inequality via a data processing argument[END_REF] to prove the ZF-EPI (65c) by integration over the path (see Section II-E). Finally, Guo, Shamai, and Verdu [START_REF] Guo | Proof of entropy power inequalities via MMSE[END_REF] generalized their approach (see Section II-C-3) to obtain [START_REF] Ibragimov | Weak signal transmission in a memoryless channel[END_REF] where and the are standard Gaussian independent of , and used it to prove the ZF-EPI (65c) by integration over the path (see Section II-E). Again the approaches since

(X) = I implies (AX) = A (X)A = AA = I.
corresponding to [START_REF] Prelov | Asymptotic behavior of the capacity of a continuous channel with large nonadditive noise[END_REF] and ( 69) are equivalent by virtue of the complementary relation [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF], as explained in Section II-C-3.

B. A New Proof of the ZF-EPI

The same ideas as in the proof of Theorem 1 are easily generalized to prove the ZF-EPI.

Theorem 2 (Mutual Information Inequality for Linear Transformations): For any random vector with independent entries having finite variances, any real-valued rectangular matrix with orthonormal rows , and any standard Gaussian random -vector and variable independent of [START_REF] Prelov | Communication channel capacity with almost Gaussian noise[END_REF] Furthermore, this inequality imply the ZF-EPI.

Proof: Noting , a Gaussian random vector with the same dimension as , we can write the following string of inequalities:

(71a) (71b) (71c)
where (71a) holds since , (71b) follows from the data processing theorem applied to the linear transformation [START_REF] Itoh | The information theoretic proof of Kac's theorem[END_REF], and (71c) follows from Sato's inequality (Lemma 2). Now apply the resulting inequality to , where and is a standard Gaussian random vector independent of all other random variables, and replace by , where . This gives The Gaussian perturbation ensures that densities of the are smooth, so that (52) of Lemma 3 applies to the RHS. Noting that and therefore, for all , we obtain where is identically distributed as (since ), and is a standard Gaussian variable, independent of all other random variables. By the stability property of the Gaussian distribution under convolution, is identically distributed as , and the are identically distributed as . Therefore, applying [START_REF] Palomar | Gradient of mutual information in linear vector Gaussian channels[END_REF] gives which shows that is nonincreasing in . Also, by Lemma 3, . Therefore, , which proves the required MII [START_REF] Prelov | Communication channel capacity with almost Gaussian noise[END_REF].

Finally, we show that (70) implies the ZF-EPI (65c). By the identity for any independent of , the MII in the form can be rewritten as where

. The other terms in the RHS of this inequality are of the form , which letting tends to zero by Lemma 3. This completes the proof.

Notice that the approach presented here for proving the ZF-EPI is the same as for proving the original EPI, namely, that the difference between both sides of the ZF-EPI (65c) is as independent white Gaussian noise is added

where and is white Gaussian independent of . Zamir and Feder derived their results for random variables . However, our approach can be readily extended to random -vectors. For this purpose, consider the random vector whose components are themselves -vectors, and adopt the convention that the components of are -vectors given by the relations , which amounts to saying that is a block matrix with submatrix entries . The generalization of Theorem 2 is straightforward and we omit the details. The corresponding general ZF-EPI is still given by (65), with the above convention in the notations.

V. TAKANO AND JOHNSON'S EPI FOR DEPENDENT VARIABLES

A. Background

Takano [START_REF] Takano | The inequalities of Fisher information and entropy power for dependent variables[END_REF] and Johnson [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF] provided conditions under which the EPI, in the form , would still hold for dependent variables. These conditions are expressed in terms of appropriately perturbed variables [START_REF] Pinsker | Sensitivity of channel capacity[END_REF] where are standard Gaussian, independent of and of each other, and and are positive functions which tend to infinity as . They involve individual scores and Fisher informations , as well as the entries of the joint score and the Fisher information matrix where is a Lagrange multiplier corresponding to the contsraint . It follows that , that is, , or . Now let be any random vector independent of , such that . Define and , and let be a Gaussian random vector identically distributed as and independent of . Since and , we may apply Theorem 4. By [START_REF] Gallager | Information Theory and Reliable Communication[END_REF], we obtain that is, replacing and rearranging Therefore, the Gaussian random vector is an optimal solution to (84) subject to the constraint . This completes the proof.

VII. COSTA'S EPI: CONCAVITY OF ENTROPY POWER

A. Background

Costa [START_REF] Costa | A new entropy power inequality[END_REF] has strengthened the EPI for two random vectors in the case where is white Gaussian. While it can be easily shown [START_REF] Dembo | Information theoretic inequalities[END_REF], [START_REF] Costa | A new entropy power inequality[END_REF] that Shannon's EPI for is equivalent to Costa's EPI is the convexity inequality which expresses that the entropy power is a concave function of the power of the added Gaussian noise [START_REF] Wyner | A theorem on the entropy of certain binary sequences and applications: Part II[END_REF] Alternatively, the concavity of the entropy power is equivalent to saying that the slope drawn from the origin is nonincreasing, while the corresponding Shannon's EPI is weaker, being simply equivalent to the inequality . The original proof of Costa through an explicit calculation of the second derivative in ( 93) is quite involved [START_REF] Costa | A new entropy power inequality[END_REF]. His calculations are simplified in [START_REF] Villani | A short proof of the "concavity of entropy power[END_REF]. Dembo gave an elegant proof using the FII over the path [START_REF] Dembo | Information theoretic inequalities[END_REF], [START_REF] Dembo | Simple proof of the concavity of the entropy power with respect to added Gaussian noise[END_REF]. Recently, Guo, Shamai, and Verdú provided a clever proof using the MMSE over the path [START_REF] Guo | Proof of entropy power inequalities via MMSE[END_REF]. Costa's EPI has been used to determine the capacity region of the Gaussian interference channel [START_REF] Costa | On the Gaussian interference channel[END_REF]. It was also used as a continuity argument about entropy that was required for the analysis of the capacity of flat-fading channels in [START_REF] Lapidoth | Capacity bounds via duality with applications to multiple-antenna systems on flat-fading channels[END_REF].

B. A New Proof of the Concavity of the Entropy Power

In his original presentation [START_REF] Costa | A new entropy power inequality[END_REF], Costa proposed the concavity property in the segment for white Gaussian , in which case he showed its equivalence to [START_REF] Wyner | A theorem on the entropy of certain binary sequences and applications: Part II[END_REF]. He also established this inequality in the dual case where is Gaussian and is arbitrary. In the latter case, however, this inequality is not sufficient to prove that is a concave function of . In this section, we prove a slight generalization of Costa's EPI, showing concavity in both cases, for an arbitrary (not necessarily white) Gaussian random vector. Again the proposed proof relies only on the basic properties of mutual information. . This gives [START_REF] Witsenhausen | Entropy inequalities for discrete channels[END_REF] We now turn this into a "mutual information power inequality" similarly as the EPI (8a) is derived from (8c) in the proof of Proposition 2. Define as the power of a Gaussian random vector having covariances proportional to those of and identical mutual information . By Shannon's capacity formula, , and therefore Choose such that in [START_REF] Witsenhausen | Entropy inequalities for discrete channels[END_REF]. This is always possible, because the difference has opposite signs for and . By applying the function to both sides of (94), we find

We now let (so that ). Since , and similarly, , we obtain Dividing by and letting gives that is, carrying out the derivation, or as required.

It would be interesting to know whether this proof can be adapted to the recent generalization of Costa's EPI [START_REF] Payaró | A multivariate generalization of Costa's entropy power inequality[END_REF]- [START_REF] Liu | A vector generalization of Costa's entropy-power inequality with applications[END_REF] in which is replaced by an arbitrary positive semidefinite matrix.

VIII. OPEN QUESTIONS

A. EPI, FII, and MII for Subsets of Independent Variables

Recently, Artstein, Ball, Barthe, and Naor [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF] proved a new entropy power inequality involving entropy powers of sums of all independent variables excluding one, which solved a longstanding conjecture about the monotonicity of entropy. This was generalized to arbitrary collections of subsets of independent variables (or vectors) by Madiman and Barron [START_REF] Madiman | The monotonicity of information in the central limit theorem and entropy power inequalities[END_REF], [START_REF] Madiman | Generalized entropy power inequalities and monotonicity properties of information[END_REF]. The generalization of the classical formulation of the EPI takes the form [START_REF] Shamai | A binary analog to the entropy-power inequality[END_REF] where the sum in the RHS is over arbitrary subsets of indexes, and is the maximum number of subsets in which one index appears. Note that we may always assume that subsets are "balanced" [START_REF] Madiman | Generalized entropy power inequalities and monotonicity properties of information[END_REF], i.e., each index appears in the RHS of [START_REF] Shamai | A binary analog to the entropy-power inequality[END_REF] exactly times. This is because it is always possible to add singletons to a collection of subsets until the balancing condition is met; since the EPI (95) would hold for the augmented collection, it a fortiori holds for the initial collection as well.

For balanced subsets, the inequalities generalizing (8c), (17c), [START_REF] Johnson | Entropy and random vectors[END_REF], and (48) are the following.

Proposition 10: Let be finitely many random -vectors, let be any Gaussian random -vector independent of , and let be any real-valued coefficients normalized such that . Then, for any collection of balanced subsets of indexes (96a) (96b) (96c) (96d) where (so that ) and is given by the covariance preserving transformation Available proofs of (96a)-(96c) are generalizations of the conventional techniques presented in Section II, where an additional tool ("variance drop lemma") is needed to prove either (96a) or (96b); see [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF]Lemma 5], [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF]Lemma 3], or [47, Lemma 2]. Artsein, Ball, Barthe, and Naor's proof of the EPI (96c), which is generalized and simplified by Madiman and Barron, is through an integration of the FII (96a) over the path (in [45, eq. (47b)]) or (in [47, eq. (47a)]). Tulino and Verdú provided the corresponding proof via MMSE [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF], through an integration of the MMSE inequality (96b) over the path [see (47c)]. Again the approaches corresponding to (96a) and (96b) are equivalent by virtue of the complementary relation [START_REF] Vrins | On the entropy minimization of a linear mixture of variables for source separation[END_REF], as explained in Section II-C-3.

That the MII (96d) holds is easily shown through (96a) or (96b) and de Bruijn's identity [START_REF] Takano | The inequalities of Fisher information and entropy power for dependent variables[END_REF] or [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF]. However, the author was not able to extend the ideas in the proof of Theorem 1 to provide a direct proof of the MII (96d), which letting would yield an easy proof of the generalized EPI (96c). Such an extension perhaps involves a generalization of the data processing inequality or Sato's inequality in [START_REF] Pinsker | Information rates in certain stationary non-Gaussian channels in weak-signal transmission[END_REF], which using the relation would yield the inequality .

B. EPI, FII, and MII for Gas Mixtures

There is a striking resemblance between the original inequalities (8c), (17c), [START_REF] Johnson | Entropy and random vectors[END_REF], and [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] for linear mixtures of independent random vectors, and known inequalities concerning entropy and Fisher information for linear "gas mixtures" of probability distributions.

Proposition 11: Let the random variable have distribution where , let be finitely many random -vectors independent of , and let be white Gaussian, independent of and . Then

Noting that has distribution , the "FII" (97a) can be proved directly as follows. Let and be the score functions of and the , respectively, and define for all . Then and since the squared norm is convex,

. Averaging over gives (97a).

Once (97a) is established, the conventional techniques presented in Section II can be easily adapted to deduce the other inequalities (97b)-(97d): Substituting for in (97a), where the are independent copies of , and noting that has the same probability distribution as , we obtain the inequality ; applying the complementary relation ( 29) gives (97b); integrating using de Bruijn's identity [START_REF] Takano | The inequalities of Fisher information and entropy power for dependent variables[END_REF] or [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF] gives (97d), from which (97c) follows as in the proof of Theorem 1.

In the present case, however, (97c) and (97d) are already well known. In fact, since is a convex combination of distributions, the "EPI" (97c) is nothing but the classical concavity property of entropy, seen as a functional of the probability distribution [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Gallager | Information Theory and Reliable Communication[END_REF], [START_REF] Mceliece | The Theory of Information and Coding, ser. Encyclopedia of Mathematics and its Applications[END_REF]. This is easily established by noting that since conditioning decreases entropy, . Also the "MII" (97d) is just the classical convexity of mutual information , seen as a functional of the distribution for fixed [9, Thm. 2.7.4], [START_REF] Gallager | Information Theory and Reliable Communication[END_REF]Thm. 4.4.3], [START_REF] Mceliece | The Theory of Information and Coding, ser. Encyclopedia of Mathematics and its Applications[END_REF]Thm. 1.7].

Accordingly, we may reverse the order of implication and derive the corresponding convexity property of Fisher information (97a) anew from the "MII" (97d). Indeed, (97d) can be rewritten in the form for any . Dividing both sides by and letting gives (97a) by virtue of de Bruijn's identity. This derivation is much shorter than earlier proofs of (97a), [START_REF] Dembo | Information theoretic inequalities[END_REF]Lemma 6], [START_REF] Budianu | Channel Estimation Under Asynchronous Packet Interference Cornell Univ[END_REF]. The convexity property of Fisher information finds application in channel estimation [START_REF] Budianu | Channel estimation under asynchronous packet interference[END_REF] and thermodynamics [START_REF] Frieden | Fisherbased thermodynamics: Its Legendre transform and concavity properties[END_REF].

Proposition 4 (

 4 Data Processing Theorem for Estimators): If form a Markov chain, then (22a) (22b)

Proposition 5 (

 5 Estimation Theoretic Data Processing Inequalities): If form a Markov chain, then The following identity ("total law of covariance") is well known and easy to check:

Fig. 1 .Fig. 2 .

 12 Fig. 1. Kullback-Leibler divergence drawn as a function of the estimated parameter for (a) low and (b) high value of Fisher information.

Fig. 3 .

 3 Fig. 3. Input-output mutual information over an additive noise channel, drawn as a function of SNR for small SNR and standard Z. (a) Gaussian channel J(Z) = 1. (b) Laplacian channel J(Z) = 2.

  revised August 24, 2010; accepted August 29, 2010. Date of current version December 27, 2010. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Nice, France, 2007.

The author is with the Institut Télécom, Télécom ParisTech, CNRS LTCI, Paris, France. Communicated by K. Kobayashi, Associate Editor for Shannon Theory. Digital Object Identifier 10.1109/TIT.2010.2090193 1 if and only if.

Lieb's excepted, since it belongs to mathematical analysis and cannot be qualified as an "information theoretic" proof.

This proof corrects a small error in[START_REF] Dembo | Information theoretic inequalities[END_REF], namely, that the first statement in the proof of Theorem 7 in[START_REF] Dembo | Information theoretic inequalities[END_REF] is false when the Gaussian random vectors do not have identical covariances.

We use the term "least squares estimation" for any estimation procedure based on the mean-squared error criterion.

This continuity argument is justified in[START_REF] Pinsker | Information rates in certain stationary non-Gaussian channels in weak-signal transmission[END_REF].

The 1=2 factor is absent in[START_REF] Palomar | Gradient of mutual information in linear vector Gaussian channels[END_REF], due to the fact that complex gradients are considered.

If the (X ) have equal variances, then so have the components of AX,

As explained in Section II-D-7, the Cramér-Rao inequality (46) is equivalent to the saddlepoint property (45) used in their "direct proof."

ACKNOWLEDGMENT

The author wishes to thank the Associate Editor for his patience, and the anonymous reviewers for their helpful comments and for pointing out several references and the counterexample of Section I-B. Preliminary advice from Prof. S. Shamai, Prof. J. Chen, and Dr. Y. Wu are also gratefully acknowledged.

Lemma 4: Let be any random -vector with finite covariances and differential entropy, and let be identically distributed Gaussian -vectors such that are independent. The quantity is differentiable at any . In addition, if where , then [START_REF] Guo | Mutual information and MMSE in Gaussian channels[END_REF] is also differentiable at . Proof: Following Stam [START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF], Barron [START_REF] Barron | Entropy and the central limit theorem[END_REF] proved that is differentiable in for any square-integrable . The proof involves exchanges of differentiation and expectation justified by the dominated convergence theorem and is not repeated here. From Lemma 1 is follows that is likewise differentiable at any . Now the following quantities are all finite.

(58a) (58b)

The last equality follows from the stability property of the Gaussian distribution under convolution, since is identically distributed as . Since is differentiable at for any is likewise differentiable at .

Proof of Theorem 1: We may always assume that for all -otherwise simply delete the for which . To prove [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF], we may also assume that all the have finite differential entropies, since otherwise the right-hand side (RHS) of ( 48) is by Lemma 1. Then all the admit densities, and likewise admits a density and has finite covariances. From Proposition 1 it follows that , and since conditioning reduces entropy, . Therefore, also has finite differential entropy. From this and Lemma 1 it follows that all subsequent mutual informations will be finite.

We can write the following string of inequalities:

where (59a) holds since , (59b) follows from the data processing theorem applied to the linear transformation ( 9), (59c) follows from Sato's inequality (Lemma 2). Note that substituting for in (59c) and assuming that and the satisfy the differentiability assumption of Lemma 3 for all , one obtains [START_REF] Kullback | Information Theory and Statistics[END_REF] We now use the assumption that is Gaussian to eliminate the term in [START_REF] Kullback | Information Theory and Statistics[END_REF]. Let for all and , where the are Gaussian, identically distributed as but independent of all other random vectors. Then is identically distributed as , and applying (59c) to the and to , one obtains

where the last equality follows from the fact that by Lemma 4, the satisfy the differentiability assumption of Lemma 3. Now define Using [START_REF] Guo | Mutual information and MMSE in Gaussian channels[END_REF], inequality [START_REF] Borden | Some information theoretic saddlepoints[END_REF] is easily rewritten as that is for any . Since is differentiable at any by Lemma 4, it easily follows that is non-increasing in . Also, by Lemma 3, . Therefore, , which is the required MII [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF].

Finally, we show that the MII implies the EPI (8c). Since and for independent of , (48) can be rewritten as [START_REF] Diggavi | The worst additive noise under a covariance constraint[END_REF] Now replace by and let . The terms in the RHS of the above inequality are of the form , which tends to zero as by Lemma 3. This completes the proof.

B. Insights and Discussions

1) Relationship to Earlier Proofs: Of course, Theorem 1 could also be proved using the conventional techniques of Section II. In fact, it follows easily from either one of the where . Takano's condition is [START_REF] Takano | The inequalities of Fisher information and entropy power for dependent variables[END_REF] (74) for all . Johnson's improvement is given by the following weaker condition [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF]:

2

(S(X 1;t )S(X 2;t )) J(X 1;t )J(X 2;t )

for all . These conditions were found by generalizing the conventional approach presented in Section II, in particular Blachman's representation of the score (Section II-C-2). They are simplified below. The EPI for dependent variables finds its application in entropy-based blind source separation of dependent components (see, e.g., [START_REF] Caiafa | A minimax entropy method for blind separation of dependent components in astrophysical images[END_REF]).

B. A Generalized EPI for Dependent Random Vectors

In this section, we extend Theorem 1 to provide a simple condition on dependent random -vectors under which not only the original EPI holds, but also the EPI [START_REF] Guleryuz | Information-theoretic inequalities for contoured probability distributions[END_REF] for any choice of coefficients . Such stronger form should be more relevant in applications such as blind separation of dependent components, for it ensures that negentropy still satisfies the requirements (10) for a contrast objective function, for any type of linear mixture. Define [START_REF] Prelov | Higher order asymptotics of mutual information for nonlinear channels with non-Gaussian noise[END_REF] corresponding to [START_REF] Pinsker | Sensitivity of channel capacity[END_REF] with for all . Our condition will be expressed in terms of symmetric mutual information defined by [START_REF] Johnson | Information Theory and The Central Limit Theorem[END_REF], which serves as a measure of dependence between the components of a random vector.

Theorem 3: Let be any finite set of (dependent) random -vectors, let be defined by [START_REF] Prelov | Higher order asymptotics of mutual information for nonlinear channels with non-Gaussian noise[END_REF], and let be a white Gaussian random -vector independent of all other random vectors. If, for any and any real-valued coefficients , adding a small perturbation to the makes them "more dependent" in the sense that [START_REF] Prelov | Higher order asymptotics of mutual information for nonlinear channels with non-Gaussian noise[END_REF] then the MII [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] and the EPI (8) hold for these random vectors .

Proof: The only place where the independence of the is used in the proof of Theorem 1 is Sato's inequality (59c), which is used to the first order of and applied to random vectors of the form (76) for all . Therefore, it is sufficient that holds for all and any choice of to prove the MII and hence the EPI. Now from the proof of Lemma 2, the difference between both sides of this inequality is

The result follows at once. Note that it is possible to check (77) for a fixed choice of the coefficients to ensure that the EPI (8c) holds for these coefficients. Of course, ( 77) is obviously always satisfied for independent random vectors . In order to relate condition (77) to Takano and Johnson's ( 74), [START_REF] Pinsker | Information transmission over channels with additive-multiplicative noise[END_REF], we rewrite the former in terms of Fisher information as follows.

Corollary 2: For random variables , ( 77) is equivalent to [START_REF] Prelov | Second-order asymptotics of mutual information[END_REF] for all , where . Therefore, if this condition is satisfied then the MII [START_REF] Tulino | Monotonic decrease of the non-Gaussianness of the sum of independent random variables: A simple proof[END_REF] and the EPI (8) hold.

Proof: Let be a standard Gaussian random variable independent of , and define and , where

. The perturbations [START_REF] Prelov | Higher order asymptotics of mutual information for nonlinear channels with non-Gaussian noise[END_REF] ensure that the density of is smooth, so that the function is differentiable for all . Now (77) is equivalent to , that is,

. By (51) so can be rewritten as By de Bruijn's identity [START_REF] Costa | A new entropy power inequality[END_REF], this is equivalent to where , that is [START_REF] Verdú | On channel capacity per unit cost[END_REF] for any vector and . This shows that (77) is equivalent to the matrix inequality (78) as required.

We now recover Takano and Johnson's conditions [START_REF] Pinsker | Weak signal transmission over certain stationary non-Gaussian channels[END_REF], [START_REF] Pinsker | Information transmission over channels with additive-multiplicative noise[END_REF] from [START_REF] Prelov | Second-order asymptotics of mutual information[END_REF].

Lemma 5: In the case of two random variables , (74) and ( 75) are equivalent to (80) [START_REF] Pham | Entropy of a variable slightly contaminated with another[END_REF] respectively, where and minimize the quadratic forms and , respectively, over all vectors of the form .

Proof: Given a positive definite symmetric matrix , the general solution to is easily found by the Lagrangian multiplier method. One finds for all and , where are the entries of the inverse matrix . Particularizing this gives and up to appropriate proportionality factors, and ( 80), ( 81) are rewritten as (82) [START_REF] Vrins | Mixing and non-mixing local minima of the entropy contrast for blind source separation[END_REF] Meanwhile, expanding the RHSs in ( 74), ( 75) using Stein's identity [START_REF] Johnson | A conditional entropy power inequality for dependent variables[END_REF] gives where for Takano's condition and for Johnson's condition. Replacing yields [START_REF] Pham | Local minima of information-theoretic criteria in blind source separation[END_REF] and [START_REF] Vrins | Mixing and non-mixing local minima of the entropy contrast for blind source separation[END_REF], respectively. This proves the lemma.

Corollary 3: In the case of two random variables , (78) implies both Takano and Johnson's conditions [START_REF] Pinsker | Weak signal transmission over certain stationary non-Gaussian channels[END_REF], [START_REF] Pinsker | Information transmission over channels with additive-multiplicative noise[END_REF].

Proof: Condition (78) implies [START_REF] Verdú | On channel capacity per unit cost[END_REF] for any of the form . Setting yields Takano's condition [START_REF] Verdú | Spectral efficiency in the wideband regime[END_REF]. Replacing the RHS of the resulting inequality by the minimum over (achieved by ) gives Johnson's condition [START_REF] Pham | Entropy of a variable slightly contaminated with another[END_REF]. Thus, our condition ( 78) is stronger than Takano's or Johnson's. This is not surprising since it yields a stronger form of the EPI (8), valid for any choice of coefficients .

VI. LIU AND VISWANATH'S COVARIANCE-CONSTRAINED EPI

As aforementioned in the Introduction, all known applications of the EPI to source and channel coding problems [START_REF] Bergmans | A simple converse for broadcast channels with additive white Gaussian noise[END_REF]- [START_REF] Oohama | Gaussian multiterminal source coding with several side informations at the decoder[END_REF] involve an inequality of the form , where is Gaussian independent of . In this and the next section, we study generalizations of this inequality. We begin with Liu and Viswanath's generalized EPI for constrained covariance matrices.

A. Background

Recently, Liu and Viswanath [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF], [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] have suggested that the EPI's main contribution to multiterminal coding problems is for solving optimization problems of the form [START_REF] Ihara | On the capacity of channels with additive non-Gaussian noise[END_REF] where is Gaussian and the maximization is over all random -vectors independent of . The solution is easily determined from the EPI in the form (8c) applied to the random vectors and Since equality holds iff and are Gaussian with identical covariances, it follows that the optimal solution to ( 84) is Gaussian with covariance matrix . Clearly, the existence of a Gaussian solution to ( 84) is equivalent to the EPI for two independent random vectors and . Liu and Viswanath [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF], [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] have found an implicit generalization of the EPI by showing that (84) still admits a Gaussian solution under the covariance constraint , where is any positive definite matrix. The gave a "direct proof," motivated by the vector Gaussian broadcast channel problem, using the classical EPI, the saddlepoint property of mutual information [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF] and the "enhancement" technique for Gaussian random vectors introduced by Weingarten, Steinberg, and Shamai [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multiple-output broadcast channel[END_REF]. They also gave a "perturbation proof" using a generalization of the conventional techniques presented in Section II, namely, an integration over a path of the form of a generalized FII (17c) with matrix coefficients, using de Bruijn's identity and the Cramér-Rao inequality 13 . This and similar results for various optimization problems involving several Gaussian random vectors find applications in vector Gaussian broadcast channels and distributed vector Gaussian source coding [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF].

B. An Explicit Covariance-Constrained MII

We first give explicit forms of covariance-constrained MII and EPI, which will be used to solve Liu and Viswanath's optimization problem. Again, the same ideas as in the proof of Theorem 1 are easily generalized to prove the following covariance-constrained MII and EPI, using only basic properties of mutual information.

Theorem 4: Let be independent random -vectors with positive definite covariance matrices, and let be Gaussian random -vectors independent of and of each other, with covariances proportional to those of and , respectively:

, where . Assume that is Gaussian and are subject to the covariance constraint [START_REF] Pinsker | Calculation of the rate of information production by means of stationary random processes and the capacity of stationary channel[END_REF] Then for any real-valued coefficients normalized such that [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF] where we have noted . Furthermore, this inequality implies the following generalized EPI: [START_REF] Gallager | Information Theory and Reliable Communication[END_REF] where [START_REF] Mceliece | The Theory of Information and Coding, ser. Encyclopedia of Mathematics and its Applications[END_REF] Note that for the particular case , we have , the random vectors and are identically distributed, and Theorem 4 reduces to Theorem 1 for two random vectors.

Proof of Theorem 4: First define with covariance matrices . From [START_REF] Pinsker | Calculation of the rate of information production by means of stationary random processes and the capacity of stationary channel[END_REF], one successively has , and upon left and right multiplication by . Similarly, . Therefore, we can write [START_REF] Posner | Random coding strategies for minimum entropy[END_REF] where and are Gaussian and independent of and , respectively. We can now write the following string of inequalities:

where (90a) holds since , (90b) follows from the data processing theorem applied to the linear transformation ( 9), (90c) follows from Sato's inequality (Lemma 2), and (90d) follows by applying the identity (58) to the random vectors defined by [START_REF] Posner | Random coding strategies for minimum entropy[END_REF]. By Proposition 8, , where is Gaussian with covariance matrix . We now use the assumption that and let in the well-known expressions for mutual informations of Gaussian random vectors where and . Since and , we have , and therefore It follows from (90d) that [START_REF] Wyner | A theorem on the entropy of certain binary sequences and applications: Part I[END_REF] The rest of the proof is entirely similar to that of Theorem 1.

Here is a sketch. Write [START_REF] Wyner | A theorem on the entropy of certain binary sequences and applications: Part I[END_REF] for and , where is identically distributed as and independent of all other random vectors, for . Applying Lemma 3 to the RHS of the resulting inequality, this gives where is identically distributed as . By virtue of [START_REF] Palomar | Gradient of mutual information in linear vector Gaussian channels[END_REF], this can be written in the form , where Therefore, is nonincreasing, and , which is the required MII [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF]. This in turn can be rewritten in the form where is defined by [START_REF] Mceliece | The Theory of Information and Coding, ser. Encyclopedia of Mathematics and its Applications[END_REF] and tends to zero as by Lemma 3. This proves [START_REF] Gallager | Information Theory and Reliable Communication[END_REF] and the theorem.

It is now easy to recover Liu and Viswanath's formulation. [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] and [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF]): The maximization problem [START_REF] Ihara | On the capacity of channels with additive non-Gaussian noise[END_REF], subject to the covariance constraint , admits a Gaussian optimal solution . Proof: Let be the optimal solution to the maximization problem obtained by restricting the solution space within Gaussian distributions. Thus maximizes over all covariance matrices . As stated in [START_REF] Liu | An extremal inequality motivated by multiterminal information theoretic problems[END_REF] and shown in [START_REF] Weingarten | The capacity region of the Gaussian multiple-input multiple-output broadcast channel[END_REF], must satisfy the Karush-Kuhn-Tucker condition

Corollary 4 (Liu and Viswanath