# 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,
where `||.||`

denotes the Frobenius norm (equivalently, the Euclidean norm if `B`

is a column vector).
The arguments `A`

and `B`

are respectively (m × k) and (m × n) matrices, so `X`

is a (k × 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 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**

**NNLS**:- Lawson, C.L. and R.J. Hanson, Solving Least-Squares Problems, Prentice-Hall, Chapter 23, p. 161, 1974.

**Fast NNLS**:- Bro R, De Jong S. A fast non-negativitity-constrained least squares algorithm. Journal of Chemometrics. 11, 393–401 (1997)

**Pivot Method**:- Kim J, Park H. Fast nonnegative matrix factorization: an active-set-like method and comparisons. SIAM Journal on Scientific Computing 33.6 (2011): 3261-3281.

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

- Dongmin Kim, Suvrit Sra, and Inderjit S. Dhillon: A New Projected Quasi-Newton Approach for the Nonnegative Least Squares Problem. UT Austin TR-06-54, circa 2007.
- Sra Suvrit Kim Dongmin and Inderjit S. Dhillon. A non-monotonic method for large-scale non-negative least squares. Optimization Methods and Software, 28(5):1012–1039, 2013.