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:
- NMF problem
- From: vaib <vaibhavpanghal@gmail.com>
- NMF problem