# Deriving Multiplicative Update Rules for NMF

How to derive the multiplicative update rules for the non-negative matrix factorization problem given by Lee and Seung.

Minimize $\left \| V - WH \right \|^2$ with respect to $W$ and $H$, subject to the constraints $W,H \geq 0.$

They have shown that the euclidean distance is non-increasing under multiplicative update rule but I am unable to figure out how the multiplicative update rules were derived. The multiplicative update rules are as follows:

\begin{equation} W_{i,j} \leftarrow W_{ij} \frac{(VH^T)_{ij}}{(WHH^T)_{ij}} \end{equation}

\begin{equation} H_{i,j} \leftarrow H_{ij} \frac{(W^TV)_{ij}}{(W^TWH)_{ij}} \end{equation}

$$\min_{W \in \mathbb{R}^{n \times k},H \in \mathbb{R}^{k \times m}} \left \| V- WH \right \|^{2}_F \text{ s.t. }W,H \geq 0$$

$$\;\;\;\;\;\;Tr((V-WH)^T(V-WH)) \;\;\;\;\;\; \scriptsize \left [ \left \|X \right \|^2 = Tr(X^TX) \right ]$$

$$Tr((V^T - H^TW^T)(V-WH) ) = Tr( V^TV - V^TWH - H^TW^TV + H^TW^WWH)$$

using $$Tr(A+B) = Tr(A) + Tr(B)$$ we get,

$$Tr( V^TV) - Tr(V^TWH) - Tr(H^TW^TV) + Tr(H^TW^TWH) \;\;\;\;\;\; (1)$$

The non-negative matrix factorization problem is non-convex in W and H but it is convex in only W or only H. To optimize the above problem, we use a block coordinate descent scheme where we optimize with respect to $$W$$ first while keeping $$H$$ fixed and then vice versa. $$W \leftarrow W - \eta_W \cdot \nabla_W f(W,H)$$ $$H \leftarrow H - \eta_H \cdot \nabla_H f(W,H)$$

Thus to solve the given problem, we need the derivatives of Eq. 1 with respect to $$W$$ and $$H$$. Since the terms in the equation are in trace form, it is simpler to get the derivatives using a few linear algebra rules.

The derivative of each term with respect to W,

$$\nabla_WTr(V^TV) = 0$$
$$\nabla_WTr(V^TWH) = \nabla_WTr(HV^TW) = (HV^T)^T = VH^T \;\;\;\;\;\;\;\;\;\; \scriptsize \left [ \nabla_X Tr(AX) = A^T \right ]$$
$$\nabla_WTr(H^TW^TV) =\nabla_WTr(VH^TW^T) = VH^T \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\, \scriptsize \left [ \nabla_X Tr(X^TA) = A \right ]$$
$$\nabla_W Tr(H^TW^TWH) = \nabla_W Tr(WHH^TW^T)= W((HH^T)^T + HH^T) = 2WHH^T \;\;\; \scriptsize \left [ \nabla_X Tr(XAX^T) = X(A+A^T) \right ]$$

The derivatives with respect to H can computed similarly. Thus,

$$\nabla_W f(W,H) = -2VH^T + 2WHH^T$$ $$\nabla_H f(W,H) = -2W^TV + 2W^TWH$$

Using the above derivatives, $$W \leftarrow W + \eta_W \cdot (VH^T - WHH^T)$$ $$H \leftarrow H + \eta_H \cdot (W^TV - W^TWH)$$

The constant $$2$$ can be adjusted in the learning rate and thus can be ignored for now. Traditionally in gradient descent, the learning rates are positive but since the subtraction of terms in the update rules can lead to negative elements, Lee and Seung in the above mentioned paper, proposed to use adaptive learning rates to avoid subtraction and thus the production of negative elements. The learning rates are defined in such a way that there is no subtraction in the update rules. Thus if we set $$\eta_W = \frac{W}{WHH^T}$$ and $$\eta_H = \frac{H}{W^TWH}$$, we arrive at the given update rules.

Another way to avoid subtraction and get the multiplicative update rule is to use the form,

$$\theta \leftarrow \theta \cdot \frac {\nabla_{\theta}^{-} f(\theta)}{\nabla_{\theta}^{+} f(\theta)}$$

where $$\nabla_{\theta}^{-} f(\theta)$$ and $$\nabla_{\theta}^{+} f(\theta)$$ are the negative terms and the positive terms, respectively, of the gradient $$\nabla_{\theta} f(\theta)$$.

Using the above mentioned formula and the derivatives produced earlier, we get the following update rule,

$$W \leftarrow W \cdot \frac{(VH^T)}{(WHH^T)}$$ $$H \leftarrow H \cdot \frac{(W^TV)}{(W^TWH)}$$

Lee and Seung provided the proof of convergence for these rules in the above mentioned paper.

A particularly simple explanation can be found in The Why and How of Nonnegative Matrix Factorization:

The authors use $$X$$ as $$V$$ and $$F(W,H) = \| X - WH\|^2$$. The following is from section on multiplicative update (its relation with gradient descent).

[...] Another more intuitive interpretation is as follows: we have that

$$\frac{[XH^T]_{ik}}{[WHH^T]_{ik}} \geq 1 \iff (\nabla_WF)_{ik} \leq 0$$

Therefore, in order to satisfy [first order optimality condition], for each entry of W, the MU either (i) increase it if its partial derivative is negative, (ii) decrease it if its partial derivative is positive, or (iii) leave it unchanged if its partial derivative is equal to zero.

The paper also contains another explanation before that one, but I find this one the most straightforward.