18

5

10

6

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.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.

10/06/2015

22 days ago

96 commits