nnls: Non-negative least squares

In zdebruine/RcppML: Rcpp Machine Learning Library

Non-negative least squares

Description

Solves the equation a %*% x = b for x subject to x > 0.

Usage

nnls(a, b, cd_maxit = 100L, cd_tol = 1e-08, L1 = 0, L2 = 0, upper_bound = 0)

Arguments

a	symmetric positive definite matrix giving coefficients of the linear system
b	matrix giving the right-hand side(s) of the linear system
cd_maxit	maximum number of coordinate descent iterations
cd_tol	stopping criteria, difference in x across consecutive solutions over the sum of x
L1	L1/LASSO penalty to be subtracted from b
L2	Ridge penalty by which to shrink the diagonal of a
upper_bound	maximum value permitted in solution, set to 0 to impose no upper bound

Details

This is a very fast implementation of sequential coordinate descent non-negative least squares (NNLS), suitable for very small or very large systems. The algorithm begins with a zero-filled initialization of x.

Least squares by sequential coordinate descent is used to ensure the solution returned is exact. This algorithm was introduced by Franc et al. (2005), and our implementation is a vectorized and optimized rendition of that found in the NNLM R package by Xihui Lin (2020).

Value

vector or matrix giving solution for x

Author(s)

Zach DeBruine

References

DeBruine, ZJ, Melcher, K, and Triche, TJ. (2021). "High-performance non-negative matrix factorization for large single-cell data." BioRXiv.

Franc, VC, Hlavac, VC, and Navara, M. (2005). "Sequential Coordinate-Wise Algorithm for the Non-negative Least Squares Problem. Proc. Int'l Conf. Computer Analysis of Images and Patterns."

Lin, X, and Boutros, PC (2020). "Optimization and expansion of non-negative matrix factorization." BMC Bioinformatics.

Myre, JM, Frahm, E, Lilja DJ, and Saar, MO. (2017) "TNT-NN: A Fast Active Set Method for Solving Large Non-Negative Least Squares Problems". Proc. Computer Science.

See Also

nmf, project

Examples

## Not run: 
# compare solution to base::solve for a random system
X <- matrix(runif(100), 10, 10)
a <- crossprod(X)
b <- crossprod(X, runif(10))
unconstrained_soln <- solve(a, b)
nonneg_soln <- nnls(a, b)
unconstrained_err <- mean((a %*% unconstrained_soln - b)^2)
nonnegative_err <- mean((a %*% nonneg_soln - b)^2)
unconstrained_err
nonnegative_err
all.equal(solve(a, b), nnls(a, b))

# example adapted from multiway::fnnls example 1
X <- matrix(1:100,50,2)
y <- matrix(101:150,50,1)
beta <- solve(crossprod(X)) %*% crossprod(X, y)
beta
beta <- nnls(crossprod(X), crossprod(X, y))
beta

# learn nmf model and do bvls projection
data(hawaiibirds)
w <- nmf(hawaiibirds$counts, 10)@w
h <- project(w, hawaiibirds$counts)
# now impose upper bound on solutions
h2 <- project(w, hawaiibirds$counts, upper_bound = 2)

## End(Not run)

zdebruine/RcppML documentation built on Sept. 13, 2023, 11:44 p.m.