DECIPHER (version 2.0.2)

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

Description

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.

Usage

NNLS(A, b, precision = sqrt(.Machine$double.eps), processors = 1, verbose = TRUE)

Arguments

A

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

b

Numeric matrix for the set of observed values. (See details section below.)

precision

The desired accuracy.

processors

The number of processors to use, or NULL to automatically detect and use all available processors.

verbose

Logical indicating whether to display progress.

Value

A list of two components:

x

The matrix of non-negative values that best explains the observed values given by $b$.

res

A matrix of residuals given by $\bold{A} x - b$.

Details

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.

References

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

Examples

# 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