This matlab code contains four heuristics to compute exact NMF's:
- multi-start strategies,
- simulated annealing (SA),
- the rank-by-rank heuristic (RBR) contructing recursively an exact NMF, and
- a hybridization between SA and RBR.
See A. Vandaele, N. Gillis, F. Glineur and D. Tuyttens, "Heuristics for Exact Nonnegative Matrix Factorization", Journal of Global Optimization 65 (2), pp 369-400, 2016. [doi] [pdf] [arXiv]
We would be glad to refer to your code: please send us the code, to arnaud.vandaele at umons.ac.be, and a corresponding paper/report, and we can make it available here.
Please let us also know of any bug that you might find in our code. Thanks!
Numerical example:
% Let us construct the slack matrix of the square whose nonnegative rank is equal to 4:
>> addpath matrices/;
>> A = slackregularngon(4)
A =
0 1.4142 1.4142 0.0000
0.0000 0 1.4142 1.4142
1.4142 0.0000 0 1.4142
1.4142 1.4142 0.0000 0
% You can compute an exact NMF of rank 4:
>> [W,H] = exactNMFheur(A,4);
Factorizing a 4x4 matrix using r=4 with 10 attempts of RBR
Parameters: K=10,N=50 - algo=5,rndtype=sparse10,LI(alpha=0.99,delta_t=1)
Attempt 1/10 --> EXACT factorization with relative error = 9.91e-14%
% You cannot compute an exact NMF of rank 3:
>> [W,H] = exactNMFheur(A,3);
Factorizing a 4x4 matrix using r=3 with 10 attempts of RBR
Parameters: K=10,N=50 - algo=5,rndtype=sparse10,LI(alpha=0.99,delta_t=1)
Attempt 1/10 --> relative error = 27.1%
Attempt 2/10 --> relative error = 27.1%
Attempt 3/10 --> relative error = 27.1%
Attempt 4/10 --> relative error = 27.1%
Attempt 5/10 --> relative error = 27.1%
Attempt 6/10 --> relative error = 27.1%
Attempt 7/10 --> relative error = 27.1%
Attempt 8/10 --> relative error = 27.1%
Attempt 9/10 --> relative error = 27.1%
Attempt 10/10 --> relative error = 27.1%