Nonnegative matrix factorization

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(New page: Given rank-2 nonnegative matrix <math>X=\!\left[\!\begin{array}{ccc}17&28&42\\ 16&47&51\\ 17&82&72\end{array}...)
Line 1: Line 1:
 +
Example 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\\
Line 19: Line 21:
\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 convex iteration;
+
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^\star\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^\mathbf{8}</math> to an ordered diagonalization and
set <math>_{}Z^\star\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^\mathbf{8}</math> to an ordered diagonalization and
<math>_{}U^\star\!=_{\!}Q(:\,,_{^{}}3\!:\!8)\!\in_{\!}\reals^{\mathbf{8}\times\mathbf{6}}</math>,
<math>_{}U^\star\!=_{\!}Q(:\,,_{^{}}3\!:\!8)\!\in_{\!}\reals^{\mathbf{8}\times\mathbf{6}}</math>,
then <math>Y\!=U^\star U^{\star\rm T}.</math>
then <math>Y\!=U^\star U^{\star\rm T}.</math>
 +
 +
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^\star U^{\star\rm T}.</math>

Revision as of 14:27, 28 September 2009

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

Given rank-2 nonnegative matrix LaTeX: X=\!\left[\!\begin{array}{ccc}17&28&42\\
</p>
<pre>                                      16&47&51\\
                                      17&82&72\end{array}\!\right],

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

LaTeX: \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\\
\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\\
&\mbox{rank}\,Z\leq2\end{array}

which follows from the fact, at optimality,

LaTeX:  Z^\star=\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^\star\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^\mathbf{8} to an ordered diagonalization and LaTeX: _{}U^\star\!=_{\!}Q(:\,,_{^{}}3\!:\!8)\!\in_{\!}\reals^{\mathbf{8}\times\mathbf{6}}, then LaTeX: Y\!=U^\star U^{\star\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^\star U^{\star\rm T}.

Personal tools