Generalized-norm conjugate direction solver

Appendix A: analytical derivation of plane-search step sizes

This appendix shows the details on generalization of plane-search algorithm for a general norm (or measure) $C(\cdot)$. As discussed previously and by Claerbout (2009), we use Taylor series expansion to find analytical forms for the step sizes in the plane-search algorithm. We form the updates in the residual value $\bf r$ by a linear combination of the gradient ${\bf g}^{(d)}$ and the previous step update of the residual ${\bf s}^{(d)}$, i.e. ${\bf r} ={\bf r} +\alpha {\bf g}^{(d)} + \beta {\bf s}^{(d)}$. Then the misfit objective function $E({\bf r})$ is given by

$$\begin{split}E ({\bf r}) &= \sum_i C(r_i + \alpha g^{(d)}_i +... ...g^{(d)}_i + \beta  s^{(d)}_i \Big )^2}{2!} C''(r_i) \end{split}$$ (16)

where $r_i$ is the residual from the current iteration. The Taylor series expansion in Equation 8 lets us find analytical derivatives of the misfit function $E({\bf r})$ with respect to both $\alpha$ and $\beta$ as follows:

$$\frac{\partial E}{\partial \alpha} = \sum_i g^{(d)}_i C'(r_i) + (\alpha g^{(d)}_i + \beta s^{(d)}_i) g^{(d)}_i C''(r_i) = 0 ,$$ (17)

$$\frac{\partial E}{\partial \beta} = \sum_i s^{(d)}_i C'(r_i) + (\alpha g^{(d)}_i + \beta s^{(d)}_i) s^{(d)}_i C''(r_i)= 0 .$$ (18)

By setting these derivatives to zero and solving the $2\times2$ system of equations we find an optimal step size in both directions ${\bf g}^{(d)}$ and ${\bf s}^{(d)}$. The equation below shows the solutions $\alpha$ and $\beta$ for this system of equations in a simplified notation.

$${\sum}  C''_i(r) \begin{bmatrix}\begin{pmatrix}g^{(d)}_i \ s^{(... ...bmatrix} = -{\sum}  C'_i(r) \begin{pmatrix}g^{(d)}_i \ s^{(d)}_i\end{pmatrix}$$ (19)

Generalized-norm conjugate direction solver