# Formulating non negative least square problem

I was reading the paper “Fitting a graph to vector data [pdf]” and I found this optimization problem: $$\min_{w,s} ||Mw||^2 + \mu||\mathbf{1} - Aw - s||$$ subject to $w,s\geq 0$, where $M$ is a $d\cdot n\times m$ matrix, $A$ a $n \times m$ one and $w$ and $s$ $m$-long vectors. The authors explain that they use MATLAB least square routine to solve it. Thus I asumed it could be rewritten as $\min ||Cx - d||^2$ by combining $w$ and $s$ into $x$ but I didn't manage to do it.

Am I on the right way or completly missing something?

The problem is that you have made a typo copying the unnumbered equation on page 3 of the paper. It should be:

$$\min_{w,s} ||Mw||^2 + \mu||\mathbf{1} - Aw - s||^2$$

This is equivalent to

$$\min_{w,t} ||Mw||^2 + \mu||\mathbf{1} - t||^2$$

where $s = t - Aw$. This is a standard weighted least square optimization problem. If you like, you can even transfer the positive factor $\mu$ into the second norm to simplify it to an unweighted least square problem with the $2m$-long vector $(w,\sqrt{\mu}t)$ as the unknown.

• Thank you for looking at the paper (although I cannot use the typo as an excuse since I only made it when asking the question). But I am still a bit confused by the sum. Does it means that I have to call lsqlin twice or could I use a block matrix like that to solve directly for the $2m$ vector: $$C=\begin{pmatrix} M & 0 \\ 0 & \sqrt{\mu}I \end{pmatrix}$$ – daureg Oct 30 '13 at 9:13
• Calling the routine twice won't work, as the result typically wouldn't be fully optimized. Using the matrix C is almost correct. I think it should be this: $$\min || \sqrt{\mu} D - C (w,\sqrt{\mu}) ||$$ with C as you gave it and D zero in the upper and left quadrants, and the identity in the bottom right: $$\left( \begin{array}{cc} 0 & 0 \\ 0 & \mathbf{1} \\ \end{array} \right)$$ Sorry for needing lots of edits to get this one right! – pyramids Oct 30 '13 at 9:18
• Note that there's a problem with my answer that I only know realized, though: This was still supposed to be a non-negative least-square problem. My substitution is means that this condition can't be passed on as such to a solver routine.Maybe it might be more helpful to seek another answer incorporating the quadprog function that the authors claim to have used for solving the equation? – pyramids Oct 30 '13 at 9:33