next up previous [pdf]

Next: CGG with model weight Up: Conjugate-Guided-Gradient (CGG) method Previous: Conjugate-Guided-Gradient (CGG) method

CGG with residual weight guide

Suppose we apply the same residual weight $\mathbf W_r$ as the one we used in the IRLS method, to the residual when we compute the gradient $\mathbf \Delta \mathbf m$ but do not apply the weight when we compute the conjugate gradient $\mathbf \Delta \mathbf r$. This means that we do not change the operator from $\mathbf L$ to $\mathbf W_r \mathbf L$, and the weight affects only the gradient direction. This corresponds to guiding the gradient direction with a weighted residual, and the resultant gradient will be the same gradient as we used for the $\ell^p$-norm residual solution in the IRLS method. Unlike the IRLS method, however, we don't need to recompute the residual when the weight has changed since we did not change the operator while the iteration goes and the problem is the same problem as before we change the weight (i.e. we are solving a linear problem). This algorithm can be implemented as shown in Algorithm 3.


\begin{algorithm}
% latex2html id marker 109\caption{ CGG method with residual...
...mathbf m, \mathbf \Delta \mathbf r) $
\ENDWHILE
\end{algorithmic}\end{algorithm}

Notice that Algorithm 3 is different from the original CG method (Algorithm 1) only at the step of gradient $\mathbf \Delta \mathbf m$ computation; the modification of the gradient is performed by changing the residual before the gradient is computed from it. By choosing the weight as a function of the residual of the previous iteration step, as we did in the IRLS method, we can guide the gradient vector to the gradient vector of the $\ell^p$-norm. Thus the result obtained by weighting the residual in the CGG method could be interpreted as a localized LS solution in the subspace composed by the $\ell^p$-norm gradient vectors, not in the whole solution space. The minimum $\ell^2$-norm location is unlikely to be located along the gradient direction of the different $\ell^p$-norm which is guided by the applied weight. Therefore, it is more likely that the solution will be close to the minimum $\ell^p$-norm location which is guided by the applied weight.


next up previous [pdf]

Next: CGG with model weight Up: Conjugate-Guided-Gradient (CGG) method Previous: Conjugate-Guided-Gradient (CGG) method

2011-06-26