Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm following an algorithm in the book "Solving Least Squares Problems" by Lawson and Hanson (#15 in Siam's Classics in Applied Mathematics) for solving non negative least squares.

That is, minimize $||Ex - f||$ subject to $x \ge 0$

It's basically using a pivoting scheme to try and find which variables can be set free and which have to be clamped to $0$. It forms a temporary matrix $E_p$, where for free variables, it takes the corresponding column in $E$, and for clamped variables, it takes a column of 0s, and computes the least squares solution for $E_p x \cong f$.

Only this isn't really the least squares solution, in the sense of having minimum residual and norm. It's a basic solution, where the fewest number of variables are set to be free as possible. In cases where the matrix is rank degenerate it won't "spread out" the answer as a proper least squares solution would.

For instance:

$$E = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \\ 1 & 2 & 3 \\ \end{array} \right), f = \left( \begin{array}{ccc} 1 \\ 1 \\ 1 \end{array} \right)$$

Produces the vector $x = \left( \begin{array}{ccc} 0 & 0 & \frac{1}{3} \end{array} \right)$ when I use my algorithm, but its unconstrained least squares solution is $x = \left( \begin{array}{ccc} \frac{1}{14} & \frac{2}{14} & \frac{3}{14} \end{array} \right)$. For comparison, Octave's lsqnonneg also returns $x = \left( \begin{array}{ccc} 0 & 0 & \frac{1}{3} \end{array} \right)$.

Both vectors, when multiplied by $E$, produce $f$ again, so they're both correct in the sense that they have minimum residual. But for my purposes the smaller norm of the second would be better.

Is there a way to "relax" this basic solution to get back a minimum norm solution? Note that the matrix isn't necessarily square. Or a different algorithm to use? I'd like to stick to pivoting algorithms over iterative gradient descent, but otherwise I'm pretty flexible.

share|improve this question
add comment

1 Answer 1

You can try some post-processing after calculating of $x$: compute the null space of $E$, then solve $$ \min \|x + v \| $$ subject to $Ev=0$ and $x+v\ge 0$.

share|improve this answer
    
Ah, interesting, I'll have to explore that. –  Jay Lemmon Jul 1 at 19:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.