8
$\begingroup$

I have the optimization problem

$$\arg\min_{a,b} \sum_{i,j} \left( \left| X(i,j)-aY(i,j)\right|-b \right)^2$$

Where $X$ and $Y$ are known. But there is a modulus inside.

I need to estimate $a$ and $b$. How can I solve it? Can I use least-squares?

$\endgroup$
3
  • $\begingroup$ Not sure how to linearize the absolute value term in the least squares problem. From a pure optimization perspective, I suppose you could rewrite the equality as a set of two inequalities and then linearize the absolute value using two inequalities but this seems super inefficient and stupid :/. Very interesting question, will think about it some more when I get some time. $\endgroup$
    – wonko
    Aug 13, 2014 at 16:15
  • $\begingroup$ Since your objective is non-smooth convex an the dimension of your problem is 2 which is very low, wouldn't it be a good idea to use the Ellipsoid Method ? $\endgroup$ Jun 17, 2015 at 9:10
  • $\begingroup$ This IS a least squares problem, as you minimize a sum of squared residues. So "Can I use least-squares" is a little irrelevant. $\endgroup$
    – user65203
    Jun 1, 2016 at 14:27

2 Answers 2

1
$\begingroup$

Hint:

You can sort the ratios $\dfrac{X(i,j)}{Y(i,j)}$ increasingly. This will define a number of intervals (say $nm+1$) for the unknown $a$ where the problem is linearized, as the signs of all $X(i,j)-a Y(i,j)$ remain constant and you can trade the absolute values for a $+$ or a $-$.

Solve all these $nm+1$ linear problems independently and check after the fact that the optimal $a$ falls in the hypothesized interval. If you find several solutions, keep the one with the least squares.

If I am right, this can be done efficiently by keeping the sums required for linear least squares and updating them when you go from an interval to the next.

$\endgroup$
1
$\begingroup$

Suppose $A, B \in \mathbb R^{n \times n}$ are given. We have the cost function

$$f (x,y) := \sum_{i,j=1}^n \left( \left| a_{ij} - x \, b_{ij} \right| - y \right)^2 = \sum_{i,j=1}^n (a_{ij} - x \, b_{ij})^2 - 2 y \sum_{i,j=1}^n \left| a_{ij} - x \, b_{ij} \right| + n^2 y^2$$

where

$$\begin{array}{rl} \displaystyle\sum_{i,j=1}^n (a_{ij} - x \, b_{ij})^2 &= \|A - x B\|_F^2\\ &= \operatorname{tr} ((A - x B)^T (A - x B))\\\\ &= \operatorname{tr} (B^T B) \, x^2 - 2 \operatorname{tr} (A^T B) \, x + \operatorname{tr} (A^T A)\end{array}$$

and

$$\sum_{i,j=1}^n \left| a_{ij} - x \, b_{ij} \right| = \|\operatorname{vec} (A) - x \, \operatorname{vec} (B)\|_1$$

Hence.

$$f (x,y) = \begin{bmatrix} 1\\ x \\ y\end{bmatrix}^T \begin{bmatrix} \,\,\,\,\, \operatorname{tr} (A^T A) & - \operatorname{tr} (A^T B) & 0\\ - \operatorname{tr} (A^T B) & \,\,\,\,\,\operatorname{tr} (B^T B) & 0\\ 0 & 0 & n^2\end{bmatrix} \begin{bmatrix} 1\\ x \\ y\end{bmatrix} - 2 y \, \| \operatorname{vec} (A) - x \, \operatorname{vec} (B)\|_1$$

It is not obvious to me how to handle the $\|\cdot\|_1$ part of this cost function.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .