In non-negative matrix tri-factorization, initialization not possible because matrix is singular

I have implemented the non-negative matrix tri-factorization algorithm (link to paper). If is similar to the more widely known NMF (non-negative matrix factorization), but incorporates prior knowledge to represent semi-supervised learning. The basic tenet is that a term-document matrix X can be factorized as $$X = FSG^T$$

where

• $X$ is an $m\times n$ term-document matrix representing $n$ documents and $m$ terms
• $F$ is an $m\times k$ matrix. i'th row represents probability of $t_i$ belonging to $k$ classes
• $G$ is an $n\times k$ matrix. i'th row represents probability of $d_i$ belonging to $k$ classes
• $S$ is a $k\times k$ matrix, provides a low-dimensional condensed view of $X$.

The matrix S is initialized as $S = (F^TF)^{-1}F^TXG(G^TG)^{-1}$.

I ran my code, which strictly follows the above paper, and it ran fine on one dataset. On another dataset, however, the matrix F leads to a situation where $F^TF$ is not invertible. As a result, I can't initialize the matrix S.

I have literally spent days trying to find some information about how to proceed in this scenario, but none of the related papers mention anything. If anyone knows how to handle this situation, please help me out. Thanks!

• Would it be possible to have a look on the code? (Only for my own interest) – user109000 Mar 18 '16 at 9:14

1 Answer

Presumably you mean $F F^T$, since $F F$ is undefined.

Anyway, the typical thing to do in situations like this is to just add $\lambda I$ to the matrix to force it to be invertible, where $\lambda$ is maybe $10^{-6}$ or so. Since this is just the initialization anyway, that shouldn't cause any serious issues.

• I was using F* to indicate the transpose of F. And what you suggested is exactly what I ended up doing. I should reduce the value of lambda, though. Currently it's 0.1. Thank you for the quick reply! This had been driving me nuts. – Chthonic Project Jan 21 '14 at 5:09
• Oh, I thought you meant * to mean multiplication – that makes more sense. :) For future reference, you can use latex notation on this site just by wrapping it in \$or \$\$. – Dougal Jan 21 '14 at 5:12 • On a different note, how do people get the mathematical notation on stackexchange? I would like to format my question using the notations you have in your answer, for instance. – Chthonic Project Jan 21 '14 at 5:13 • That's written using LaTeX, a common way of writing mathematics in documents. When editing, click on the gold-diamond with the question mark at the top right and you can go through to some (very) brief help on formatting, including a tiny bit on LaTeX. One easy way to see how to do something is to find a post that does it, right click, Show Math As -> TeX Commands, select, copy, paste between \$ signs, edit. There are many documents online (web pages and pdfs) with lots of details on mathematics in LaTeX, much of which works here. Here's one – Glen_b Jan 21 '14 at 5:25