Non-negative matrix factorization

Hi,

Im trying to do NMF with multiplicative update. I want to paralellize this piece of code shown below with parfor, but I dont know how to do it.

A is input matrix m x n, and k must be smaller than min of (m,n), H and W are output matrices.

Thank you for help :)

Answer 1

[Steven Lord]

Can you compute w0 and h0 at iteration t = 2 without knowing the values of w0 and h0 computed at iteration t = 1? No, you can't. Because of that cross-iteration dependency you can't convert this into a parfor loop. From the documentation:

"Basically, if one iteration depends on the results of another iteration, these iterations are not independent and cannot be evaluated in parallel, so you cannot easily reprogram the loop into a parfor-loop."

[Adam]

So is there any other way how to parallelize this in Matlab?

[Steven Lord]

Can you parallelize the process of baking a cake? To some extent you can. The oven can preheat while you're mixing the ingredients and you can make the frosting while the cake is baking.

But if you try to bake the ingredients in the oven while you're mixing them, at best you'll end up with a slightly charred bag of flour (or cake mix, depending on your baking skill.) At worst you'll end up in the hospital with burns on your arms and/or your house will burn down. That ordering -- the baking step must come after the mixing step -- is a firm requirement that blocks parallelization.

Similarly, needing h0 from iteration n to compute h0 at iteration n+1 is a key part of your code. Is there a different non-iterative algorithm to compute the NMF that can be parallelized? I'm not sure. But as written I'm not sure your code can be parallelized for computing the NMF of one matrix.

Now if you had multiple cakes you needed to bake (multiple matrices whose NMF you wanted to compute) you could parallelize that process by having multiple people all mixing batter simultaneously then putting each of their cakes into separate ovens at the same time. [Think cooking competition TV shows.] But that's a better fit for spmd than parfor, I think. Using the example on the spmd documentation page, in the context of this cake metaphor each magic matrix is a different cake.