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)

3 Answers 3

6

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.

  • 0
    +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.2012-11-28
4

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)}$

1

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. :)