How to solve this equation (may be with least squares)?

Question

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?

Answer 1

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.

Answer 2

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.