Blocky models via the L1/L2 hybrid norm

Model derivatives

Here is the usual definition of residual $r_i$ of theoretical data $\sum_j F_{i,j} m_j$ from observed data $d_i$

$$r_i = (\sum_j F_{i,j} m_j) - d_i \quad\quad {\rm or}\quad\quad \bold r = \bold F \bold m - \bold d.$$ (1)

Let $C()$ be a convex function ($C''\ge 0$) of a scalar. The penalty function (or norm of residuals is expressed by

$$N(\bold m) = \sum_i C(r_i)$$ (2)

We denote a column vector $\bold g$ with components $g_i$ by $\bold g = \rm vec(g_i)$. We soon require the derivative of $C(r)$ at each residual $r_i$:

$$\bold g \quad=\quad \rm vec\left[ \frac{\partial C(r_i)}{\partial r_i} \right]$$ (3)

We often update models in the direction of the gradient of the norm of the residual.

$$\Delta\bold m \quad=\quad \frac{\partial N}{ \partial m_k} \quad=... ...i}{ \partial m_k} \quad=\quad \sum_i g(r_i) F_{i,k} \quad=\quad \bold F'\bold g$$ (4)

Define a model update direction by $\Delta \bold m = \bold F'\bold g$. Since $\bold r = \bold F\bold m -\bold d$, we see the residual update direction will be $\Delta \bold r = \bold F \Delta \bold m$. To find the distance $\alpha$ to move in those directions

$$\bold m \leftarrow \bold m + \alpha\Delta \bold m$$ (5)

$$\bold r \leftarrow \bold r + \alpha\Delta \bold r$$ (6)

we choose the scalar $\alpha$ to minimize

$$N(\alpha) = \sum_i C(r_i+\alpha\Delta r_i)$$ (7)

The sum in equation (7) is a sum of ``dishes'', shapes between L2 parabolas and L1 V's. The $i$-th dish is centered on $\alpha = -r_i/\Delta r_i$. It is steep and narrow if $\Delta r_i$ is large, and low and flat where $\Delta r_i$ is small. The positive sum of convex functions is convex. There are no local minima. We can get to the bottom by following the gradient. Next we consider some choices for convex functions. We'll need them, their first and second derivatives.

Blocky models via the L1/L2 hybrid norm