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>