next up previous print clean
Next: norm Up: Attenuation of the noise Previous: Attenuation of the noise

Preconditioning for accelerated convergence

A generally available preconditioning method is to change variables so that the regularization operator becomes an identity matrix Claerbout and Fomel (2002). The gradient $\nabla$ in equation (2) has no inverse, but its spectrum $-\nabla'\nabla$, which appears in equation (3), can be factored ($-\nabla'\nabla={\bf H'H}$) into triangular parts ${\bf H}$ and ${\bf H'}$ where ${\bf H}$ is known as the Helix derivative. This ${\bf H}$ is invertible by deconvolution Claerbout (1998). The fitting goals in equation (2) can be then rewritten  
 \begin{displaymath}
\begin{array}
{lllll}
 \bold 0 &\approx& \bold r_d &=& \bold...
 ...&\approx& \epsilon \bold r_p &=& \epsilon \bold p,
 \end{array}\end{displaymath} (4)
with ${\bf p}={\bf Hh} \approx \nabla {\bf h}$ and $\bold r_p$ is the residual for the new variable ${\bf p}$. We then minimize the misfit function
\begin{displaymath}
f(\bold p) = \Vert\bold r_d\Vert^2+\epsilon^2\Vert\bold r_p\Vert^2\end{displaymath} (5)
and finally compute ${\bf h}={\bf H^{-1}p}$ to estimate the interpolated map of the lake. Experience shows that iterative solution for ${\bf p}$ converges much more rapidly than iterative solution for ${\bf h}$ thus showing that ${\bf H}$ is a good choice for preconditioning. There is no simple way of knowing beforehand what is the best value of $\epsilon$. Practitioners like to see solutions for various values of $\epsilon$. Of course, that can cost a lot of computational effort. Practical exploratory data analysis is more pragmatic. Without a simple clear theoretical basis, analysts generally begin from ${\bf p=0}$ and then abandon the fitting goal $\bold 0 \approx \epsilon \bold r_p =\epsilon \bold p$Crawley (2000); Rickett et al. (2001). Implicitly, they take $\epsilon=0$. Then they examine the solution as a function of iteration, imagining that the solution at larger iterations corresponds to smaller $\epsilon$, and that the solution at smaller iterations corresponds to larger $\epsilon$. In all our computations, we follow this approach and omit the regularization in the estimation of the depth maps.
next up previous print clean
Next: norm Up: Attenuation of the noise Previous: Attenuation of the noise
Stanford Exploration Project
7/8/2003