Inverse of binary entropy function for $0 \le x \le \frac{1}{2}$

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)

-

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

-

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

-

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.

-
Thanks! How did you come up with $H_2(x) \approx 4 \log(2) x (1-x)$? – Red Aug 29 '12 at 3:17
The entropy is symmetric function of $x$, suggesting to approximate it by a polynomial in $x(1-x)$. – Sasha Aug 29 '12 at 3:19
@Red I meant symmetric around $x=1/2$. – Sasha Aug 29 '12 at 3:27
+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. – user17762 Nov 28 '12 at 23:53