fcnnls: Fast Combinatorial Nonnegative Least-Square
In renozao/NMF: Algorithms and Framework for Nonnegative Matrix Factorization (NMF)

Description Usage Arguments Details Value Methods (by generic) Author(s) References See Also Examples

This function solves the following nonnegative least square linear problem using normal equations and the fast combinatorial strategy from Van Benthem and Keenan (2004):

fcnnls(x, y, ...)

## S4 method for signature 'matrix,matrix'
fcnnls(x, y, verbose = FALSE, pseudo = TRUE, ..., check = TRUE)

## S4 method for signature 'numeric,matrix'
fcnnls(x, y, ...)

## S4 method for signature 'ANY,numeric'
fcnnls(x, y, ...)

## S3 method for class 'fcnnls'
print(x, ...)

`x`	the coefficient matrix
`y`	the target matrix to be approximated by X K.
`...`	extra arguments passed to the internal function `.fcnnls`. Currently not used.
`verbose`	toggle verbosity (default is `FALSE`).
`pseudo`	By default (`pseudo=FALSE`) the algorithm uses Gaussian elimination to solve the successive internal linear problems, using the `solve` function. If `pseudo=TRUE` the algorithm uses Moore-Penrose generalized `pseudoinverse` from the `corpcor` package instead of solve.
`check`	logical that specifies if the sign of the arguments `x` and `y` should be checked – since these arguments should only contain non-negative values. If `TRUE`, then an error is thrown when negative values are found.

min ||Y - X K||_F, s.t. K>=0

where Y and X are two real matrices of dimension n x p and n x r respectively, and |.|_F is the Frobenius norm.

The algorithm is very fast compared to other approaches, as it is optimised for handling multiple right-hand sides.

Within the NMF package, this algorithm is used internally by the SNMF/R(L) algorithm from Kim and Park (2007) to solve general Nonnegative Matrix Factorization (NMF) problems, using alternating nonnegative constrained least-squares. That is by iteratively and alternatively estimate each matrix factor.

The algorithm is an active/passive set method, which rearrange the right-hand side to reduce the number of pseudo-inverse calculations. It uses the unconstrained solution K_u obtained from the unconstrained least squares problem, i.e. min ||Y - X K||_F^2 , so as to determine the initial passive sets.

The function fcnnls is provided separately so that it can be used to solve other types of nonnegative least squares problem. For faster computation, when multiple nonnegative least square fits are needed, it is recommended to directly use the function .fcnnls.

The code of this function is a port from the original MATLAB code provided by Kim and Park (2007).

A list containing the following components:

`x`	the estimated optimal matrix K.
`fitted`	the fitted matrix X K.
`residuals`	the residual matrix Y - X K.
`deviance`	the residual sum of squares between the fitted matrix X K and the target matrix Y. That is the sum of the square residuals.
`passive`	a r x p logical matrix containing the passive set, that is the set of entries in K that are not null (i.e. strictly positive).
`pseudo`	a logical that is `TRUE` if the computation was performed using the pseudoinverse. See argument `pseudo`.

fcnnls(x = matrix,y = matrix): This method wraps a call to the internal function .fcnnls, and formats the results in a similar way as other lest-squares methods such as lm.
fcnnls(x = numeric,y = matrix): Shortcut for fcnnls(as.matrix(x), y, ...).
fcnnls(x = ANY,y = numeric): Shortcut for fcnnls(x, as.matrix(y), ...).

Original MATLAB code : Van Benthem and Keenan

Adaption of MATLAB code for SNMF/R(L): H. Kim

Adaptation to the NMF package framework: Renaud Gaujoux

Original MATLAB code from Van Benthem and Keenan, slightly modified by H. Kim:
http://www.cc.gatech.edu/~hpark/software/fcnnls.m

Van Benthem MH, Keenan MR (2004). “Fast algorithm for the solution of large-scale non-negativity-constrained least squares problems.” _Journal of Chemometrics_, *18*(10), 441-450. ISSN 0886-9383, doi: 10.1002/cem.889 (URL: https://doi.org/10.1002/cem.889).

Kim H, Park H (2007). “Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis.” _Bioinformatics (Oxford, England)_, *23*(12), 1495-502. ISSN 1460-2059, doi: 10.1093/bioinformatics/btm134 (URL: https://doi.org/10.1093/bioinformatics/btm134).

nmf

## Define a random nonnegative matrix matrix
n <- 200; p <- 20; r <- 3
V <- rmatrix(n, p)

## Compute the optimal matrix K for a given X matrix
X <- rmatrix(n, r)
res <- fcnnls(X, V)

## Compute the same thing using the Moore-Penrose generalized pseudoinverse
res <- fcnnls(X, V, pseudo=TRUE)

## It also works in the case of single vectors
y <- runif(n)
res <- fcnnls(X, y)
# or
res <- fcnnls(X[,1], y)