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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

A good approximation of $$y=H_2(x) = -x \log_2 (x) - (1-x) \log_2 (1-x)$$ is given by $$y \sim (4x(1-x))^{3/4}\implies x\sim \frac{1}{2} \left(1-\sqrt{1-y^{4/3}}\right)$$ for $0\leq x \leq \frac 12$. This is avery good starting point for Newton method. $$x_0=\frac{1}{2} \left(1-\sqrt{1-y^{4/3}}\right)\implies x_1=\frac{\log \left(1+\sqrt{1-y^{4/3}}\right)+(y-1) \log (2)}{2 \tanh ^{-1}\left(\sqrt{1-y^{4/3}}\right)}$$ which is almost the solution.

Edit

Details about the approximation.

To match the end points and the maximum, a simple model is $$H_2 \sim [4x(1-x)]^a$$ Considering the norm $$\Phi(a)=\int_0^1 \Bigg[-([4x(1-x)]^a-\frac{(1-x) \log (1-x)}{\log (2)}-\frac{x \log (x)}{\log (2)} \Big]^2\,dx$$ we have the analytical expression of $\Phi(a)$. Computing its derivative and solving (numerically), for $a$, $\Phi'(a)=0$ using Newton method, the minimum is attained for $a=0.741967 \sim \frac 34$.

For $a=\frac 34$, $\Phi=0.0000180914$ while at the exact solution $\Phi=0.0000125374$. Making the root rational $a=\frac{762}{1027}$, we should almost exactly the optimal value of $\Phi$ (difference $=5.58\times 10^{-16}$).

If instead, we match the value of the second derivative at $x=\frac 12$, $a=\frac{1}{2 \log (2)}=0.721348$.

We can still improve working with the norm related to the inverse function itself. $$y=[4x(1-x)]^a \implies x_*=\frac{1}{2} \left(1-\sqrt{1-y^{1/a}}\right)$$ $$\Psi(a)=\int_0^1 \Big[y-H_2(x_*) \Big]^2\,dy$$ is minimum $(\Psi_\text{opt}=0.0000236224)$ when $a=0.746497$ still much closer to the selected $a=\frac 34$.

Using $a=\frac 34$ $$\int_0^1 \Big[y-H_2(x_0) \Big]^2\,dy=2.53 \times 10^{-5}$$ $$\int_0^1 \Big[y-H_2(x_1) \Big]^2\,dy=2.47 \times 10^{-9}$$