Sequential Coordinate-wise Algorithm for the Non-negative Least Squares Problem

Consider the linear system $\bold{A} x = b$ where $\bold{A} \in R\textsuperscript{m x n}$, $x \in R\textsuperscript{n}$, and $b \in R\textsuperscript{m}$. The technique of least squares proposes to compute $x$ so that the sum of squared residuals is minimized. NNLS solves the least squares problem $\min{||\bold{A} x = b||\textsuperscript{2}}$ subject to the constraint $x \ge 0$. This implementation of the Sequential Coordinate-wise Algorithm uses a sparse input matrix $\bold{A}$, which makes it efficient for large sparse problems.

NNLS(A, b, precision = sqrt(.Machine$double.eps), processors = 1, verbose = TRUE)
List representing the sparse matrix with integer components i and j, numeric component x. The fourth component, dimnames, is a list of two components that contains the names for every row (component 1) and column (component 2).
Numeric matrix for the set of observed values. (See details section below.)
The desired accuracy.
The number of processors to use, or NULL to automatically detect and use all available processors.
Logical indicating whether to display progress.

The input $b$ can be either a matrix or a vector of numerics. If it is a matrix then it is assumed that each column contains a set of observations, and the output $x$ will have the same number of columns. This allows multiple NNLS problems using the same $\bold{A}$ matrix to be solved simultaneously, and greatly accelerates computation relative to solving each sequentially.


A list of two components:
The matrix of non-negative values that best explains the observed values given by $b$.
A matrix of residuals given by $\bold{A} x - b$.


Franc, V., et al. (2005). Sequential coordinate-wise algorithm for the non-negative least squares problem. Computer Analysis of Images and Patterns, 407-414.

See Also

Array2Matrix, DesignArray

  • NNLS
# unconstrained least squares:
A <- matrix(c(1, -3, 2, -3, 10, -5, 2, -5, 6), ncol=3)
b <- matrix(c(27, -78, 64), ncol=1)
x <- solve(crossprod(A), crossprod(A, b))

# Non-negative least squares:
w <- which(A > 0, arr.ind=TRUE)
A <- list(i=w[,"row"], j=w[,"col"], x=A[w],
          dimnames=list(1:dim(A)[1], 1:dim(A)[2]))
x_nonneg <- NNLS(A, b)

# compare the unconstrained and constrained solutions:
cbind(x, x_nonneg$x)

# the input value "b" can also be a matrix:
b2 <- matrix(b, nrow=length(b), ncol=2) # repeat b in two columns
x_nonneg <- NNLS(A, b2) # solution is repeated in two output columns
Documentation reproduced from package DECIPHER, version 2.0.2, License: GPL-3

Community examples

Looks like there are no examples yet.