Nonnegative matrix factorization

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Current revision (20:33, 25 June 2026) (edit) (undo)
 
Line 3: Line 3:
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>
+
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}{\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\\
+
<math>\begin{array}{rl}{\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\\
+
{\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\\
Line 17: Line 18:
which follows from the fact, at optimality,
which follows from the fact, at optimality,
-
<math> Z^*=\left[\!\begin{array}{c}I\\ W\\ H^{\rm T}\end{array}\!\right]\begin{array}{c}\textbf{[}\,I\;\;W^{\rm T}\;H\,\textbf{]}
+
<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 [[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^*\!=Q\Lambda Q^{\rm T}\!\in\mathbb{S}^{\mathbf{8}}</math> to a nonincreasingly ordered diagonalization and
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>,
+
<math>_{}U^*\!=_{\!}Q(:\,,\,3:8)\!\in_{\!}\mathbb{R}^{\mathbf{8}\times\mathbf{6}}</math>,
then <math>Y\!=U^* U^{*\rm T}.</math>
then <math>Y\!=U^* U^{*\rm T}.</math>
<br>
<br>
-
In summary, initialize <math>Y=I\,</math> then alternate solution of
+
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\\
+
<math>\begin{array}{rl}\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}</math>
&H\geq0\end{array}</math>
with
with
 +
<math>\,Y\!=U^* U^{*\rm T}.</math>
-
<math>Y\!=U^* U^{*\rm T}.</math>
 
Global convergence occurs, in this example, in only a few iterations.
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\\ </p> <pre> 16&47&51\\ 17&82&72 \end{array}\!\right]\,,

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

LaTeX: \begin{array}{rl}{\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}{rl}\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.

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Nonnegative_matrix_factorization"
Personal tools