0
$\begingroup$

I am interested in finding the histogram's weights that minimize the KL-divergence with a uniform distribution, with for extra constraint that the means of both distributions should be equal. The uniform distribution has arbitrary bounds, but its domain is a subset of the domain of the histogram.

If the uniform distribution is collapsed to a single point (dirac), my intuition tells me that the best histogram weights should be an interpolation between the two bins nearest to the location of the dirac.

The histogram can be defined as a mixture of uniform distributions: $$q_w(x) = \sum_{i=1}^N w_i \pi_i(x)$$ with $\pi_i(x) = \frac{1}{\left|D_i\right|}\mathbb{1}_{x \in D_i}$ the individual bins, and $D_i$ the domain of each bin. The domains never overlap.

The uniform distribution is set as $$p(x) = \frac{1}{b - a}\mathbb{1}_{x \in [a, b)}.$$

The problem consists of finding the sets of weights minimizing the KL-divergence with two constraints: $$\begin{array}{ll} \text{minimize} & KL(p || q_w) \\ \text{subject to}& \sum_{i=1}^N w_i = 1 \\ &\sum_{i=1}^N w_i \mu_i = \mu_p, \end{array}$$ with $\mu_i$ the means of each bin and $\mu_p$ the mean of the uniform distribution.

Setting up the Lagrange method: $$ \begin{equation}\begin{aligned} f(w) &= \int_a^b p(x) \log\left(\frac{p(x)}{q_w(x)}\right) dx \\ &= -\mathbb{H}[p] -\int_a^b p(x) \log\left(\sum_{i=1}^N w_i \pi_i(x)\right) dx \\ &= -\mathbb{H}[p] - \sum_{i=1}^N \int_{D_i} p(x) \log w_i dx - \sum_{i=1}^N \int_{D_i} p(x) \log \pi_i(x) dx \\ &= - \sum_{i=1}^N \int_{D_i} p(x) dx \log w_i + C \end{aligned}\end{equation}\tag{1}$$

$g(w) = \sum_{i=1}^N w_i - 1 \tag{2}$

$h(w) = \sum_{i=1}^N w_i \mu_i - \mu_p \tag{3}$

Taking the derivatives and equating to zero: $$\frac{\partial}{\partial w_i} f(w) = \lambda_1 \frac{\partial}{\partial w_i} g(w) + \lambda_2 \frac{\partial}{\partial w_i} h(w)$$

$$-\int_{D_i} p(x) dx \frac{1}{w_i} = \lambda_1 + \lambda_2 \mu_i \tag{4}$$

$$w_i = -\frac{\int_{D_i} p(x) dx}{\lambda_1 + \lambda_2 \mu_i}\tag{5}$$


I am adding a separator because I am not sure this part is correct. Using (4), $$\mu_i = -\frac{\int_{D_i} p(x) dx \frac{1}{w_i} + \lambda_1}{\lambda_2} \tag{6}.$$

Feeding (6) into the second constraint (3), $$\mu_p = \sum_{i=1}^N w_i \mu_i = -\sum_{i=1}^N w_i \frac{\int_{D_i} p(x) dx \frac{1}{w_i} + \lambda_1}{\lambda_2}$$

$$ \begin{equation}\begin{aligned} -\mu_p\lambda_2 &= \sum_{i=1}^N \int_{D_i} p(x) dx + w_i \lambda_1 \\ &= 1 + \lambda_1 \sum_{i=1}^N w_i \\ &= 1 + \lambda_1 \end{aligned}\end{equation}\tag{7}$$ The first integral is 1 because we're integrating over (the sum of) the full domain of p, and the sum of weights is 1 because of the first constraint (2).

So now I have $\lambda_1 = -1 -\mu_p\lambda_2$, thus (using (7) in (4)): $$-\int_{D_i} p(x) dx \frac{1}{w_i} = -1 -\mu_p\lambda_2 + \lambda_2 \mu_i = \lambda_2 (\mu_i - \mu_p) - 1$$


I wasn't able to find anything fruitful after that, I am unsure if it is possible to find $\lambda_2$, and find a solution the $w_i$. I think that the uniform distribution may be an issue since its domain is smaller than the histogram, rendering the problem ill-posed.
$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .