Deriving KL-Divergence Multiplicative Updates

Why the KL Updates Have a Ratio Form

For nonnegative measurements, a large discrepancy can matter differently when the observed value is small than when it is large. Generalized KL loss captures that relative discrepancy while allowing entries of the data matrix to be zero. This tutorial derives the corresponding multiplicative updates for the two nonnegative factors and shows how to check an update numerically.

Let $X$ be an $n \times p$ matrix with nonnegative entries, and approximate it by $WH$, where $W$ is $n \times r$, $H$ is $r \times p$, and $W,H$ are elementwise nonnegative. Write $y_{ij}=(WH)_{ij}=\sum_{k=1}^r W_{ik}H_{kj}$. The generalized KL objective is a loss between $X$ and its reconstruction $WH$; minimizing it does not, by itself, imply a particular probabilistic model for the data.

Definition: The generalized KL divergence loss for nonnegative matrices $X$ and $Y$ is $$ D_{\mathrm{KL}}(X\|Y)=\sum_{i=1}^{n}\sum_{j=1}^{p}\left[X_{ij}\log\left(\frac{X_{ij}}{Y_{ij}}\right)-X_{ij}+Y_{ij}\right]. $$ A term with $X_{ij}=0$ is defined by continuity as $Y_{ij}$. To obtain a finite loss, $Y_{ij}$ must be positive wherever $X_{ij}>0$.

The optimization problem here is to minimize $D_{\mathrm{KL}}(X\|WH)$ over nonnegative $W$ and $H$. For the derivations below, assume the factors are strictly positive initially, so each $y_{ij}>0$. Also require that the denominators in the updates are positive. Strictly positive factors satisfy these conditions when $r\geq1$; zero entries in $X$ are allowed.

Elementwise Gradients and the Updates

For positive $y_{ij}$, differentiating one loss term with respect to its reconstruction gives $\partial D_{\mathrm{KL}}/\partial y_{ij}=1-X_{ij}/y_{ij}$. Since $\partial y_{ij}/\partial W_{ik}=H_{kj}$, the chain rule gives the gradient for each entry of $W$. Interchanging the roles of the two factors gives the gradient for each entry of $H$.

\frac{\partial D_{\mathrm{KL}}}{\partial W_{ik}} =\sum_{j=1}^{p}H_{kj}\left(1-\frac{X_{ij}}{(WH)_{ij}}\right), \qquad \frac{\partial D_{\mathrm{KL}}}{\partial H_{kj}} =\sum_{i=1}^{n}W_{ik}\left(1-\frac{X_{ij}}{(WH)_{ij}}\right).

Each gradient is the difference between a nonnegative “reconstruction” contribution and a nonnegative “data-to-reconstruction” contribution. For $W_{ik}$, these are $\sum_j H_{kj}$ and $\sum_j H_{kj}X_{ij}/y_{ij}$. Setting the gradient to zero suggests equating them, or multiplying $W_{ik}$ by their ratio. This gives the multiplicative update; the corresponding argument applies to $H_{kj}$.

Update rule: With the other factor held fixed, the generalized KL multiplicative updates are $$ W_{ik}\leftarrow W_{ik} \frac{\displaystyle\sum_j H_{kj}X_{ij}/(WH)_{ij}} {\displaystyle\sum_j H_{kj}}, \qquad H_{kj}\leftarrow H_{kj} \frac{\displaystyle\sum_i W_{ik}X_{ij}/(WH)_{ij}} {\displaystyle\sum_i W_{ik}}. $$ In each update, compute $WH$ and use the current values of the factors. A matrix form for the $W$ update is $W\leftarrow W\odot[((X\oslash WH)H^\mathsf{T})/(\mathbf{1}H^\mathsf{T})]$; the $H$ update is $H\leftarrow H\odot[W^\mathsf{T}(X\oslash WH)/(W^\mathsf{T}\mathbf{1})]$. The divisions and products in these matrix expressions are elementwise.

The ratios are nonnegative, so positive factors remain nonnegative after an update. The ratio argument from the gradient alone motivates the rule but does not prove that an arbitrary gradient-splitting update will decrease the objective. For this KL objective, monotonicity can be justified by a majorizing function for each factor block.

Why a Block Update Does Not Increase the Loss

Consider updating one row $w_k=(W_{i1},\ldots,W_{ir})$ of $W$, with the row index $i$ fixed and $H$ held fixed. At the current strictly positive factors, write $y_{ij}^{(t)}=\sum_k W_{ik}^{(t)}H_{kj}$, and define $q_{kj}=W_{ik}^{(t)}H_{kj}/y_{ij}^{(t)}$. For each $j$, these values are nonnegative and sum to one. Convexity of $-\log z$ implies $-\log(\sum_k q_{kj}z_k)\leq\sum_k q_{kj}(-\log z_k)$ for positive $z_k$. Taking $z_k=W_{ik}H_{kj}/q_{kj}$ bounds the negative logarithm in the KL loss by a function that touches the loss at the current row. The linear $Y$ terms are already linear in $W_{ik}$. Thus this bound is a majorizer: it is at least the objective for every candidate row and equals it at the current row.

For a component $k$, the part of that majorizer depending on $W_{ik}$, apart from constants, has the form $-A_{ik}\log W_{ik}+B_kW_{ik}$, where $A_{ik}=\sum_j X_{ij}q_{kj}$ and $B_k=\sum_j H_{kj}$. Its derivative is $-A_{ik}/W_{ik}+B_k$, so its minimum is at $W_{ik}=A_{ik}/B_k$. Substitution of $q_{kj}$ gives $A_{ik}=W_{ik}^{(t)}\sum_j H_{kj}X_{ij}/y_{ij}^{(t)}$, exactly the stated multiplicative update. Because the majorizer equals the original loss at the current point and bounds it above elsewhere, minimizing the majorizer cannot increase the original loss. The same argument applies to an $H$ block. Therefore, sequential block updates do not increase the objective under the stated positivity and denominator conditions.

Worked Updates

Worked Example: One Row and Two Measurements

Suppose the hypothetical observed row is $X=(4,0)$, with current $W=(1)$ and $H=(1,2)$. The reconstruction is $Y=(1,2)$, which is positive in both positions. For the single entry of $W$, the gradient is $\sum_j H_{1j}(1-X_{1j}/Y_{1j})$.

Gradient and update. The gradient is $1(1-4/1)+2(1-0/2)=-3+2=-1$. The update multiplier is $(1\cdot4/1+2\cdot0/2)/(1+2)=4/3$, so $W$ changes from $1$ to $4/3$. The negative gradient is consistent with increasing $W$.

Loss check. Initially the loss is $4\log(4/1)-4+1+2=4\log4-1\approx4.545$. After the update, $Y=(4/3,8/3)$, and the loss is $4\log(4/(4/3))-4+4/3+8/3=4\log3\approx4.394$. The loss decreases, as expected for this block update. The units of $X$, $Y$, and the loss terms are those of the hypothetical count entries; the ratios inside logarithms are dimensionless.

Worked Example: Updating Both Factors for a Count Matrix

Consider the hypothetical count matrix $X=\begin{pmatrix}4&0\\1&3\end{pmatrix}$, with rank $r=1$, $W=\begin{pmatrix}1\\2\end{pmatrix}$, and $H=\begin{pmatrix}1&1\end{pmatrix}$. All factor entries are positive, and $Y=WH=\begin{pmatrix}1&1\\2&2\end{pmatrix}$ is positive, so the ratios are defined, including at the zero count.

Update $W$. The elementwise count-to-reconstruction ratios are $X/Y=\begin{pmatrix}4&0\\0.5&1.5\end{pmatrix}$. For the first row of $W$, the numerator is $1(4)+1(0)=4$, and the denominator is $1+1=2$. Thus $W_{11}\leftarrow1(4/2)=2$. For the second row, the numerator is $1(0.5)+1(1.5)=2$, and the denominator is $2$, giving $W_{21}\leftarrow2(2/2)=2$. After this block update, $W=(2,2)^\mathsf{T}$ and $Y=\begin{pmatrix}2&2\\2&2\end{pmatrix}$.

Update $H$. Use this updated $W$. The new ratios are $X/Y=\begin{pmatrix}2&0\\0.5&1.5\end{pmatrix}$. The numerator for $H_{11}$ is $2(2)+2(0.5)=5$, and its denominator is $2+2=4$, so $H_{11}\leftarrow1(5/4)=1.25$. For $H_{12}$, the numerator is $2(0)+2(1.5)=3$, and the denominator is $4$, so $H_{12}\leftarrow1(3/4)=0.75$. The resulting reconstruction is $Y=\begin{pmatrix}2.5&1.5\\2.5&1.5\end{pmatrix}$.

Check the objective. Initially, its four contributions sum to $[4\log4-4+1]+[1]+[\log(1/2)-1+2]+[3\log(3/2)-3+2]\approx4.068$. After the $W$ update, they sum to $[4\log2-4+2]+[2]+[\log(1/2)-1+2]+[3\log(3/2)-3+2]\approx3.296$. After the $H$ update, the sum is $[4\log(4/2.5)-4+2.5]+[1.5]+[\log(1/2.5)-1+2.5]+[3\log(3/1.5)-3+1.5]\approx3.043$. The loss falls at both steps. These are evaluations of the stated objective, not evidence that the factors have reached a global minimum.

Worked Example: A Zero Entry Can Be Locked

