MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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:
  • Prev by Date: Re: Problem with mathlink:PLEASE HELP ME
  • Next by Date: Re: Superscripts in post-processed plot labels
  • Previous by thread: NMF problem
  • Next by thread: Fitting using a custom function