2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.