7
$\begingroup$

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

Question:

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 ?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.