optimize matrix equation (low rank)

Question

I am trying to solve the following optimization problem

$min_{H,V}$ $||A-HV||_F^2$ s.t $V\geq 0$ (i.e all entries are non-negative) and H is low rank

Is there a way to tackle the is problem

Can i alternate between solving H and V ( fix H solve for V and vice-versa)

Answer 1

What you have is a variant of non-negative matrix factorization, which is a pretty active research field. It is generally an intractable problem, so one typically resort to various iterative schemes as you ask about.

Non-negativity is easy if one is allowed to use optimzation (which could be way too expensive though), while low-rank is more problematic. It could be that the low-rank iteration could be dealt with easily using thresholding and SVDs (typical tool in this field, not to unlikely in this case). Another currently fashionable approach is to replace the rank with a penalty on the nuclear norm of the matrix, a proxy which works well in practice on some problems.

Proof-of-concept code using no tricks with SVDs or so, just iteratively solving the non-negativity problem in $V$, and a nuclear norm penalized problem for $H$. Implemented in the MATLAB Toolbox YALMIP (disclaimer, developed by me). You need an SDP solver also, such as mosek or sdpt3 etc.

X = randn(10);

V = sdpvar(10,10,'full');
H = sdpvar(10,10,'full');

% Initial guess on H
assign(H,randn(10));

ops = sdpsettings('verbose',0);
for i = 1:10
    optimize([V >= 0], norm(X - value(H)*V),ops);
    optimize([], norm(X - H*value(V)) + 1*norm(H,'nuclear'),ops);
    norm(X - H*V)
end
svd(value(H))

Note, I am not from the NNF field, so it could be that this particular problem actually is easy or massively investigated.