dummy-link

NonNegLeastSquares

Some nonnegative least squares solvers in Julia

Readme

Build Status NonNegLeastSquares NonNegLeastSquares License

NonNegLeastSquares.jl

Some nonnegative least squares solvers in Julia

Basic Usage:

The command X = nonneg_lsq(A,B) solves the optimization problem:

Minimize ||A*X - B|| subject to Xᵢⱼ >= 0; in this case, ||.|| denotes the Frobenius norm (equivalently, the Euclidean norm if B is a column vector). The arguments A and B are respectively (m x k) and (m x n) matrices, so X is a (k x n) matrix.

Currently Implemented Algorithms:

The code defaults to the "Pivot Method" algorithm. To specify a different algorithm, use the keyword argument alg. Currently implemented algorithms are:

nonneg_lsq(A,b;alg=:nnls)  # NNLS
nonneg_lsq(A,b;alg=:fnnls) # Fast NNLS
nonneg_lsq(A,b;alg=:pivot) # Pivot Method
nonneg_lsq(A,b;alg=:pivot,variant=:cache) # Pivot Method (cache pseudoinverse up front)
nonneg_lsq(A,b;alg=:pivot,variant=:comb) # Pivot Method with combinatorial least-squares

Default algorithm:

nonneg_lsq(A,b) # pivot method

The keyword Gram specifies whether the the inputs are Gram matrices (as shown in the examples below). This defaults to false.

nonneg_lsq(A'*A,A'*b;alg=:nnls,gram=true) # NNLS
nonneg_lsq(A'*A,A'*b;alg=:fnnls,gram=true) # Fast NNLS

References

Installation:

Pkg.add("NonNegLeastSquares")
Pkg.test("NonNegLeastSquares")

Simple Example:

using NonNegLeastSquares

A = [ -0.24  -0.82   1.35   0.36   0.35
      -0.53  -0.20  -0.76   0.98  -0.54
       0.22   1.25  -1.60  -1.37  -1.94
      -0.51  -0.56  -0.08   0.96   0.46
       0.48  -2.25   0.38   0.06  -1.29 ];

b = [-1.6,  0.19,  0.17,  0.31, -1.27];

x = nonneg_lsq(A,b)

Produces:

5-element Array{Float64,1}:
 2.20104
 1.1901 
 0.0    
 1.55001
 0.0

Speed Comparisons:

Run the examples/performance_check.jl script to compare the various algorithms that have been implemented on some synthetic data. Note that the variants :cache and :comb of the pivot method improve performance substantially when the inner dimension, k, is small. For example, when m = 5000 and n = 5000 and k=3:

Comparing pivot:none to pivot:comb with A = randn(5000,3) and B = randn(5000,5000)
-------------------------------------------------------------------------------------
PIVOT:none →   2.337322 seconds (1.09 M allocations: 4.098 GB, 22.74% gc time)
PIVOT:comb →   0.096450 seconds (586.76 k allocations: 23.569 MB, 3.01% gc time)

Algorithims That Need Implementing:

Pull requests are more than welcome, whether it is improving existing algorithms, or implementing new ones.

First Commit

10/06/2015

Last Touched

about 2 months ago

Commits

87 commits

Requires:

Used By: