# Nonnegative matrix factorization

### From Wikimization

(Difference between revisions)

(New page: Given rank-2 nonnegative matrix <math>X=\!\left[\!\begin{array}{ccc}17&28&42\\ 16&47&51\\ 17&82&72\end{array}...) |
Current revision (16:40, 30 October 2016) (edit) (undo) |
||

(10 intermediate revisions not shown.) | |||

Line 1: | Line 1: | ||

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

<math>X=\!\left[\!\begin{array}{ccc}17&28&42\\ | <math>X=\!\left[\!\begin{array}{ccc}17&28&42\\ | ||

16&47&51\\ | 16&47&51\\ | ||

- | + | 17&82&72\end{array}\!\right],</math> | |

- | + | ||

find a nonnegative factorization | find a nonnegative factorization | ||

<math> X=WH\,</math> | <math> X=WH\,</math> | ||

by solving | by solving | ||

- | <math>\begin{array}{cl} | + | <math>\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\\ | &W\geq0\\ | ||

&H\geq0\\ | &H\geq0\\ | ||

- | & | + | &{\text rank}\,Z\leq2\end{array}</math> |

which follows from the fact, at optimality, | which follows from the fact, at optimality, | ||

- | <math> Z^ | + | <math> 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}</math> | \end{array}</math> | ||

- | Use the known closed-form solution for a direction vector <math>Y\,</math> to regulate rank (rank constraint is replaced) by | + | Use the known closed-form solution for a direction vector <math>Y\,</math> to regulate rank (rank constraint is replaced) by [[Convex Iteration]]; |

+ | |||

+ | set <math>_{}Z^*\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^{\mathbf{8}}</math> to a nonincreasingly ordered diagonalization and | ||

+ | <math>_{}U^*\!=_{\!}Q(:\,,_{^{}}3:8)\!\in_{\!}\mathbb{R}^{\mathbf{8}\times\mathbf{6}}</math>, | ||

+ | then <math>Y\!=U^* U^{*\rm T}.</math> | ||

+ | |||

+ | <br> | ||

+ | In summary, initialize <math>Y=I\,</math> then alternate solution of | ||

+ | |||

+ | <math>\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}</math> | ||

+ | |||

+ | with | ||

- | + | <math>Y\!=U^* U^{*\rm T}.</math> | |

- | + | 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 find a nonnegative factorization by solving

which follows from the fact, at optimality,

Use the known closed-form solution for a direction vector to regulate rank (rank constraint is replaced) by Convex Iteration;

set to a nonincreasingly ordered diagonalization and , then

In summary, initialize then alternate solution of

with

Global convergence occurs, in this example, in only a few iterations.