Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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
add comment

1 Answer

Let $F(W,H)$ denote the objective function (squared loss, or KL). These updates are designed to create a sequence $(W^t,H^t)$ such that $F(W^{t+1},H^{t+1})$ is monotonically decreasing (or nonincreasing, if we start at a stationary point, for example).

Both updates can be derived by using the separability of the objective functions, and then appealing to the Majorize-Minorize (MM) approach (of which the famous EM algorithm is a special case).

You can have a look at Generalized Nonnegative Matrix Approximations with Bregman Divergences by Dhillon & Sra, (2005), where this idea is developed for more general objective functions.

I don't think that one can say much about these leading to "best unbiased" estimators or the like, but I don't know that stuff too well to comment more precisely.

share|improve this answer
add comment

Your Answer

 
discard

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

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