0
$\begingroup$

It is well known that, maximizing the entropy of the joint distribution $P(x_1,...,x_n)$ of a random vector $(X_1,...,X_n)$ subject to equality constraints for the mean vector ($\mu$) and the variance covariance matrix ($\Sigma$) one obtains the multivariate normal $\mathcal{N}(\mu,\Sigma)$.

My question is about the case where one can impose only inequality constraint. In particular, I would be interested in relaxing the constraints on the off diagonal entries of the variance-covariance matrix (whereas I would be willing to mantain equality constraints on the vector of means and variances). Cases of interest, for my problem, would be:

  1. Constraining a certain number of covariances to zero, while letting the others unconstrained. I.e. studying the problem under $\Sigma_{ij}=0$ for some $i\neq j$
  2. Imposing, on top of the above constraint, also inequality constraints, specifying the sign of the entries, but not their value. I.e. allowing for inequality constraints of the form $\Sigma_{ij}\geq 0$ and $\Sigma_{ij}\leq 0$ for some $i\neq j$ (I guess strict inequalities may cause problems with the existence of the solution).

Any help or reference to results for this case would be much appreciated.

$\endgroup$
4
  • $\begingroup$ Why is case 1 any different from the general result you mention about multivariate normal being the entropy maximizing pdf given (arbitrary) mean and (arbitrary) covariance matrix? It only happens that in case 1 some of the covariance matrix elements are zero. It is not clear what you are searching for in case 2. Are you trying to find the covariance that results in maximum entropy under constraints? If so, the pdf is again normal with a well known formula for the entropy. Simply numerically optimize this formula with respect to the covariance matrix elements, subject to any constraints $\endgroup$
    – Stelios
    Feb 5, 2023 at 21:54
  • $\begingroup$ 1 is different, because I have less constraints. Which values for covariances will I put in the entries which are not constrained. For 2, the point is that I would like an analytic solution, rather than a numerical one $\endgroup$ Feb 6, 2023 at 8:09
  • $\begingroup$ You cannot let the diagonal entries of the covariance matrix unconstrained, the differential entropy grows without bounds with them. $\endgroup$
    – leonbloy
    Feb 6, 2023 at 22:22
  • $\begingroup$ Of course, you are right! Anyway I can actually constrain them to be below some value $\endgroup$ Feb 7, 2023 at 10:33

1 Answer 1

1
$\begingroup$

Whenever a diagonal covariance matrix satisfies the constraints you specify (with the addition of some constraint that forces the variances to remain finite), it will be the form of the maximizer of entropy. This is a direct consequence of the joint entropy of two random variables being bounded above by the sum of the marginal entropies with equality iff they are independent, which lets the joint distribution factor into the product of the marginals. This is also the case for a normal distribution with diagonal covariance.

It's very instructive to look at the connection between exponential family distributions and entropy. The general setup of a maximum entropy distribution optimization problem can be stated as

$$ \min_p -H(p) \\ \text{s.t.} \\ \int p(x) = 1 \\ E[f_i(x)] = c_i, i = 1 \ldots m $$

Writing this out with Lagrange multipliers for the constraints and applying a standard calculus of variations argument shows that the pdf is in the form of

$$ p(x) = \exp(\sum_{i=1}^m \theta_i f_i(x) - \lambda) $$

Where I've chosen the signs of the Lagrange multipliers $\theta$ and $\lambda$ to correspond with the conventions for canonical parameters and the log-normalizer, respectively. Since all the constraints are strict equality and the multipliers may take any value, the choice is arbitrary.

What happens if we add some inequality constraints? $E[g_i(x)] - d_i \leq 0, i = 1 \ldots n$. Now, we must add some more Lagrange multipliers $\mu_i$ but the sign is crucial, as these may only be nonnegative. This results in

$$p(x) = \exp(\sum_{i=1}^m \theta_i f_i(x) - \sum_{i = 1}^n \mu_i g_i(x) - \lambda)$$

Recall that a Lagrange multiplier may be interpreted as the derivative of the objective with respect to the value of the corresponding constraint-

$$ \frac{\partial (-H(p))}{\partial d_i} = -\mu_i$$

So a positive $\mu_i$ means that increasing $d_i$ increases the entropy, and it is zero it means that the constraint does not impact the solution at all- the maximizer of entropy when excluding the constraint already satisfies the constraint. This means one of two things for inequality constraints:

  1. The constraint is one that reduces entropy when introduced, and the entropy increases with $d_i$- the maximum is obtained with equality. In this case, the solution is exactly the same as if all inequality constraints with positive multipliers were equality.

  2. The constraint is already satisfied when the others are satisfied, the multiplier is zero, and the solution is the same as if the inequality constraint was not given.

So, if we can determine which of these cases is true for each inequality constraint, we can reduce the problem to one with all equality constraints by replacing the constraints in (1) with equality and dropping the constraints in (2). Doing that will typically require working out the specifics of the problem, but conveniently this guarantees that the family of the distribution is not changed by replacing some equality constraints with inequalities.

For a concrete example, the maximum entropy distribution over $\mathbb{R}^2$ with $E[x_1] = E[x_2] = 0$, $E[x_1^2] = 1$, $E[x_2^2] \leq 1$, and $E[x_1 x_2] \leq 0.5$ is a normal distribution. Starting with just the variance inequality constraint, we can use the fact that the density may be factored into the product of two marginal distributions which implies the entropy is additive, and see that increasing the variance of any of the independent margins increases the entropy. Therefore, $E[x_2^2] = 1$ is equivalent. Now, adding in $E[x_1 x_2] \leq 0.5$, we have two easy sanity checks. First, without that constraint, the ME distribution already has zero covariance since $x_1$ and $x_2$ are independent (which satisfies the inequality). Second, joint entropy is always less than or equal to the sum of marginal entropies, with equality iff they are independent- so making the covariance nonzero can only reduce the joint entropy. And for a constraint like $E[x_1 x_2] \geq d_{12}$, the greater the covariance, the lesser the entropy, making the maximizer have covariance equal to $d_{12}$.

Proving the results for higher numbers of dimensions is more involved. The Lagrange multipliers will be a function of the precision matrix (inverse of the covariance matrix) while the constraints are on the covariance, and the two need not have the same pattern of nonzero entries. However, since we've shown that the density is still a normal distribution and the entropy of a normal is available in closed form, you can simply calculate the gradient of the entropy evaluated at the covariance matrix for the maximizer without any inequalities and check whether or not changing the covariance towards the constraint increases entropy (in which case the constraint is saturated) or decreases (the constraint is already satisfied).

For convex minimization objectives, if all the equality constraints are affine and the inequality constraints are convex, then the space of feasible solutions is also convex. This is the underlying reason that the inequality constraints end up equivalent to an equality constraint or irrelevant to the solution- the convexity of the feasible set guarantees a unique maximum. Replacing the constraints with strict inequalities would not, taking for example the maximum entropy distribution over the reals with zero mean and variance strictly less than 1. Since the entropy increases with variance for a normal, making the variance arbitrarily close to 1 increases the entropy and the supremum of entropy is the same as at 1, but the set being open means the point obtaining that supremum is outside of it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .