View source for User:Ifarley/Full-waveform inversion, Part 2: Adjoint modeling

{{Tutorial|TLE|January 2018}}
This is the second part of a three-part tutorial series on [[full-waveform inversion|full-waveform inversion (FWI)]] in which we provide a step-by-step walk through of setting up forward and adjoint wave equation solvers and an optimization framework for inversion. In [[Full-waveform inversion 1: forward modeling|Part 1]]<ref>Louboutin, M., Witte, P., Lange, M., Kukreja, N., Luporini, F., Gorman, G., and Herrmann, F., 2017, Full-waveform inversion, Part 1: Forward modeling: ''The Leading Edge'', 36, 1033–1036. {{doi|10.1190/tle36121033.1}}</ref>, we showed how to use [http://www.opesci.org/devito-public/ Devito] to set up and solve acoustic wave equations with (impulsive) seismic sources and sample wavefields at the receiver locations to forward model shot records. Here in Part 2, we will discuss how to set up and solve adjoint wave equations with Devito and, from that, how we can calculate gradients and function values of the FWI objective function.

== Introduction ==
The gradient of FWI is most commonly computed via the adjoint-state method, by crosscorrelating forward and adjoint wavefields and summing the contributions over all time steps<ref name=Plessix>Plessix, R. E., 2016, A review of the adjoint-state method for computing the gradient of a functional with geophysical applications: ''Geophysical Journal International'', 167, 495–503. {{doi|10.1111/j.1365-246X.2006.02978.x}}</ref>. Calculating the gradient for one source location consists of three steps:

#Solve the forward wave equation to create a shot record. The time varying wavefield must be stored for use in step 3; techniques such as subsampling can be used to reduce the storage requirements.
#Compute the data residual (or misfit) between the predicted and observed data.
#Solve the corresponding discrete adjoint model using the data residual as the source. Within the adjoint (reverse) time loop, crosscorrelate the second time derivative of the adjoint wavefield with the forward wavefield. These crosscorrelations are summed to form the gradient.

We start with the definition and derivation of the adjoint wave equation and its Devito stencil and then show how to compute the gradient of the conventional least-squares FWI misfit function. As usual, this tutorial is accompanied by all the code you need to reproduce the figures. Go to http://github.com/seg/tutorials-2018 and follow the links.

== A simple experiment ==
To demonstrate the gradient computation in the simplest possible way, we perform a small seismic transmission experiment with a circular imaging phantom, i.e., a constant velocity model with a circular high-velocity inclusion in its center, as shown in Figure 1. For a transmission experiment, we place 21 seismic sources on the left-hand side of the model and 101 receivers on the right-hand side.

[[File:Tle37010069.1 fig1.jpeg|thumb|center|500px|Figure 1:  (a) The velocity model, with sources and receivers arranged vertically. (b) The initial estimate. (c) The difference between the model and the initial estimate.]]

We will use the forward propagator from [[Full-waveform inversion 1: forward modeling|Part 1]] to independently model the 21 “observed” shot records using the true model. As the initial model for our gradient calculation, we use a constant velocity model with the same velocity as the true model, but without the circular velocity perturbation. We will then model the 21 predicted shot records for the initial model, calculate the data residual and gradient for each shot, and sum them to obtain the full gradient.

== The adjoint wave equation ==
Adjoint wave equations are a main component in seismic inversion algorithms and are required for computing gradients of both linear and nonlinear objective functions. To ensure stability of the adjoint modeling scheme and the expected convergence of inversion algorithms, it is important that the adjoint wave equation is in fact the adjoint (transpose) of the forward wave equation. The derivation of the adjoint wave equation in the acoustic case is simple, as it is self-adjoint if we ignore the absorbing boundaries for the moment. However, in the general case, discrete wave equations do not have this property (such as the coupled anisotropic TTI wave equation<ref>Zhang, Y., Zhang, H., and Zhang, G., 2011, A stable TTI reverse time migration and its implementation: ''Geophysics'', 76, WA3–WA11. {{doi|10.1190/1.3554411}}</ref>) and require correct derivations of their adjoints. We concentrate here, as in [[Full-waveform inversion 1: forward modeling|Part 1]], on the acoustic case and follow an optimize-discretize approach, which means we write out the adjoint wave equation for the continuous case first and then discretize it, using finite-difference operators of the same order as for the forward equation. With the variables defined as in [[Full-waveform inversion 1: forward modeling|Part 1]] and the data residual <math>\delta d(x,y,t,x_{r},y_{r})</math>, located at <math>x_{r},y_{r}</math> (receiver locations) as the adjoint source, the continuous adjoint wave equation is given by:

<math>m(x,y)\frac{{d}^{2}v(t,x,y)}{{{d}t^{2}}}-\Delta v(t,x,y)-\mathit{\Eta}(t,x,y)=\delta d(t,x,y;x_{r},y_{r})</math>.

The adjoint acoustic wave equation is equivalent to the forward equation with the exception of the damping term <math>\mathit{\Eta}(t,x,y)=\eta (x,y)dv (t,x,y)/dt</math>, which contains a first time derivative and therefore has a change of sign in its adjoint. (A second derivative matrix is the same as its transpose, whereas a first derivative matrix is equal to its negative transpose and vice versa.)

Following the pattern of [[Full-waveform inversion 1: forward modeling|Part 1]], we first define the discrete adjoint wavefield '''v''' as a Devito <code>TimeFunction</code> object. For reasons we will explain later, we do not need to save the adjoint wavefield:

<pre>
v = TimeFunction (name="v", grid=model.grid,
                  time_order=2, space_order=4,
                  save=False)
</pre>

Now symbolically set up the PDE:
<pre>pde = model.m * v.dt2 - v.laplace - model.damp * v.dt</pre>

As before, we then define a stencil:
<pre>stencil_v = Eq(v.backward, solve(pde, v.backward)[0])</pre>

Just as for the forward wave equation, <code>stencil_v</code> defines the update for the adjoint wavefield of a single time step. The only difference is that, while the forward-modeling propagator goes forward in time, the adjoint propagator goes backward in time, since the initial time conditions for the forward propagator turn into final time conditions for the adjoint propagator. As for the forward stencil, we can write out the corresponding discrete expression for the update of the adjoint wavefield:

<math>\mathbf{v}\begin{bmatrix}
time - dt
\end{bmatrix}=2\mathbf{v}\begin{bmatrix}
time
\end{bmatrix}-\mathbf{v}\begin{bmatrix}
time + dt
\end{bmatrix}+{\frac{dt^{2}}{\boldsymbol{\mathbf{m}}}}\Delta \mathbf{v}\begin{bmatrix}
time
\end{bmatrix}</math>,

with dt being the time-stepping interval. Once again, this expression does not contain any (adjoint) source terms so far, which will be defined as a separate <code>SparseFunction</code> object. Since the source term for the adjoint wave equation is the difference between an observed and modeled shot record, we first define an (empty) shot record <code>residual</code> with 101 receivers and coordinates defined in <code>rec_coords</code>. We then set the data field <code>rec.data</code> of our shot record to be the data residual between the observed data <code>d_obs</code> and the predicted data <code>d_pred</code>. The symbolic residual source expression <code>res_term</code> for our adjoint wave equation is then obtained by ''injecting'' the data residual into the modeling scheme (<code>residual.inject</code>). Since we solve the time-stepping loop backward in time, the <code>res_term</code> is used to update the previous adjoint wavefield <code>v.backward</code>, rather than the next wavefield. As in the forward-modeling example, the source is scaled by <math>{d}t^{2}{/}\mathbf{m}</math>. In Python, we have:
<pre>
residual = PointSource(name='residual', ntime=nt
                       grid=model.grid, coordinates=rec_coords)

res_term = residual.inject(field=v.backward,
                           expr=residual * dt**2 / model.m,
                           offset=model.nbpml)
</pre>

In this demonstration, there is no real data. Instead we will generate the “observed” data via forward modeling with the true model <code>model</code>. The synthetic data is generated from the initial model <code>model0</code>. The resulting data, and their difference, are shown in Figure 2.

[[File:Tle37010069.1 fig2.jpeg|thumb|center|500px|Figure 2: Shot records for a shot at a Z position of 0.5 km. (a) The observed data, using the known model with the high-velocity disc, contains a perturbation not present in (b) the “predicted” data, using the initial estimate of the model, which contains no disc. (c) The residual.]]

[[File:Tle37010069.1 fig3.jpeg|thumb|center|500px|Figure 3: Gradient plots for (a) a single shot at 0.5 km and (b) the sum of all shots.]]

Finally, we create the full propagator by adding the residual source expression to our previously defined stencil and set the flag <code>time_axis=Backward</code>, to specify that the propagator runs backward in time:

<pre>op_adj = Operator([stencil_v] + res_term, time_axis=Backward)</pre>

In contrast to forward modeling, we do not record any measurements at the surface since we are only interested in the adjoint wavefield itself. The full script for setting up the adjoint wave equation, including an animation of the adjoint wavefield is available in <code>adjoint_modeling.ipynb</code>.

== Computing the FWI gradient ==
The goal of FWI is to estimate a discrete parametrization of the subsurface by minimizing the misfit between the observed shot records of a seismic survey and numerically modeled shot records. The predicted shot records are obtained by solving an individual wave equation per shot location and depend on the parametrization '''m''' of our wave propagator. The most common function for measuring the data misfit between the observed and modeled data is the <math>\ell_{2}</math> norm, which leads to the following objective function<ref>Lions, J. L., 1971, Optimal control of systems governed by partial differential equations: Springer-Verlag Berlin Heidelberg.</ref> <ref>Tarantola, A., 1984, Inversion of seismic reflection data in the acoustic approximation: ''Geophysics'', 49, 1259–1266. {{doi|10.1190/1.1441754}}</ref>:

<math>\underset{m}{minimize}f(\boldsymbol{\mathbf{m}})=\sum_{i=1}^{n_{s}}\frac{1}{2}\left |  \right |\boldsymbol{{d}}_{i}^{pred}(\boldsymbol{m},\boldsymbol{q}_{i})-\boldsymbol{d_{i}^{obs}}\left |  \right |_{2}^{2}</math>,

where the index ''i'' runs over the total number of shots <math>n_{s}</math>, and the model parameters are the squared slowness. Optimization problems of this form are called nonlinear least-squares problems, since the predicted data modeled with the forward-modeling propagator (<code>op_fwd()</code> in [[Full-waveform inversion 1: forward modeling|Part 1]]) depends nonlinearly on the unknown parameters '''m'''. The full derivation of the FWI gradient using the adjoint-state method is outside the scope of this tutorial, but conceptually we obtain the gradient by applying the chain rule and taking the partial derivative of the inverse wave equation <math>\mathbf{A}(\boldsymbol{m})^{-1}</math> with respect to '''m''', which yields the following expression<ref name=Plessix></ref> <ref>Virieux, J. and Operato S., 2009, An overview of full-waveform inversion in exploration geophysics: ''Geophysics'', 74, WCC1–WCC26. {{doi|10.1190/1.3238367}}</ref>:

<math>f(\mathbf{m})=-\sum_{i=1}^{n_{s}}\sum_{time=1}^{n_{t}}\mathbf{u}[time]\odot\ddot{v}[time]</math>.

The inner sum time = 1,…, <math>n_{t}</math> runs over the number of computational time steps <math>n_{t}</math> and <math>\ddot{v}</math> denotes the second temporal derivative of the adjoint wavefield '''v'''. Computing the gradient of equation 3, therefore corresponds to performing the point-wise multiplication (denoted by the symbol ⊙) of the forward wavefields with the second time derivative of the adjoint wavefield and summing over all time steps.

To avoid the need to store the adjoint wavefield, the FWI gradient is calculated in the reverse time loop while solving the adjoint wave equation. To compute the gradient '''g''' for the current time step '''v'''[time]:

<math>\mathbf{g}=\mathbf{g}-\frac{\mathbf{v}[time-dt]-2\mathbf{v}[time]+\mathbf{v}[time+dt]}{dt^{2}}\odot{\mathbf{u}[time]}</math>

The second time derivative of the adjoint wavefield is computed with a second-order finite-difference stencil and uses the three adjoint wavefields that are kept in memory during the adjoint time loop (equation 2).

In Devito, we define the gradient as a <code>Function</code> since the gradient is computed as the sum over all time steps and therefore has no time dependence:

<pre>grad = Function(name="grad", grid=model.grid)</pre>

The update for the gradient as defined in equations 4 and 5 is then:

<pre>grad_update = Eq(grad, grad - u * v.dt2)</pre>

Now we must add the gradient update expression to the adjoint propagator <code>op_grad</code>. This yields a single symbolic expression with update instructions for both the adjoint wavefield and the gradient:

<pre>op_grad = Operator([stencil_v] + res_term + [grad_update],
                        time_axis=Backward)
</pre>

Solving the adjoint wave equation by running the following now computes the FWI gradient for a single source. Its value is stored in <code>grad.data</code>.

<pre>op_grad(u=u0, v=v, m=mode10.m,
             residual=pred.data-obs.data,
             time=nt, dt=dt)
</pre>

Now we can iterate over all the shot locations, running the same sequence of commands each time.

This gradient can then be used for a simple gradient descent optimization loop, as illustrated at the end of the notebook <code>adjoint_modeling.ipynb</code>. After each update, a new gradient is computed for the new velocity model until sufficient decrease of the objective or chosen number of iteration is reached. A detailed treatment of optimization and more advanced algorithms will be described in the third and final part of this tutorial series.

== Conclusions ==
We need the gradient of the FWI objective function in order to find the optimal solution. It is computed by solving adjoint wave equations and summing the point-wise product of forward and adjoint wavefields over all time steps. Using Devito, the adjoint wave equation is set up in a similar fashion as the forward wave equation, with the main difference being the (adjoint) source, which is the residual between the observed and predicted shot records.

With the ability to model shot records and compute gradients of the FWI objective function, we are ready to demonstrate how to set up more gradient-based algorithms for FWI in Part 3 next month.

== Acknowledgments ==
This research was carried out as part of the SINBAD II project with the support of the member organizations of the SINBAD Consortium. This work was financially supported in part by EPSRC grant EP/L000407/1 and the Imperial College London Intel Parallel Computing Centre.

==Related links==
[[Full-waveform inversion 1: forward modeling]]

== References ==
{{reflist}}

== Corresponding authors  ==
* Corresponding author: Mathias Louboutin, Seismic Laboratory for Imaging and Modeling (SLIM), The University of British Columbia, {{Email|mloubout|eoas.ubc.ca}}
* Philipp Witte, Seismic Laboratory for Imaging and Modeling (SLIM), The University of British Columbia
* Michael Lange, Imperial College London, London, UK
* Navjot Kukreja, Imperial College London, London, UK
* Fabio Luporini, Imperial College London, London, UK
* Gerard Gorman, Imperial College London, London, UK
* Felix J. Herrmann, Seismic Laboratory for Imaging and Modeling (SLIM), The University of British Columbia, now at Georgia Institute of Technology, USA

==External links==
{{search}}

[[Category:Tutorials]]