Suppose one row of a hypothetical matrix is $X=(1,3)$, with two component rows of $H$ both equal to $(1,1)$, and current $W=(1,0)$. The reconstruction is $Y=(1,1)$, so the loss and update ratios are defined despite one zero factor.

For the second component, the gradient is $1(1-1/1)+1(1-3/1)=-2$, which points toward increasing that component. Its multiplicative update factor is $(1\cdot1/1+1\cdot3/1)/(1+1)=2$. But the updated entry is $0\cdot2=0$: a zero remains zero. With a small positive starting value $W_2=0.1$ instead, while keeping $W_1=1$, the reconstruction is $(1.1,1.1)$, and the multiplier for $W_2$ is $[(1/1.1)+(3/1.1)]/2\approx1.818$, producing $W_2\approx0.1818$. Strictly positive initialization avoids this particular lock.

Assumptions, Diagnostics, and Alternatives

The monotonicity argument applies to the stated KL objective when each update uses the current reconstruction, entries with positive counts have positive reconstructions, and the update denominators are positive. A zero data entry is not a problem: its contribution to the loss is the reconstructed value, and its ratio $X_{ij}/y_{ij}$ is zero when $y_{ij}>0$. If a reconstruction is zero where the data are positive, the loss is infinite and the ratio is undefined. Do not handle that case by silently replacing a denominator with zero; use a valid positive initialization or otherwise address the modeling and numerical issue explicitly.

A practical implementation should monitor the objective after each block or full iteration, verify that all factor entries remain nonnegative, and check that $WH$ is positive wherever $X$ is positive. Small floating-point safeguards can be necessary, but adding an arbitrary constant to all entries changes the computed objective and should be documented. Track convergence using both changes in loss and factor updates: a small loss change alone does not establish that the factors are uniquely determined or scientifically meaningful.

Approach	What it optimizes or provides	Practical distinction
KL multiplicative updates	Generalized KL loss with nonnegative factors	Simple elementwise ratios; positive initialization is important to avoid zero locking.
Frobenius multiplicative updates	Squared reconstruction error	Uses a different loss and therefore weights discrepancies differently.
Alternating nonnegative least squares or projected gradient	Constrained block optimization or gradient steps	Can offer different convergence and numerical behavior, but requires solving or controlling nonnegative subproblems.

The KL updates are computationally convenient, but they do not guarantee a global minimum: the factorized objective is nonconvex jointly in $W$ and $H$. Different starts can reach different stationary solutions, and zero entries can prevent movement in directions that would improve the loss. A useful diagnostic is to compare final losses across multiple valid positive starts while checking reconstruction quality and the intended scientific interpretation. Choosing the KL loss rather than a squared-error loss is a modeling choice about discrepancy, not a guarantee that the count-generating mechanism has been correctly specified.

Common Mistakes

Using the wrong reconstruction in a ratio. Compute $X/(WH)$ from the current factors for the block being updated; after updating $W$, recompute it before updating $H$.
Treating the ratio as an additive gradient step. The update multiplies a factor entry by a nonnegative ratio; it is not $W_{ik}-\eta\,\partial D/\partial W_{ik}$.
Allowing a zero reconstruction under a positive observation. This makes the objective infinite and the update ratio undefined. Ensure valid support before applying the formula.
Assuming a zero factor can revive. Multiplication by a finite ratio leaves zero at zero. Strictly positive initialization avoids this specific problem.
Calling a decreasing loss proof of global optimality. The block updates can be monotone while still converging to a non-global stationary point.

Key takeaway: Under generalized KL loss, each factor entry is multiplied by a ratio of a data-weighted contribution to a reconstruction-weighted contribution. Correctly computed block updates preserve nonnegativity and do not increase this objective under the stated conditions, but positivity, zero locking, and local minima still require attention.

Check Your Understanding

Answer each question, then compare with the solutions.

For $X_{ij}=0$ and $Y_{ij}=2$, what is the contribution to generalized KL loss?
For a single entry $W_{ik}$, explain why its update denominator is $\sum_j H_{kj}$.
If a positive count is reconstructed as zero, can the multiplicative ratio be used directly? Why or why not?
Does a nonincreasing KL objective prove that the final factors are a global minimizer?

Solutions. (1) The contribution is $Y_{ij}=2$, using the continuous convention for the zero-count term. (2) It is the sum of the nonnegative linear reconstruction contributions $H_{kj}$ in the gradient; it must be positive for the stated ratio update. (3) No. The loss is infinite and $X_{ij}/Y_{ij}$ is undefined, so the reconstruction must be made valid before applying the update. (4) No. Monotonicity rules out an increase at an update under the assumptions, but the factorized objective is nonconvex jointly and the algorithm need not find a global minimum.