1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – daureg Oct 30 '13 at 9:13
  • $\begingroup$ 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! $\endgroup$ – pyramids Oct 30 '13 at 9:18
  • $\begingroup$ 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? $\endgroup$ – pyramids Oct 30 '13 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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