Derivative of $\|Ax-b\|_1$

341 Views Asked by At

Using least squares approximation

$E^2 = \| Ax - b\|^2 = (a_1x - b_1)^2+...+(a_mx-b_m)^2$

The derivative of E^2 at the point $\hat{x}$ is zero if:

$(a_1\hat{x}-b_1)a_1+...+(a_m\hat{x}-b_m)a_m=0$

Then:

$\hat{x} = \dfrac{(a_1b_1+...+a_mb_m)}{(a^2_1+...+a^2_m)} = \dfrac{a^Tb}{a^Ta}$

What about using least absolute derivation instead of least squares?

Where $E = \| Ax - b\|$

I want to be able to use least absolute derivation to solve for $A,B,C$ such that an outlier won't affect the solutions much.

$R=1$

$2A+B = C+R.$

$B+C = 5A.$

$A+C+2R = B+4R.$

$A+B+C = 6.33R$

This is in continuation of the last two questions I asked.

1

There are 1 best solutions below

3
On

Regardless of the misuse of notation as I pointed out in a comment, the question is $$D \| Ax-b\|_1 =\ ?$$ First look at $\|x\|_1$, the derivative is$\newcommand{\sgn}{{\rm sgn}}$ $$D\| x\|_1 = (\sgn(x_1), \ldots, \sgn(x_n))$$ Where $x_i \ne 0$ for all $i$ and undefined else. (The undefinedness, especially for the excat solution is the reason we usually use least-squares). The chain rule with $D_x (Ax) = A^T$ gives $$D \| Ax - b\|_1 = D\|\cdot\|_1 (Ax-b) \cdot A^T = \sgn(Ax-b)^T A^T = (A\ \sgn(Ax-b))^T$$ Where $\sgn$ is to be taken component-wise. Again this is undefined for any $x$ such that $a_i^T x - b_i = 0$ so for any $x$ having one $0$-residue, wich is bad because ideally we want $Ax-b = 0$ where the derivative is undefined for all components.