1

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?

daureg
  • 11

1 Answers1

1

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 09: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!

     –  Oct 30 '13 at 09: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? –  Oct 30 '13 at 09:33