Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we are given a matrix $V$ and our goal is to find non-negative matrices $W$ and $H$ such that $V \approx WH$. So we want to minimize $K(V || WH)$ (Kullback-Leibler Divergence) where $$K(V||WH) = ||V-WH||^{2} \tag{1}$$ or $$K(V||WH) = \sum_{i,j} \left[V_{i,j} \log \frac{V_{i,j}}{(WH)_{ij}}-V_{ij}+(WH)_{ij} \right] \tag{2}$$

depending on whether $\epsilon$ is normally distributed or poisson distributed respectively. Note that $\epsilon$ is noise. We want to minimize this subject to $W,H \geq 0$. For $K(V||WH)$ based on (1), we get $$H_{ak}^{t+1} = H_{ak}^{t} \left(\frac{\sum_{i}V_{ik} W_{ia}}{\sum_{i} W_{ia} \left(\sum_{b} W_{ib} H_{bk}^{t} \right)} \right)$$ and$$W_{ia}^{t+1} = H_{ia}^{t} \left(\frac{\sum_{i}H_{ak} V_{ik}}{\sum_{i} \left(\sum_{b} W_{ib} H_{bk}^{t} \right) H_{ak}} \right)$$

For $K(V||WH)$ based on (2), we get $$H_{ak}^{t+1} = H_{ak}^{t} \left(\frac{\sum_{i} \left(\frac{V_{ik}}{\sum_{b} W_{ib} H_{bk}^{t}} \right) W_{ia}}{\sum_{i} W_{ia}} \right)$$ and

$$W_{ia}^{t+1} = W_{ia}^{t} \left(\frac{\sum_{i} \left(\frac{V_{ik}}{\sum_{b} W_{ib}^{t} H_{bk}} \right) H_{ak}}{\sum_{k} H_{ak}} \right)$$

Why should these be the update rules? Are these iterations basically the best unbiased estimators for $W$ and $H$?

Added. When we factor $V$ into two non-negative matrices $W$ and $H$, we ultimately want to minimize the error between $V$ and $WH$. In other words $V = WH+\epsilon$ and we want to minimize $\epsilon$ which is the error term. We can assume that this error $\epsilon$ is normally distributed or poisson distributed. This is how we get $K(V||WH)$.

share|improve this question
I find this question very strangely phrased. It says "depending on whether $\epsilon$ is normally distributed or poisson distributed" when nothing called $\epsilon$ has been mentioned, nor is it mentioned later! What is $\epsilon$ and what does it have to do with these matrices, and how are we supposed to understand the question without knowing that?? –  Michael Hardy Jan 5 '12 at 23:03
@MichaelHardy: I have updated the question. –  Thomas Jan 5 '12 at 23:10
You said "Note that $\epsilon$ is noise", but nothing specific about where it enters the situation until much further down where you wrote "Added." It is still at best vaguely written. Also, we're to estimated $W$ and $H$, rather than the product $WH$. There can be many ways to factor $WH$. Are there any grounds to prefer one? My suspicion is that you read something that might say that one of $W$ and $H$ is to be estimated and the other is known, or else says each is to have certain properties. –  Michael Hardy Jan 5 '12 at 23:58
@MichaelHardy: We simultaneously update $W$ and $H$. So we are given initial $W$ and then find $H$. We do this back and forth. –  Thomas Jan 6 '12 at 0:40
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.