       Re: Non-negative Least Squares (NNLS) algorithm

• To: mathgroup at smc.vnet.net
• Subject: [mg43782] Re: Non-negative Least Squares (NNLS) algorithm
• Date: Sat, 4 Oct 2003 02:05:00 -0400 (EDT)
• References: <blj6cf\$1j6\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```mdw at ccu1.auckland.ac.nz (Michael Woodhams) wrote in message news:<blj6cf\$1j6\$1 at smc.vnet.net>...
> 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.
[...]

Michael,

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),
xinit,
fm = FindMinimum[Evaluate[axf.axf],
Evaluate[Sequence@@Transpose[{xi, xinit}]]];
xi^2 /. fm[]
]
];

(* 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,
0,0,0.245039,0.215131}}

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,
0,0,0.246019,0.215755}}
---
jcp

```

• 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