0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

$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).

$\endgroup$
4
  • $\begingroup$ 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})$? $\endgroup$
    – Jan
    Commented Aug 17, 2017 at 12:44
  • $\begingroup$ @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. $\endgroup$
    – Jenkar
    Commented Aug 17, 2017 at 12:57
  • $\begingroup$ 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}$$ $\endgroup$
    – Jan
    Commented Aug 19, 2017 at 8:19
  • $\begingroup$ 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? $\endgroup$
    – Jan
    Commented Aug 19, 2017 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.