next up previous print clean
Next: Attenuation of the ship Up: Attenuation of the noise Previous: Preconditioning for accelerated convergence

${\ell^1}$ norm

We show how spikes and noise glitches can be attenuated with an approximate ${\ell^1}$ norm. One main problem with the Galilee data is the presence of glitches in the middle of the lake and at the track ends. Starting from equation (4), we can introduce a weighting operator that deemphasizes high residuals as follows:  
 \begin{displaymath}
\begin{array}
{lllll}
 \bold 0 &\approx& \bold r_d &=& \bold...
 ...&\approx& \epsilon \bold r_p &=& \epsilon \bold p,
 \end{array}\end{displaymath} (6)
with a diagonal matrix $\bf{W}$
\begin{displaymath}
{\bf W} = {\bf diag} \left( \frac{1}{(1+r_i^2/\bar{r}^2)^{1/4}} \right),\end{displaymath} (7)
where ri is the residual for one component of $\bold r_d$, and $\bar{r}$ a constant we choose a-priori. This weighting operator ranges from $\ell^2$ to ${\ell^1}$ depending on the constant $\bar{r}$. It is somewhat difficult to evaluate a good $\bar{r}$ for a particular problem because the transition between the two norms is smooth. We choose $\bar{r}=0.01$ cm which is very small. This choice is not based on geophysical considerations: $\bar{r}=10$ cm might appear a better choice since the measurements are recorded to an accuracy of about 10 cm. It is not based on statistical choices either as done by Bube and Langan (1997). This choice of $\bar{r}$ simply gives us the most pleasing results after inversion. Because it is very small, we are essentially simulating a ${\ell^1}$ norm only. The weighting operator $\bf{W}$ is kept constant for a number of iterations and then reevaluated. The IRLS method is guaranteed to converge to the ${\ell^1}$ estimate of the model parameters Bube and Langan (1997). The linear steps are computed with a conjugate gradient solver. Abandoning the damping in equation (6), i.e, $\epsilon=0$,makes the IRLS method very appealing because we focus on the minimization of the data residual. This is only possible with the preconditioning of the problem.

We now test our proposed method to get rid of the outliers. We then use the fitting goals in equations (4) and (6) to produce depth images of the Sea of Galilee. Equation (4) is referred as the $\ell^2$ norm solution and equation (6) as the ${\ell^1}$ norm solution.

In Figure [*]a, we show ${\bf p}$ estimated with the $\ell^2$ norm. Although ${\bf p}$ appears to be a variable of mathematical interest only, in fact, the solution ${\bf h}$ is so smooth that we have difficulty viewing it. We could view the two components of $\nabla \bold h $ but it happens that ${\bf p}$ is a roughened version of ${\bf h}$. Hence it is more convenient to view ${\bf p}$ than the two images $\partial \bold h/\partial x$and $\partial \bold h/\partial y$.We can see a lot of spurious noise everywhere in the map of Figure [*]a. In addition, we can see the vessel tracks in the north part of the map. This first result is obtained after 1000 iterations which means that we essentially simulate a least-squares solution without damping. Therefore, all the noise in the data is inverted for and mapped in the final model. With noisy data, it is common practice to use a damped least-squares to minimize the effects of the noise. We can easily simulate a damped least-squares solution by decreasing the number of iterations, as explained in the preceding section. In Figure [*]b, we show the roughened map of the Sea of Galilee after 50 iterations, thus recreating the solution of a damped least-squares problem. Most of the noise has been attenuated but glitches are still present in the northern part of the lake and the ${\ell^1}$ norm should be utilized.

Figure [*]c displays ${\bf p}$ estimated with the ${\ell^1}$ norm (e.g., equation (6) with a small $\bar{r}$). Most of the glitches are attenuated showing vessel tracks only. Some ancient shorelines in the west part and south part of the Sea of Galilee are now easy to identify. In addition, we also start to see a ``valley'' in the middle of the lake that probably represents the on-going rifting in this area. The data outside the sea have been also partially removed.

Figures [*]a,b,c show the bottom of the Sea of Galilee (${\bf h}={\bf H^{-1}p}$) after inversion. The ${\ell^1}$ result is a great improvement over the $\ell^2$ maps with or without damping. The glitches inside and outside the sea have disappeared. It is also pleasing to see that the ${\ell^1}$ norm gives us positive depths everywhere. Although not everywhere visible in Figure [*], it is interesting to notice that we produce topography outside the lake. Indeed, the effect of regularization is to produce synthetic topography which is a natural continuation of the lake floor.

We have shown that the combined utilization of preconditioning and IRLS removes the spikes in the depth map of the Sea of Galilee. In the next section, we propose removing the ship tracks by introducing an operator in equation (6) that will model the coherent noise created by different weather and human conditions during the acquisition of the data.

 
comp-L1-L2
comp-L1-L2
Figure 4
(a) ${\bf p}$ estimated with equation (4) in a least-squares sense after 1000 iterations, which simulates a least-squares solution without damping. (b) ${\bf p}$ estimated with equation (4) in a least-squares sense after 50 iterations, which simulates a least-squares solution with damping. (c) ${\bf p}$estimated with equation (6) in a ${\ell^1}$ sense. The spikes have been correctly attenuated.
[*] view burn build edit restore

 
comp-L1-L2-depth
comp-L1-L2-depth
Figure 5
(a) View of the bottom of the lake (${\bf h}={\bf H^{-1}p}$) with the $\ell^2$norm after 1000 iterations, which simulates a least-squares solution without damping. (b) View of the bottom of the lake with the $\ell^2$norm after 50 iterations, which simulates a least-squares solution with damping. (c) View of the bottom of the lake with the ${\ell^1}$ norm. Note that with the ${\ell^1}$ norm, all the depth values are now positives and that the spikes have been attenuated.
[*] view burn build edit restore


next up previous print clean
Next: Attenuation of the ship Up: Attenuation of the noise Previous: Preconditioning for accelerated convergence
Stanford Exploration Project
7/8/2003