Fast Nonnegative Least Squares
Project description
fnnls
An implementation of the Fast Nonnegative Least Squares (fnnls) algorithm presented in the paper "A fast non‐negativity‐constrained least squares algorithm" by Bro and De Jung:
Bro, Rasmus, and Sijmen De Jong. "A fast non‐negativity‐constrained least squares algorithm." Journal of Chemometrics: A Journal of the Chemometrics Society 11, no. 5 (1997): 393401.
Given a matrix Z and vector x, this algorithm aims to find the optimal d to minimize  x  Zd  subject to d >= 0.
The fnnls algorithm is most comparable to the Lawson and Hanson algorithm for nonegative least squares published in 1974, which is the standard algorithm used by the SciPy library. In practice, the algorithm converges to the nonnegative least square solution faster than the SciPy implementation of the Lawson and Hanson algorithm for tall and large matrices.
Installation
To install fnnls, run this command in your terminal:
$ pip install fnnls
This is the preferred method to install fnnls, as it will always install the most recent stable release.
If you don't have pip installed, these installation instructions can guide you through the process.
Usage
Quick Start
It's easy to directly solve a nonnegative least squares task with fnnls
:
>>> import numpy as np
>>> from fnnls import fnnls
>>> np.random.seed(1)
>>> Z = np.abs(np.random.rand(5,10))
>>> x = np.abs(np.random.rand(5))
>>> fnnls(Z,x)
[array([0. , 0. , 0. , 0.49507457, 0. ,
0. , 0.10518829, 0. , 0. , 0. ]), 0.29527550874513586]
Custom least squared functions:
The fast nonegative least square algorithm solves an unconstrained least squares task for every iteration. By default, we use numpy.linalg.lstsq.
We provide more custom functions to solve the least squares algorithm, and give users the ability to define and use their own functions.
>>> import numpy as np
>>> from fnnls import fnnls
>>> from fnnls import RK #the Randomized Karzmarz method
>>> np.random.seed(1)
>>> RK1 = lambda Z, x: RK(Z,x,random_state=1) #Set random state
>>> Z = np.abs(np.random.rand(5,10))
>>> x = np.abs(np.random.rand(5))
>>> fnnls(Z,x,lstsq=RK1)
[array([0. , 0. , 0. , 0.22992788, 0. ,
0.19111572, 0.15289165, 0.10472243, 0. , 0. ]), 0.3198075779021192]
Note that to set a random state above for RK, we had to define a new function RK1.
Initializing the Passive Set
The fast nonnegative least squares algorithm is a combinatorial algorithm that continually updates a passive set P to indicate the support (nonzero elements) of the solution at the current iteration. Often, it is possible to have knowledge of an estimate for the support of the solution, which can improve the efficiency of the algorithm. We allow users to choose to input an estimate for the support.
>>> import numpy as np
>>> from fnnls import fnnls
>>> from time import time
>>> np.random.seed(1)
>>> Z = np.abs(np.random.rand(100,100))
>>> x = np.abs(np.random.rand(100))
>>> start = time()
>>> d, res = fnnls(Z,x) #run with no initial support
>>> end = time()
>>> endstart #time without initial support
0.0065343379974365234
>>> support = np.nonzero(d)[0] #find the support of the solution
>>> start = time()
>>> d_sup, res = fnnls(Z, x, P_initial = support) #run with initial support
>>> end = time()
>>> endstart #time with initial support
0.0012061595916748047
>>> np.array_equal(d,d_sup) #check the two solutions are equal
True
Authors
 Joshua Vendrow
 Jamie Haddock
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for fnnls1.0.0py2.py3noneany.whl
Algorithm  Hash digest  

SHA256  d826861ef1a4d9fb303fb7c95db9ecc940cdcf3ae4f7ca7067a4d4c799859774 

MD5  1575091f7f6893fdce0bfe9370022506 

BLAKE2b256  45ba74e0f30f22edf462bb2a3a5ccb651a6200ae5bd9394bf195e2033033b43b 