Nonnegative Matrix Factorization by Alternating Nonnegativity Constrained Least Squares using Block Principal Pivoting/Active Set method.
This function solves one the following problems: given A and k, find W and H such that
(1) minimize 1/2 * ||A-WH ||_F^2
(2) minimize 1/2 * ( ||A-WH ||_F^2 + alpha * ||W ||_F^2 + beta * ||H ||_F^2 )
(3) minimize 1/2 * ( ||A-WH ||_F^2 + alpha * ||W ||_F^2 + beta * (sum_(i=1)^n ||H(:,i) ||_1^2 ) )
where W>=0 and H>=0 elementwise. The input arguments are A : Input data matrix (m x n) and k : Target low-rank.
Optional Inputs
Default is ’regularized’, which is recommended for quick application testing unless ’sparse’ or ’plain’ is explicitly needed. If sparsity is needed for ’W’ factor, then apply this function for the transpose of ’A’ with formulation (3). Then, exchange ’W’ and ’H’ and obtain the transpose of them. Imposing sparsity for both factors is not recommended and thus not included in this software.
to use formulation (1)
to use formulation (2)
to use formulation (3)
Default is ’bp’, which is in general faster.
item ’bp’ to use the algorithm in [1] item ’as’ to use the algorithm in [2]
Parameter alpha in the formulation (2) or (3). Default is the average of all elements in A. No good justfication for this default value, and you might want to try other values.
Parameter beta in the formulation (2) or (3). Default is the average of all elements in A. No good justfication for this default value, and you might want to try other values.
Maximum number of iterations. Default is 100.
Minimum number of iterations. Default is 20.
Maximum amount of time in seconds. Default is 100,000.
(m x k) initial value for W.
(k x n) initial value for H.
Stopping tolerance. Default is 1e-3. If you want to obtain a more accurate solution, decrease TOL and increase MAX_ITER at the same time.
If present the function will show information during the calculations.
Outputs
Obtained basis matrix (m x k)
Obtained coefficients matrix (k x n)
Number of iterations
If present the history of computation is returned.
Usage Examples:
nmf_bpas (A,10) nmf_bpas (A,20,'verbose') nmf_bpas (A,30,'verbose','nnlssolver','as') nmf_bpas (A,5,'verbose','type','sparse') nmf_bpas (A,60,'verbose','type','plain','Winit',rand(size(A,1),60)) nmf_bpas (A,70,'verbose','type','sparse','nnlssolver','bp','alpha',1.1,'beta',1.3)
References:
[1] For using this software, please cite:
Jingu Kim and Haesun Park, Toward Faster Nonnegative Matrix Factorization: A New Algorithm and Comparisons,
In Proceedings of the 2008 Eighth IEEE International Conference on Data Mining (ICDM’08), 353-362, 2008
[2] If you use ’nnls_solver’=’as’ (see below), please cite:
Hyunsoo Kim and Haesun Park, Nonnegative Matrix Factorization Based
on Alternating Nonnegativity Constrained Least Squares and Active Set Method,
SIAM Journal on Matrix Analysis and Applications, 2008, 30, 713-730
Check original code at http://www.cc.gatech.edu/~jingu
See also: nmf_pg.
The following code
m = 300;
n = 200;
k = 10;
W_org = rand(m,k);, W_org(rand(m,k)>0.5)=0;
H_org = rand(k,n);, H_org(rand(k,n)>0.5)=0;
% normalize W, since 'nmf' normalizes W before return
norm2=sqrt(sum(W_org.^2,1));
toNormalize = norm2 > eps;
W_org(:,toNormalize) = W_org(:,toNormalize) ./ norm2(toNormalize);
A = W_org * H_org;
[W,H,iter,HIS]=nmf_bpas (A,k,'type','plain','tol',1e-4);
% -------------------- column reordering before computing difference
reorder = zeros(k,1);
selected = zeros(k,1);
for i=1:k
for j=1:k
if ~selected(j), break, end
end
minIx = j;
for j=minIx+1:k
if ~selected(j)
d1 = norm(W(:,i)-W_org(:,minIx));
d2 = norm(W(:,i)-W_org(:,j));
if (d2
Produces the following output
Stop: tolerance reached.
recovery_error_W = 0.0062901
recovery_error_H = 0.0073926
Package: linear-algebra