In the Non-Negative Matrix factorization (NMF), you basically compute an approximation of a given matrix $V \in \mathbb{R}_{+}^{n \times m}$ into matrices $W$ and $H$ such that $W \in \mathbb{R}_{+}^{n \times r}$ and $H \in \mathbb{R}_{+}^{r \times m}$. Or in other words, $V \approx WH$. For the Sparse NMF with sparsity parameter $\lambda\ge 0 $ and sparsity function $g$, you minimize a cost function of this form: $$F(W, H) = \frac{1}{2}\|V - \bar W H\|^2 + \lambda\sum_{ij}g\left(H_{ij}\right) \qquad\text{where } \bar W =\frac W {\|W\|}$$

And $\|\ldots\|$ can be any differentiable norm. For $g(H_{ij}) =H_{ij}$, the steps for updating $H$ and $W$ are suggested here as follows for :

\begin{align}H_{ij} \longleftarrow H_{ij}&\odot\frac{V_i^T \bar W_j}{R_i^T\bar W_j + \lambda}\\ W_j \longleftarrow W_j&\odot\frac{\sum_i H_{ij}\left[V_i + \left(R_i^T\bar W_j\right)\bar W_j\right]}{\sum_i H_{ij}\left[R_i + \left(R_i^T\bar W_j\right)\bar W_j\right]}\end{align}

Where $R = WH$ and the matrix division and the $\odot$ multiplication are done element-wise.

In this paper, it is suggested to accelerate the convergence as follows:

To speed up the convergence, the multiplicative term can be exponentiated with an acceleration parameter $\delta$ larger than one. For each iteration the costfunction is evaluated and if the cost is smaller than in the previous iteration, $\delta$ is increased and if it is larger, then $\delta$ is decreased.

This is done in the $H$ update step. Following the notations of the updates above, this will be as follows: $$H_{ij} \longleftarrow H_{ij}\odot\left(\frac{V_i^T \bar W_j}{R_i^T\bar W_j + \lambda}\right)^\delta$$


How can one guarantee that with this acceleration we'll have fewer computational steps until convergence than without. Or how to ensure a minimum number of increasing and decreasing of $\delta$ until convergence ?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.