Non-negative least squares

Template:Short description Template:Regression bar In mathematical optimization, the problem of non-negative least squares (NNLS) is a type of constrained least squares problem where the coefficients are not allowed to become negative. That is, given a matrix Template:Math and a (column) vector of response variables Template:Math, the goal is to find

$\underset{𝐱}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\Vert 𝐀𝐱-𝐲{\Vert }_2^2$ subject to Template:Math.

Here Template:Math means that each component of the vector Template:Math should be non-negative, and Template:Math denotes the Euclidean norm.

Non-negative least squares problems turn up as subproblems in matrix decomposition, e.g. in algorithms for PARAFAC and non-negative matrix/tensor factorization. The latter can be considered a generalization of NNLS.

Another generalization of NNLS is bounded-variable least squares (BVLS), with simultaneous upper and lower bounds Template:Math.Template:RTemplate:Rp

Quadratic programming version

The NNLS problem is equivalent to a quadratic programming problem

$\underset{𝐱\mathbf{\ge }\mathrm{𝟎}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}(\frac{1}{2}{𝐱}^{𝖳}𝐐𝐱+{𝐜}^{𝖳}𝐱),$

where Template:Math = Template:Math and Template:Math = Template:Math. This problem is convex, as Template:Math is positive semidefinite and the non-negativity constraints form a convex feasible set.

Algorithms

The first widely used algorithm for solving this problem is an active-set method published by Lawson and Hanson in their 1974 book Solving Least Squares Problems.Template:Rp In pseudocode, this algorithm looks as follows:Template:R

• Inputs:
  • a real-valued matrix Template:Mvar of dimension Template:Math,
  • a real-valued vector Template:Math of dimension Template:Mvar,
  • a real value Template:Mvar, the tolerance for the stopping criterion.
• Initialize:
  • Set Template:Math.
  • Set Template:Math}.
  • Set Template:Math to an all-zero vector of dimension Template:Mvar.
  • Set Template:Math.
  • Let Template:Math denote the sub-vector with indexes from R
• Main loop: while Template:Math and Template:Math:
  • Let Template:Mvar in Template:Math be the index of Template:Math in Template:Math.
  • Add Template:Mvar to Template:Mvar.
  • Remove Template:Mvar from Template:Mvar.
  • Let Template:Mvar be Template:Mvar restricted to the variables included in Template:Mvar.
  • Let Template:Math be vector of same length as Template:Math. Let Template:Math denote the sub-vector with indexes from P, and let Template:Math denote the sub-vector with indexes from R.
  • Set Template:Math
  • Set Template:Math to zero
  • While Template:Math:
    • Let Template:Math.
    • Set Template:Math to Template:Math.
    • Move to Template:Mvar all indices Template:Mvar in Template:Mvar such that Template:Math.
    • Set Template:Math
    • Set Template:Math to zero.
  • Set Template:Math to Template:Mvar.
  • Set Template:Math to Template:Math.
• Output: x

This algorithm takes a finite number of steps to reach a solution and smoothly improves its candidate solution as it goes (so it can find good approximate solutions when cut off at a reasonable number of iterations), but is very slow in practice, owing largely to the computation of the pseudoinverse Template:Math.Template:R Variants of this algorithm are available in MATLAB as the routine Template:Mono and in SciPy as Template:Mono.

Many improved algorithms have been suggested since 1974.Template:R Fast NNLS (FNNLS) is an optimized version of the Lawson–Hanson algorithm.Template:R Other algorithms include variants of Landweber's gradient descent method, coordinate-wise optimization based on the quadratic programming problem aboveTemplate:R, and an active set method called TNT-NN.

See also

• M-matrix
• Perron–Frobenius theorem