II.2.2.1: Absolute Values

Suppose the problem we have to solve is to minimize $$f(x)=\sum_{i=1}^nw_i|h_i(x)|$$ over $x\in\mathcal{X}.$ Here $h_i(x)$ is supposed to be differentiable. In statistics it typically is a residual, for instance $h_i(x)=y_i-z_i'x.$ Suppose, for the time being, that $h_i(x)\not= 0$. Then we have the majorization $$\sum_{i=1}^nw_i|h_i(x)|\leq \frac{1}{2}\sum_{i=1}^n\frac{w_i}{|h_i(y)|} (h^2_i(x)+h^2_i(y)),$$ and we must minimize $$g(x,y):=\sum_{i=1}^n\frac{w_i}{|h_i(y)|}h^2_i(x),$$ which is a weighted least squares problem.

The simplest case of this is the one-dimensional example is $h_i(x)=y_i-x$, which means we want to compute the weighted median. The algorithm is simply $$x^{(k+1)}=\frac{\sum_{i=1}^n u_i(x^{(k)})y_i}{\sum_{i=1}^n u_i(x^{(k)})},$$ where $$u_i(x)=\frac{w_i}{\mid y_i-x\mid}.$$

We have assumed, so far, in this example that $h_i(y)\not= 0$. If $h_i(y)=0$ at some point in the iterative process then the majorization function does not exist, and we cannot compute the upgrade. One easy way out of this problem is to minimize $$f_\epsilon(x)=\sum_{i=1}^nw_i\sqrt{h_i^2(x)+\epsilon^2}$$ for small values of $\epsilon$. Clearly if $\epsilon_1>\epsilon_2$ then $$\min_x f_{\epsilon_1}(x)=f_{\epsilon_1}(x_1)>f_{\epsilon_2}(x_1)\geq\min_x f_{\epsilon_2}(x).$$ It follows that

The function $f_\epsilon$ is differentiable. We find $$\mathcal{D}f_\epsilon(x)=\sum_{i=1}^n w_i\frac{h_i(x)}{\sqrt{h_i^2(x)+\epsilon^2}}\mathcal{D}h_i(x),$$ and $$\mathcal{D}^2f_\epsilon(x)=\sum_{i=1}^n w_i\frac{1}{\sqrt{h_i^2(x)+\epsilon^2}} \left\{\frac{\epsilon^2}{h_i^2(x)+\epsilon^2}\left(\mathcal{D}h_i(x)\right)^2+h_i(x)\mathcal{D}^2h_i(x)\right\}.$$ With obvious modifications the same formulas apply if $x$ is a vector of unknowns, for instance if $h(x)=y-Zx$.

By the implicit function theorem the function $x(\epsilon)$ defined by $\mathcal{D}f_\epsilon(x(\epsilon))=0$ is differentiable, with derivative $$\mathcal{D}x(\epsilon)=\epsilon\frac{\sum_{i=1}^nw_i\left[h_i^2(x(\epsilon))^2+\epsilon^2\right]^{-\frac32}h_i(x(\epsilon))\mathcal{D}h_i(x(\epsilon))}{\mathcal{D}^2f_\epsilon(x(\epsilon))}$$

For the weighted median the iterates are still the same weighted averages, but now with weights $$u_i(x,\epsilon)=\frac{w_i}{\sqrt{(y_i-x)^2+\epsilon^2}}.$$ Differentiating the algorithmic map gives the convergence ratio $$\kappa_\epsilon(x)\mathop{=}\limits^{\Delta}\frac{\sum_{i=1}^n u_i(x,\epsilon)\frac{(y_i-x)^2}{(y_i-x)^2+\epsilon^2}}{\sum_{i=1}^n u_i(x,\epsilon)}.$$ Clearly $\min_i\frac{(y_i-x)^2}{(y_i-x)^2+\epsilon^2}\leq\kappa_\epsilon(x)\leq\max_i\frac{(y_i-x)^2}{(y_i-x)^2+\epsilon^2},$ which implies $\kappa_\epsilon(x)< 1.$ If $y_i\not=x$ for all $i$, then $\lim_{\epsilon\rightarrow 0}\kappa_\epsilon(x)=1$ and convergence is asymptotically sublinear.