# Why W is transposed in the final form of multiplicative updates of NMF - $H^*=H * \frac{W^T\frac{V}{WH}}{W^T 1}$

For NMF using Kullback-Liebler divergence \begin{equation*} d_{\mathrm{KL}} (\mathbf{V}\ \vert\vert \mathbf{WH})\stackrel{\hbox{cst.}}{\hbox{=}} \sum_{ij}-V_{ij}\log\sum_{k}{(WH)_{ij}} + \sum_{ij}\sum_{k}{(WH)_{ij}} \end{equation*}

Jensen's inequality helps us derived updated $H^*_{kj}$ $$H^*_{kj} = \frac{\sum_{i}V_{ij}\pi_{ijk}}{\sum_i W_{ik}}$$

And $$\pi_{ijk} = \frac{W_{ik}H_{kj}}{\sum_k W_{ik}H_{kj}}$$

So that $$H^*_{kj} = H_{kj} * \frac{\sum_{i}(\frac{V}{WH})_{ij} W_{ik}}{\sum_i W_{ik}} \tag{1}$$

As the document written "These are multiplicative updates. in matrix form:" $$H^*=H * \frac{W^T\frac{V}{WH}}{W^T 1}\tag{2}$$

When $*$ is element-wise multiplication and 1 is matrix of 1 in $i*j$ dimension.

I wonder why the $W$ is transposed and $1$ is brought into (2) from (1)? I know the final result get the correct dimension of H as $k*j$. But I don't understand the reasons that allow it to change in this manner?

$W_{ik} = W^T_{ki}$

Hence \begin{align} H^*_{kj} &= \frac{\sum_i (\frac{V}{WH})_{ij}*W_{ik}}{\sum_i W_{ik}}\\ &=\frac{\sum_i (\frac{V}{WH})_{ij}*W^T_{ki}}{\sum_i W^T_{ki}} \\ &=\frac{\sum_i W^T_{ki} *(\frac{V}{WH})_{ij}}{\sum_i W^T_{ki}} \end{align}

This explains the how of the transposition. The why is simply to make the matrix form appear easily (since the goal matrix has dimension $k * j$) : the indices line up on the top ($ki * ij$) and the bottom part now starts with $k$, allowing a multiplication with that $1$ matrix of dimension $i * j$.

The $1$ does not change the equation : $W^T * 1$ is the matrix $(\sum_i W^T_{ai})$, with $k$ rows and $j$ columns (and every row contains $j$ time the same element, $\sum_i W^T_{ai}$, where $a$ is the row number).

• But does matrix multiplication can't switch? I mean $AB \neq BA$. Why does we can switch $W^T$ to be in front of $(V/WH)_{ij}$? And at last paragraph, do you mean $(∑_{i}W^T_{kj})$ instead of $(∑_{i}W^T_{ai})$?
– Jan
Commented Aug 17, 2017 at 12:44
• @Jan The thing is, this is not matrix multiplication at that point : it is a multiplication between two scalars ($(\frac{V}{WH})_{ij}$ and $W^T_{ki}$). Multiplication between scalars is commutative. And no, I do mean $(\sum_i W^T_{ai})$. It is a sum on the column of $W^T$. I used $a$ instead of $k$ to avoid confusion between index and dimension. Commented Aug 17, 2017 at 12:57
• I am so sorry @Jenkar. I just have another question. In your proof, at the end $W_T$ is $W_ki$ one. But in algorithm, why we can use original $W$ and transpose (just one time) to update? I mean we don't have to prep $W_ki$ first, and put in equation for transpose again, do we? I have sort of pseudocode example and it seems like we can do \begin{align} H^*_{kj} &= \frac{\sum_i W^T_{ik} *(\frac{V}{WH})_{ij}}{\sum_i W^T_{ik}} \end{align}
– Jan
Commented Aug 19, 2017 at 8:19
• My pseudocode example is link slide 98 and 101. In general as well, $$H^*=H * \frac{W^T\frac{V}{WH}}{W^T 1}$$ seems to imply the original $W$ without changing anything. Why is it?
– Jan
Commented Aug 19, 2017 at 8:23