A survey on surrogate approaches to non-negative matrix factorization (Q1633790)

Let $M$ be an $n\times m$ matrix with real non-negative entries. Choose an integer $p\ll\min\left\{ n,m\right\}$. The non-negative matrix factorization problem (NMF) is to find non-negative matrices $K$ and $X$ where $K$ is $n\times p$, $X$ is $p\times m$ and $M$ is approximately equal to $KX$. This approximates $M$ by a non-negative matrix of rank at most $p$. For example, if we use the Frobenius norm then we want to compute non-negative $K\ $and $X$ such that $\left\Vert M-KX\right\Vert _{F}^{2}$ is minimized. Non-negativity is a awkward side condition so the minimization problem is often replaced by a minimization of an objective function of the form $F(K,X):=\left\Vert M-KX\right\Vert _{F}^{2}+\Phi(K,X)$ where $\Phi(K,X)$ is a penalty function which becomes large whenever $K$ or $X$ has a negative entry. Minimization of this latter function is carried out iteratively in a series of steps in which one of $K$ or $X$ is kept fixed and the other modified to reduce the size of the objective function. In practice this last computation is carried out by replacing $F(K,X)$ at each step by a simpler function called a surrogate functional. The overall process is sometimes referred to as an MM-algorithm (see, for example, [\textit{D. R. Hunter} and \textit{K. Lange}, ``A tutorial on MM algorithms'' Am. Stat. 58, 30--37 (2004; \url{doi:10.1198/0003130042836})]). This survey paper explains some of the principles used to carry out the computation for the NMF problem giving examples.