# Fast Combinatorial Nonnegative Least-Square

## Description

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

## Usage

```fcnnls(x, y, ...)

S4 (matrix,matrix)
`fcnnls`(x, y, verbose = FALSE, pseudo = TRUE, ...)```

## Arguments

...
extra arguments passed to the internal function `.fcnnls`. Currently not used.
verbose
toggle verbosity (default is `FALSE`).
x
the coefficient matrix
y
the target matrix to be approximated by ```X K```.
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.

## Value

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

## Details

```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 et
al. (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 et al. (2007).

```

## Methods

1. fcnnls```signature(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`.

2. fcnnls```signature(x = "numeric", y = "matrix")```: Shortcut for ```fcnnls(as.matrix(x), y, ...)```.

3. fcnnls`signature(x = "ANY", y = "numeric")`: Shortcut for `fcnnls(x, as.matrix(y), ...)`.

## References

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

Van Benthem M and Keenan MR (2004). "Fast algorithm for the solution of large-scale non-negativity-constrained least squares problems." _Journal of Chemometrics_, *18*(10), pp. 441-450. ISSN 0886-9383, , .

Kim H and Park H (2007). "Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis." _Bioinformatics (Oxford, England)_, *23*(12), pp. 1495-502. ISSN 1460-2059, , .

## Examples

``````
## 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)

``````

`nmf`