Least-square inversion with inexact adjoints. Method of conjugate directions: A tutorial

First step of the improvement

Assuming $n>1$, we can add some amount of the previous step ${\bf s}_{n-1}$ to the chosen direction ${\bf c}_n$ to produce a new search direction ${\bf s}_n^{(n-1)}$, as follows:

$${\bf s}_n^{(n-1)} = {\bf c}_n + \beta_n^{(n-1)} {\bf s}_{n-1}\;,$$ (10)

where $\beta_n^{(n-1)}$ is an adjustable scalar coefficient. According to to the fundamental orthogonality principle (7),

$$\left({\bf r}_{n-1}, {\bf A s}_{n-1}\right) = 0\;.$$ (11)

As follows from equation (11), the numerator on the right-hand side of equation (9) is not affected by the new choice of the search direction:

$$\left({\bf r}_{n-1}, {\bf A s}_n^{(n-1)}\right)^2 = \left[... ...ght)\right]^2 = \left({\bf r}_{n-1}, {\bf A c}_n\right)^2\;.$$ (12)

However, we can use transformation (10) to decrease the denominator in (9), thus further decreasing the residual ${\bf r}_n$. We achieve the minimization of the denominator

$$\Vert{\bf A s}_n^{(n-1)}\Vert^2 = \Vert{\bf A c}_n\Vert^2 ... ...+ \left(\beta_n^{(n-1)}\right)^2 \Vert{\bf A s}_{n-1}\Vert^2$$ (13)

by choosing the coefficient $\beta_n^{(n-1)}$ to be

$$\beta_n^{(n-1)} = - {{\left({\bf A c}_n, {\bf A s}_{n-1}\right)} \over {\Vert{\bf A s}_{n-1}\Vert^2}}\;.$$ (14)

Note the analogy between (14) and (6). Analogously to (7), equation (14) is equivalent to the orthogonality condition

$$\left({\bf A s}_n^{(n-1)}, {\bf A s}_{n-1}\right) = 0\;.$$ (15)

Analogously to (8), applying formula (14) is also equivalent to defining the minimized denominator as

$$\Vert{\bf A c}_n^{(n-1)}\Vert^2 = \Vert{\bf A c}_n\Vert^2 ... ...A s}_{n-1}\right)^2} \over {\Vert{\bf A s}_{n-1}\Vert^2}}\;.$$ (16)

Least-square inversion with inexact adjoints. Method of conjugate directions: A tutorial