# How to solve for the minimum KL Divergence when the distribution is discrete?

Say we have a simple case of $$p(x,y)$$ is a 3x3 matrix: $$\begin{bmatrix} 1/6 & 0 & 0 \\ 1/6 & 3/6 & 0 \\ 0 & 0 & 1/6 \end{bmatrix}$$

And $$q(x,y)=q(x)q(y)$$. If I'm trying to solve for the form of $$q_x$$ and $$q_y$$ that minimizes $$D_{KL}(q||p)$$, what's the best approach to solving this problem? I know that if the two distributions were continuous, I could use gradient descent or something similar, but without trying to brute force the solution here, I can't see the proper way to solve.

Lastly, I've been concerned about taking the $$D_{KL}(q||p)$$ when the two distributions do not have the same support (because of the 0's in the matrix above), but I read somewhere on SE that we can treat those $$\log(0)$$ terms as 0 although I remain unconvinced.

Your problem is about handling impossible events in KL-divergence. Your $$x$$ and $$y$$ notation is not useful here (though it might be relevant for your specific problem). We can flatten everything and call X = (x,y).

Let's start from the definition of KL divergence : $$D_{KL}(q\|p) = \sum _{X} q(X) \log\left(\frac{q(X)}{p(X)}\right)$$

It looks rather undefined as soon $$p(X)=0$$ or $$q(X)=0$$... Let's look at the calculus :

Case 1: $$q(X) = 0$$ and $$p(X)\neq 0$$ : In that case , $$\lim_{x\rightarrow 0}xlog(x) =0$$. Hence, we will count 0 in the sum.

Case 2: $$q(X) \neq 0$$ and $$p(X) = 0$$ : In that case , $$\lim_{x\rightarrow 0}log(1/x) =+ \infty$$. Hence, we will count $$+ \infty$$ in the sum.

Case 3: $$q(X) =0$$ and $$p(X) = 0$$ : Then, it is really undefined...

Now, let's look at some higher level interpretation. $$D_{KL}(q\|p)$$ quantifies how credible distribution $$p$$ is when we sample according to $$q$$.

Case 1: $$q(X) = 0$$ and $$p(X)\neq 0$$ : Since we sample according to $$q$$, we will never sample event $$X$$. Hence, it does not weight in $$D_{KL}(q\|p)$$.

Case 2: $$q(X) \neq 0$$ and $$p(X) = 0$$ : Since we sample according to $$q$$, a single sample of event $$X$$ tells us with absolute certainty that we are not sampling $$p$$. Hence, $$D_{KL}(q\|p)$$ is infinite.

Case 3: $$q(X) =0$$ and $$p(X) = 0$$ : $$X$$ is an event which does not happen in $$p$$ and $$q$$. So why would you put it in the sum in the first place?

For your specific case, you have a lot of $$0$$ in $$p$$. Hence, your KL-divergence will be infinite except if $$q$$ have the same zeros. Since you further assume that $$q(x,y) = q_x(x)q_y(y)$$, we have the following constraint :

$$q_x(1)q_y(2)=0$$ $$q_x(1)q_y(3)=0$$ $$q_x(2)q_y(3)=0$$ $$q_x(3)q_y(1)=0$$ $$q_x(3)q_y(2)=0$$

For instance : $$q_x = \left[1/2, 1/2, 0 \right]$$ and $$q_y = \left[1, 0, 0 \right]$$.