Re: NMF problem

• To: mathgroup at smc.vnet.net
• Subject: [mg97694] Re: [mg97671] NMF problem
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 19 Mar 2009 02:09:11 -0500 (EST)
• References: <200903180955.EAA06107@smc.vnet.net>

```vaib wrote:
> Hi friends,
> I am making a project where I have to make use of NMF (non-negative
> matrix factorization). But there's a problem I'm facing. Its been
> quite some time since I studied any maths. I am getting to understand
> NMF slowly but it does not seem to be working. I have a few questions:
>
> 1. Kindly tell me some good resources to study NMF and LNMF from. I
> would prefer resources that start from scratch.
>
> 2. Whats the real intuitive/graphical meaning of the multiplicative
> update functions? O! I forget to mention. I only have to study NMF for
> minimizing Euclidean distance and KL Divergence.
>
> I understand well through graphs. I need conceptual information on how
> this stuff works.
>
> Thanking in anticipation.
> Vaibhav

This does not address your questions, but does indicate how one might
approach the decomposition problem in Mathematica (and with relatively
simple code).

A brute-force approach is to set it up as a quadratic optimization
problem. Given a matrix mat, you want to find factors A,X such that A.X
is a close approximation to mat, and all elements of A,X are
nonnegative. Below is an example that uses NMinimize.

In[3]:= mat = RandomReal[{0, 1}, {4, 4}]

Out[3]= {{0.936465, 0.861454, 0.610776, 0.797641}, {0.633923,
0.960643, 0.203871, 0.92107}, {0.254202, 0.248351, 0.438789,
0.263852}, {0.539495, 0.283209, 0.364426, 0.11926}}

amat = Array[a, {4, 4}];
xmat = Array[x, {4, 4}];
vars = Flatten[Join[amat, xmat]];

In[23]:= {min, vals} =
NMinimize[{Total[(amat.xmat - mat)^2, 2], Thread[0<=vars]}, vars]

Out[23]= {2.49829*10^-26, {a[1, 1] -> 0.340709, a[1, 2] -> 1.31141,
a[1, 3] -> 0.476329, a[1, 4] -> 0.63511, a[2, 1] -> 2.11758*10^-22,
a[2, 2] -> 1.2244, a[2, 3] -> 0.145836, a[2, 4] -> 0.893492,
a[3, 1] -> 0.490447, a[3, 2] -> 0.325596, a[3, 3] -> 1.00647*10^-8,
a[3, 4] -> 0.191064, a[4, 1] -> 0.210105, a[4, 2] -> 0.733511,
a[4, 3] -> 0.286423, a[4, 4] -> 6.40909*10^-9, x[1, 1] -> 0.219704,
x[1, 2] -> 0.0387703, x[1, 3] -> 0.812809, x[1, 4] -> 0.143658,
x[2, 1] -> 0.449788, x[2, 2] -> 0.374994, x[2, 3] -> 0.122797,
x[2, 4] -> 0.0426963, x[3, 1] -> 0.570518, x[3, 2] -> 6.24158*10^-7,
x[3, 3] -> 0.361628, x[3, 4] -> 0.201654, x[4, 1] -> 1.19304*10^-7,
x[4, 2] -> 0.56128, x[4, 3] -> 0.000873426, x[4, 4] -> 0.939443}}

We double-check the closeness of approximation by looking at the largest
discrepancy between product and original matrix.

In[26]:= Max[Abs[amat.xmat - mat /. vals]]

Out[26]= 1.37002*10^-13

This is not a viable approach once the dimension gets to even modest
size. Decomposing an 11x11 gave a reasonable result but took about 42
seconds. There are ways to coax a decent result from FindMinimum but
that, too, seems to get quite slow as dimension rises.

Daniel Lichtblau
Wolfram Research

```

• References: