# Non-negative matrix factorisation Non-negative matrix factorisation (NMF) consists in finding, given a non-negative matrix $V$, non-negative matrix factors $W$ and $H$ such that $ V \approx WH. $ This amounts to finding a basis $W$ that is optimised for the linear approximation of $V$. ## Cost functions Euclidean distance: $ \|A - B\|^2 = \sum_{ij} (A_{ij} - B_{ij})^2 $ Generalised Kullback-Leibler divergence: $ D(A\|B) = \sum_{ij} \left( A_{ij} \log \frac{A_{ij}}{B_{ij}} - A_{ij} + B_{ij} \right) $ ## Multiplicative update rules 1. $\| V - WH \|$ is non-increasing under the update rules $ H_{a\mu} \leftarrow H_{a\mu} \frac{(W^T V)_{a\mu}}{(W^T W H)_{a\mu}} \qquad W_{ia} \leftarrow W_{ia} \frac{(V H^T)_{ia}}{(W H H^T)_{ia}} $ 2. $D(V \| WH)$ is non-increasing under the update rules $ H_{a\mu} \leftarrow H_{a\mu} \frac{\sum_i \frac{W_{ia} V_{i\mu}}{(WH)_{i\mu}}}{\sum_k W_{ka}} \qquad W_{ia} \leftarrow W_{ia} \frac{\sum_i \frac{H_{a\mu}V_{i\mu}}{(WH)_{i\mu}}}{\sum_\nu H_{a\nu}} $ Both measures are invariant if and only if $W$ and $H$ are at a stationary point, and the multiplicative factor is 1 if $V = WH$. --- ## 📚 References - Lee, Daniel, and H. Sebastian Seung. [“Algorithms for Non-Negative Matrix Factorization.”](https://proceedings.neurips.cc/paper/2000/hash/f9d1152547c0bde01830b7e8bd60024c-Abstract.html) Advances in Neural Information Processing Systems, vol. 13, MIT Press, 2001. Neural Information Processing Systems.