---
tag: 1JV7093B4C
kind: problem
name: Non-negative least squares
msc: [65F20, 90C20, 65K05]
uses: [0BYTQ4X1HC, 07Q7CNM5WF]
about: [0BYTQ4X1HC]
sources:
  - url: https://en.wikipedia.org/wiki/Non-negative_least_squares
same_as:
  wikidata: Q17086437
  wikipedia: Non-negative least squares
history:
  posed_by: "Charles L. Lawson and Richard J. Hanson"
  first_stated: "1974"
  notes: "Lawson and Hanson gave the standard active-set algorithm in Solving Least Squares Problems (1974)."
---

## Problem

Let $A \in \R^{m \times n}$ and $b \in \R^m$.
The *non-negative least squares problem* (NNLS) is to find
$$x^* \in \arg\min \set{ \norm{Ax - b}_2^2 : x \in \R^n, \ x \ge 0 },$$
where $x \ge 0$ means $x_i \ge 0$ for every $i$.

## Remarks

The problem always has a solution.
The image of the non-negative orthant under $A$ is a closed convex cone, and $Ax^*$ is the nearest point of that cone to $b$.
The objective is a [[convex function|07Q7CNM5WF]], so NNLS is a convex quadratic programming problem, and the solution is unique when $A$ has full column rank.
By the Karush–Kuhn–Tucker conditions, $x$ is a solution if and only if, with $w = A^T(b - Ax)$, one has $x \ge 0$, $w \le 0$ and $x_i w_i = 0$ for every $i$.
Example: for $A = I$ the solution is $x^*_i = \max(b_i, 0)$, which satisfies these conditions.
The classical algorithm is the active-set method of Lawson and Hanson, published in their 1974 book *Solving Least Squares Problems*.
It moves variables between a free set and a set fixed at zero.
At each step it solves an unconstrained least squares problem on the free set, and it stops after finitely many steps.
Projected gradient and coordinate descent methods are used for large problems.

## Explanations

### L1 human

Ordinary least squares finds the best fit of $Ax$ to $b$ with no restriction on $x$.
In many applications, such as concentrations, intensities or counts, the unknowns cannot be negative, and the unrestricted fit may give negative values.
NNLS asks for the best fit among non-negative $x$ only.
The answer is the closest point to $b$ in the cone of all non-negative combinations of the columns of $A$.