8
$\begingroup$

I'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough.

My approach was to take the Taylor series at $x=\frac{1}{4}$, cut it off as a quadratic, then find the inverse of that. That yields

$$H_2^{-1}(x) \approx -\frac{1}{16} \, \sqrt{-96 \, x \log\left(2\right) + 9 \, \log\left(3\right)^{2} - 72 \, \log\left(3\right) + 96 \, \log\left(4\right)} + \frac{3}{16} \, \log\left(3\right) + \frac{1}{4}$$

Unfortunately, that's a pretty bad approximation and it's complex at $H_2^{-1}(1)$. What other approaches can I take?

[1] I originally forgot to write the base 2 subscript (I added that in a later edit)

|cite|improve this question
$\endgroup$
6
$\begingroup$

A rather coarse approximation of $H_2(x)$ on the said interval is $4 \log(2) x(1-x)$. Hence a crude approximation for the inverse is: $$ H_2^{-1}(y) \approx \frac{1}{2} \left(1- \sqrt{1-\frac{y}{\log(2)}}\right) = \frac12\frac{y}{\log(2) + \sqrt{\log(2)\left(\log(2)-y\right)}} $$ This initial approximation should be refined with Newton-Raphson method.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! How did you come up with $H_2(x) \approx 4 \log(2) x (1-x)$? $\endgroup$ – Red Aug 29 '12 at 3:17
  • 2
    $\begingroup$ The entropy is symmetric function of $x$, suggesting to approximate it by a polynomial in $x(1-x)$. $\endgroup$ – Sasha Aug 29 '12 at 3:19
  • 1
    $\begingroup$ @Red I meant symmetric around $x=1/2$. $\endgroup$ – Sasha Aug 29 '12 at 3:27
  • $\begingroup$ +1. A slightly better approximation would be to choose $a$ such that $$\int_0^1 \left(H_2(x) - ax(1-x) \right)^2 dx$$ is minimized. This gives us $a= \dfrac{35}{12} \approx 2.91667$ as opposed to $a = 4 \log(2) \approx 2.7726$. Sasha's $4 \log 2$ ensures that the approximation is always $\leq H_2(x)$, whereas the above approximation optimizes the choice over the entire domain. $\endgroup$ – user17762 Nov 28 '12 at 23:53
4
$\begingroup$

A nice approximation I found in this thesis:

$ \frac{x}{2 \log_2 (6/x)} \leq H_2^{-1}(x) \leq \frac{x}{ \log_2 (1/x)}$

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I suggest you use the remez command in Chebfun (http://www.chebfun.org/) to compute a polynomial that approximates this function very well. Your question is closely connected to approximation theory, and this very user-friendly software should be able to give you anything you want. :)

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.