MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Non-negative Least Squares (NNLS) algorithm

mdw at (Michael Woodhams) wrote in message news:<blj6cf$1j6$1 at>...
> A little while ago, I looked at this group and the web for an
> implementation of the NNLS algorithm, but all I found was a post in
> this group from 1997 from somebody also looking for an implementation,
> so I had to do it myself.
> The problem: Given a matrix A (usually more rows than columns) and
> vector f, find vector x such that:
> 1) All elements of x are non-negative
> 2) subject to contraint (1), the Euclidian norm (2-norm) of vector
> (A.x-f) is minimized.


Congratulations for your NNLS code!
I had a 10-liner naive solution (see below) using FindMinimum. 
It seems to work most of the time, but your solution is more accurate 
and... at least sixty times faster!

NNLSFindMinimum[A_, f_] := 
Module[{nbx = Length[First[A]], xi, x, axf, xinit},
      xi = Array[x,nbx];
      axf = A.xi^2 - f;
      xinit = PseudoInverse[A].f;
      If[And@@( #>=0& /@ xinit),
        	fm = FindMinimum[Evaluate[axf.axf],
                Evaluate[Sequence@@Transpose[{xi, xinit}]]];
        	xi^2 /. fm[[2]]

(* a small test : *)
a = Table[Random[],{i,10},{j,20}];
f = Table[Random[],{i,10}];
x = NNLSFindMinimum[a,f]//Timing
% // Chop[#, 10.^-5] &
{1.001 Second,{0.0580067,0.0246345,0,0.0227949,0,0,0,0.386312,0,0,0,0,0,0,0,0,

x = NNLS[a, f] // Timing
{0.016 Second,{0.058114,0.02338271,0,0.0227961,0,0,0,0.386253,0,0,0,0,0,0,0,0,

  • Prev by Date: Re: negative pattern matching anyone?
  • Next by Date: Re: Plotting functions with undefined values
  • Previous by thread: Non-negative Least Squares (NNLS) algorithm
  • Next by thread: matrix differentiation