Ex. 14.24

Consider the non-negative matrix factorization (14.72) in the rank one case (\(r=1\)).

(a) Show that the updates (14.74) reduce to

\[\begin{eqnarray} w_i &\leftarrow& w_i\frac{\sum_{j=1}^px_{ij}}{\sum_{j=1}^pw_ih_j}\non\\ h_j &\leftarrow& h_j\frac{\sum_{i=1}^Nx_{ij}}{\sum_{i=1}^Nw_ih_j}\non \end{eqnarray}\]

where \(w_i = w_{i1}, h_j = h_{1j}\). This is an example of the iterative proportional scaling procedure, applied to the independence model for a two-way contingency table (Fienberg, 1977, for example.)

(b) Show that the final iterates have the explicit form

\[\begin{equation} w_i = c\cdot \frac{\sum_{j=1}^px_{ij}}{\sum_{i=1}^N\sum_{j=1}^px_{ij}}, \ \ h_k = \frac{1}{c}\cdot \frac{\sum_{i=1}^Nx_{ik}}{\sum_{i=1}^N\sum_{j=1}^px_{ij}}\non \end{equation}\]

for any constant \(c > 0\). These are equivalent to the usual row and column estimates for a two-way independence model.

Soln. 14.24

(a) When \(r = 1\), \((\bW\bb{H})_{ij} = w_ih_j\), therefore (14.74) becomes

\[\begin{eqnarray} w_i &\leftarrow& w_i\frac{\sum_{j=1}^ph_jx_{ij}/w_ih_j}{\sum_{j=1}^ph_j}\non\\ &=&w_i\frac{\sum_{j=1}^px_{ij}}{\sum_{j=1}^pw_ih_j}.\non \end{eqnarray}\]

Similar arguments apply to \(h_j\) with

\[\begin{equation} hj \leftarrow h_j\frac{\sum_{i=1}^Nx_{ij}}{\sum_{i=1}^Nw_ih_j}.\non \end{equation}\]

(b) From (a) we know that, in the final iterates, plug the update formula for \(h_j\) into \(w_i\) we get

\[\begin{eqnarray} w_i &\leftarrow& \frac{\sum_{j=1}^p x_{ij}}{\sum_{j=1}^p h_j}\non\\ &=&\frac{\sum_{j=1}^p x_{ij}}{\sum_{j=1}^p\frac{\sum_{i=1}^Nx_{ij}}{\sum_{i=1}^Nw_i}}\non\\ &=&\sum_{i=1}^Nw_i \cdot \frac{\sum_{j=1}^p x_{ij}}{\sum_{j=1}^p\sum_{i=1}^Nx_{ij}}\non\\ &=&c \cdot \frac{\sum_{j=1}^p x_{ij}}{\sum_{j=1}^p\sum_{i=1}^Nx_{ij}},\non \end{eqnarray}\]

where \(c>0\) could be any constant. Similar arguments apply to \(h_k\).