Part of a series on |
Regression analysis |
---|
Models |
Estimation |
Background |
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 A and a (column) vector of response variables y, the goal is to find [1]
Here x ≥ 0 means that each component of the vector x should be non-negative, and ‖·‖2 denotes the Euclidean norm.
Non-negative least squares problems turn up as subproblems in matrix decomposition, e.g. in algorithms for PARAFAC [2] and non-negative matrix/tensor factorization. [3] [4] The latter can be considered a generalization of NNLS. [1]
Another generalization of NNLS is bounded-variable least squares (BVLS), with simultaneous upper and lower bounds αi ≤ xi ≤ βi. [5]: 291 [6]
The NNLS problem is equivalent to a quadratic programming problem
where Q = ATA and c = −AT y. This problem is convex, as Q is positive semidefinite and the non-negativity constraints form a convex feasible set. [7]
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. [5]: 291 In pseudocode, this algorithm looks as follows: [1] [2]
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 ((AP)T AP)−1. [1] Variants of this algorithm are available in MATLAB as the routine lsqnonneg [8] [1] and in SciPy as optimize.nnls. [9]
Many improved algorithms have been suggested since 1974. [1] Fast NNLS (FNNLS) is an optimized version of the Lawson—Hanson algorithm. [2] Other algorithms include variants of Landweber's gradient descent method [10] and coordinate-wise optimization based on the quadratic programming problem above. [7]
Part of a series on |
Regression analysis |
---|
Models |
Estimation |
Background |
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 A and a (column) vector of response variables y, the goal is to find [1]
Here x ≥ 0 means that each component of the vector x should be non-negative, and ‖·‖2 denotes the Euclidean norm.
Non-negative least squares problems turn up as subproblems in matrix decomposition, e.g. in algorithms for PARAFAC [2] and non-negative matrix/tensor factorization. [3] [4] The latter can be considered a generalization of NNLS. [1]
Another generalization of NNLS is bounded-variable least squares (BVLS), with simultaneous upper and lower bounds αi ≤ xi ≤ βi. [5]: 291 [6]
The NNLS problem is equivalent to a quadratic programming problem
where Q = ATA and c = −AT y. This problem is convex, as Q is positive semidefinite and the non-negativity constraints form a convex feasible set. [7]
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. [5]: 291 In pseudocode, this algorithm looks as follows: [1] [2]
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 ((AP)T AP)−1. [1] Variants of this algorithm are available in MATLAB as the routine lsqnonneg [8] [1] and in SciPy as optimize.nnls. [9]
Many improved algorithms have been suggested since 1974. [1] Fast NNLS (FNNLS) is an optimized version of the Lawson—Hanson algorithm. [2] Other algorithms include variants of Landweber's gradient descent method [10] and coordinate-wise optimization based on the quadratic programming problem above. [7]