Skip to main content

Fast Nonnegative Least Squares

Project description

fnnls

PyPI Version Supported Python Versions

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): 393-401.

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 -U 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 (non-zero 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()
>>> end-start #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()
>>> end-start #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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

fnnls-0.0.1.tar.gz (9.1 kB view hashes)

Uploaded source

Built Distribution

fnnls-0.0.1-py2.py3-none-any.whl (11.1 kB view hashes)

Uploaded py2 py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page