# Nonnegative matrix factorization

(Difference between revisions)
 Revision as of 14:27, 28 September 2009 (edit)← Previous diff Current revision (17:40, 30 October 2016) (edit) (undo) (8 intermediate revisions not shown.) Line 1: Line 1: - Example from [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry], ch.4: + Exercise from [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry], ch.4: Given rank-2 nonnegative matrix Given rank-2 nonnegative matrix $X=\!\left[\!\begin{array}{ccc}17&28&42\\ [itex]X=\!\left[\!\begin{array}{ccc}17&28&42\\ 16&47&51\\ 16&47&51\\ - 17&82&72\end{array}\!\right],$ + 17&82&72\end{array}\!\right],[/itex] - + find a nonnegative factorization find a nonnegative factorization $X=WH\,$ $X=WH\,$ by solving by solving - $\begin{array}{cl}\mbox{find}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&W\,,\,H\\ + [itex]\begin{array}{cl}{\text find}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&W\,,\,H\\ - \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X\\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ + {\text subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &W\geq0\\ &H\geq0\\ &H\geq0\\ - &\mbox{rank}\,Z\leq2\end{array}$ + &{\text rank}\,Z\leq2\end{array}[/itex] which follows from the fact, at optimality, which follows from the fact, at optimality, - $Z^\star=\left[\!\begin{array}{c}I\\W\\H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I~~W^{\rm T}~H\,\textbf{]} + [itex] Z^*=\left[\!\begin{array}{c}I\\W\\H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I~~W^{\rm T}~H\,\textbf{]} \end{array}$ \end{array}[/itex] Use the known closed-form solution for a direction vector $Y\,$ to regulate rank (rank constraint is replaced) by [[Convex Iteration]]; Use the known closed-form solution for a direction vector $Y\,$ to regulate rank (rank constraint is replaced) by [[Convex Iteration]]; - set $_{}Z^\star\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^\mathbf{8}$ to an ordered diagonalization and + set $_{}Z^*\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^{\mathbf{8}}$ to a nonincreasingly ordered diagonalization and - $_{}U^\star\!=_{\!}Q(:\,,_{^{}}3\!:\!8)\!\in_{\!}\reals^{\mathbf{8}\times\mathbf{6}}$, + $_{}U^*\!=_{\!}Q(:\,,_{^{}}3:8)\!\in_{\!}\mathbb{R}^{\mathbf{8}\times\mathbf{6}}$, - then $Y\!=U^\star U^{\star\rm T}.$ + then $Y\!=U^* U^{*\rm T}.$

Line 31: Line 30: $\begin{array}{cl}\mbox{minimize}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&\langle Z\,,Y\rangle\\ [itex]\begin{array}{cl}\mbox{minimize}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&\langle Z\,,Y\rangle\\ - \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X\\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ + \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &W\geq0\\ &H\geq0\end{array}$ &H\geq0\end{array}[/itex] Line 37: Line 36: with with - $Y\!=U^\star U^{\star\rm T}.$ + $Y\!=U^* U^{*\rm T}.$ + Global convergence occurs, in this example, in only a few iterations.

## Current revision

Exercise from Convex Optimization & Euclidean Distance Geometry, ch.4:

Given rank-2 nonnegative matrix $LaTeX: X=\!\left[\!\begin{array}{ccc}17&28&42\\

 16&47&51\\

17&82&72\end{array}\!\right],$

find a nonnegative factorization $LaTeX: X=WH\,$ by solving

$LaTeX: \begin{array}{cl}{\text find}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&W\,,\,H\\ {\text subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &H\geq0\\ &{\text rank}\,Z\leq2\end{array}$

which follows from the fact, at optimality,

$LaTeX: Z^*=\left[\!\begin{array}{c}I\\W\\H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I~~W^{\rm T}~H\,\textbf{]} \end{array}$

Use the known closed-form solution for a direction vector $LaTeX: Y\,$ to regulate rank (rank constraint is replaced) by Convex Iteration;

set $LaTeX: _{}Z^*\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^{\mathbf{8}}$ to a nonincreasingly ordered diagonalization and $LaTeX: _{}U^*\!=_{\!}Q(:\,,_{^{}}3:8)\!\in_{\!}\mathbb{R}^{\mathbf{8}\times\mathbf{6}}$, then $LaTeX: Y\!=U^* U^{*\rm T}.$

In summary, initialize $LaTeX: Y=I\,$ then alternate solution of

$LaTeX: \begin{array}{cl}\mbox{minimize}_{A\in\mathbb{S}^3,\,B\in\mathbb{S}^3,\,W\in\mathbb{R}^{3\times2},\,H\in\mathbb{R}^{2\times3}}&\langle Z\,,Y\rangle\\ \mbox{subject to}&Z=\left[\begin{array}{ccc}I&W^{\rm T}&H\\W&A&X \\H^{\rm T}&X^{\rm T}&B\end{array}\right]\succeq0\\ &W\geq0\\ &H\geq0\end{array}$

with

$LaTeX: Y\!=U^* U^{*\rm T}.$ Global convergence occurs, in this example, in only a few iterations.