@Presentation {peters2015SINBADFqpf, title = {A quadratic-penalty full-space method for waveform inversion}, journal = {SINBAD Fall consortium talks}, year = {2015}, publisher = {SINBAD}, abstract = {In PDE-constrained optimization problems other than geophysical full-waveform inversion, full-space optimization methods are commonly used. This type of optimization method updates both the medium parameters and the wavefields, instead of solving wave equations explicitly. In the FWI context, this means the objective function value and gradient can be obtained at very little computational cost. A major obstacle is, however, the requirement to have all wavefields in memory.}, keywords = {Presentation, private, SINBAD, SINBADFALL2015, SLIM}, url = {https://www.slim.eos.ubc.ca/Publications/Private/Conferences/SINBAD/2015/Fall/peters2015SINBADFqpf/peters2015SINBADFqpf.pdf}, url2 = {https://www.slim.eos.ubc.ca/Publications/Private/Conferences/SINBAD/2015/Fall/peters2015SINBADFqpf/peters2015SINBADFqpf.mov}, author = {Bas Peters and Felix J. Herrmann} } @article {vanleeuwen2015IPpmp, title = {A penalty method for {PDE}-constrained optimization in inverse problems}, journal = {Inverse Problems}, volume = {32}, number = {1}, year = {2015}, note = {(Inverse Problems)}, month = {12}, pages = {015007}, abstract = {Many inverse and parameter estimation problems can be written as PDE-constrained optimization problems. The goal is to infer the parameters, typically coefficients of the PDE, from partial measurements of the solutions of the PDE for several right-hand sides. Such PDE-constrained problems can be solved by finding a stationary point of the Lagrangian, which entails simultaneously updating the parameters and the (adjoint) state variables. For large-scale problems, such an all-at-once approach is not feasible as it requires storing all the state variables. In this case one usually resorts to a reduced approach where the constraints are explicitly eliminated (at each iteration) by solving the PDEs. These two approaches, and variations thereof, are the main workhorses for solving PDE-constrained optimization problems arising from inverse problems. In this paper, we present an alternative method that aims to combine the advantages of both approaches. Our method is based on a quadratic penalty formulation of the constrained optimization problem. By eliminating the state variable, we develop an efficient algorithm that has roughly the same computational complexity as the conventional reduced approach while exploiting a larger search space. Numerical results show that this method indeed reduces some of the nonlinearity of the problem and is less sensitive to the initial iterate.}, keywords = {Inverse problems, Optimization, PDE, penalty method}, url = {https://www.slim.eos.ubc.ca/Publications/Public/Journals/InverseProblems/2015/vanleeuwen2015IPpmp/vanleeuwen2015IPpmp.pdf}, url2 = {http://stacks.iop.org/0266-5611/32/i=1/a=015007}, author = {Tristan van Leeuwen and Felix J. Herrmann} } @conference {leeuwen2014EAGEntf, title = {A new take on {FWI}: wavefield reconstruction inversion}, booktitle = {EAGE Annual Conference Proceedings}, year = {2014}, month = {06}, abstract = {We discuss a recently proposed novel method for waveform inversion: Wavefield Reconstruction Inversion (WRI). As opposed to conventional FWI {\textendash} which attempts to minimize the error between observed and predicted data obtained by solving a wave equation {\textendash} WRI reconstructs a wave-field from the data and extracts a model-update from this wavefield by minimizing the wave-equation residual. The method does not require explicit computation of an adjoint wavefield as all the necessary information is contained in the reconstructed wavefield. We show how the corresponding model updates can be interpreted physically analogously to the conventional imaging-condition-based approach.}, keywords = {EAGE, Full-waveform inversion, Optimization, penalty method, Wavefield Reconstruction Inversion}, doi = {10.3997/2214-4609.20140703}, url = {https://www.slim.eos.ubc.ca/Publications/Public/Conferences/EAGE/2014/leeuwen2014EAGEntf/leeuwen2014EAGEntf.pdf}, presentation = {https://www.slim.eos.ubc.ca/Publications/Public/Conferences/EAGE/2014/leeuwen2014EAGEntf/leeuwen2014EAGEntf_pres.pdf}, author = {Tristan van Leeuwen and Felix J. Herrmann and Bas Peters} } @InProceedings{SchmidtBergFriedlanderMurphy:2009, author = {M. Schmidt and E. van den Berg and M. P. Friedlander and K. Murphy}, title = {Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm}, booktitle = {Proceedings of The Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS) 2009}, pages = {456-463}, year = 2009, editor = {D. van Dyk and M. Welling}, volume = 5, address = {Clearwater Beach, Florida}, month = {April}, } @article{Symes2007, author = {Symes}, title = {Reverse Time Migration with Optimal Checkpointing}, journal = {GEOPHYSICS}, volume = {72}, number = {5}, pages = {SM213-SM221}, year = {2007}, doi = {10.1190/1.2742686}, URL = {http://library.seg.org/doi/abs/10.1190/1.2742686}, eprint = {http://library.seg.org/doi/pdf/10.1190/1.2742686} } @article {Virieux, author = {J. Virieux and S. Operto}, title = {An overview of full-waveform inversion in exploration geophysics}, journal = {GEOPHYSICS}, volume = {74}, number = {5}, pages = {WCC1-WCC26 }, year = {2009}, doi = {10.1190/1.3238367}, URL = {http://library.seg.org/doi/abs/10.1190/1.3238367}, eprint = {http://library.seg.org/doi/pdf/10.1190/1.3238367} } @article{Plessi, author = {Plessi}, title = {A review of the adjoint-state method for computing the gradient of a functional with geophysical applications}, journal = {Geophysical Journal International}, volume = {167}, number = {2}, pages = {495-503}, year = {2006}, doi = {10.1111/j.1365-246X.2006.02978.x}, URL = {http://gji.oxfordjournals.org/content/167/2/495.short}, eprint = {http://gji.oxfordjournals.org/content/167/2/495.full.pdf} } @ARTICLE{Griewank2000ARA, author = "Andreas Griewank and Andrea Walther", title = "Algorithm 799: {R}evolve: {A}n Implementation of Checkpoint for the Reverse or Adjoint Mode of Computational Differentiation", note = "Also appeared as Technical University of Dresden, Technical Report IOKOMO-04-1997.", ad_theotech = "Checkpointing", journal = "{ACM} Transactions on Mathematical Software", volume = "26", number = "1", pages = "19--45", year = "2000", CODEN = "ACMSCU", ISSN = "0098-3500" } @MISC{Clapp, author = {Clapp}, title = {Reverse time migration with random boundaries}, year = {2009}, report ={Stanford Exploration Project}, number={SEP138}, url={http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.359.6496&rep=rep1&type=pdf#page=35} } @mastersthesis {Skajaa, year = {2010}, school = {Courant Institute of Mathematical ScienceNew York University}, type = {masters}, author = {A. Skajaa}, title = {Limited Memory BFGS for Nonsmooth Optimization}, url = {http://cs.nyu.edu/overton/mstheses/skajaa/msthesis.pdf} } @conference {wason2013EAGEobs, title = {Ocean bottom seismic acquisition via jittered sampling}, booktitle = {EAGE}, year = {2013}, month = {06}, abstract = {We present a pragmatic marine acquisition scheme where multiple source vessels sail across an ocean-bottom array firing at airgunsjittered source locations and instances in time. Following the principles of compressive sensing, we can significantly impact the reconstruction quality of conventional seismic data (from jittered data) and demonstrate successful recovery by sparsity promotion. In contrast to random (under)sampling, acquisition via jittered (under)sampling helps in controlling the maximum gap size, which is a practical requirement of wavefield reconstruction with localized sparsifying transforms. Results are illustrated with simulations of time-jittered marine acquisition, which translates to jittered source locations for a given speed of the source vessel, for two source vessels.}, keywords = {Acquisition, blended, deblending, EAGE, interpolation, marine}, doi = {10.3997/2214-4609.20130379}, url = {https://www.slim.eos.ubc.ca/Publications/Public/Conferences/EAGE/2013/wason2013EAGEobs/wason2013EAGEobs.pdf}, presentation = {https://www.slim.eos.ubc.ca/Publications/Public/Conferences/EAGE/2013/wason2013EAGEobs/wason2013EAGEobs_pres.pdf}, author = {Haneet Wason and Felix J. Herrmann} } @article {hennenfent2008GEOPsdw, title = {Simply denoise: wavefield reconstruction via jittered undersampling}, journal = {Geophysics}, volume = {73}, number = {3}, year = {2008}, month = {05}, pages = {V19-V28}, publisher = {SEG}, abstract = {In this paper, we present a new discrete undersampling scheme designed to favor wavefield reconstruction by sparsity-promoting inversion with transform elements that are localized in the Fourier domain. Our work is motivated by empirical observations in the seismic community, corroborated by recent results from compressive sampling, which indicate favorable (wavefield) reconstructions from random as opposed to regular undersampling. As predicted by theory, random undersampling renders coherent aliases into harmless incoherent random noise, effectively turning the interpolation problem into a much simpler denoising problem. A practical requirement of wavefield reconstruction with localized sparsifying transforms is the control on the maximum gap size. Unfortunately, random undersampling does not provide such a control and the main purpose of this paper is to introduce a sampling scheme, coined jittered undersampling, that shares the benefits of random sampling, while offering control on the maximum gap size. Our contribution of jittered sub-Nyquist sampling proves to be key in the formulation of a versatile wavefield sparsity-promoting recovery scheme that follows the principles of compressive sampling. After studying the behavior of the jittered undersampling scheme in the Fourier domain, its performance is studied for curvelet recovery by sparsity-promoting inversion (CRSI). Our findings on synthetic and real seismic data indicate an improvement of several decibels over recovery from regularly-undersampled data for the same amount of data collected.}, keywords = {Acquisition, Compressive Sensing, Geophysics, Optimization, Processing, sampling, SLIM}, doi = {10.1190/1.2841038}, url = {https://www.slim.eos.ubc.ca/Publications/Public/Journals/Geophysics/2008/hennenfent08GEOsdw/hennenfent08GEOsdw.pdf}, html_version = {https://www.slim.eos.ubc.ca/Publications/Public/Journals/Geophysics/2008/hennenfent08GEOsdw/paper_html/paper.html}, author = {Gilles Hennenfent and Felix J. Herrmann} } @article {vanLeeuwen2014SISC3Dfds, title = {{3D} frequency-domain seismic inversion with controlled sloppiness}, journal = {SIAM Journal on Scientific Computing}, volume = {36}, number = {5}, year = {2014}, note = {(SISC)}, month = {10}, pages = {S192-S217}, abstract = {Seismic waveform inversion aims at obtaining detailed estimates of subsurface medium parameters, such as the spatial distribution of soundspeed, from multiexperiment seismic data. A formulation of this inverse problem in the frequency domain leads to an optimization problem constrained by a Helmholtz equation with many right-hand sides. Application of this technique to industry-scale problems faces several challenges: First, we need to solve the Helmholtz equation for high wave numbers over large computational domains. Second, the data consist of many independent experiments, leading to a large number of PDE solves. This results in high computational complexity both in terms of memory and CPU time as well as input/output costs. Finally, the inverse problem is highly nonlinear and a lot of art goes into preprocessing and regularization. Ideally, an inversion needs to be run several times with different initial guesses and/or tuning parameters. In this paper, we discuss the requirements of the various components (PDE solver, optimization method, \dots) when applied to large-scale three-dimensional seismic waveform inversion and combine several existing approaches into a flexible inversion scheme for seismic waveform inversion. The scheme is based on the idea that in the early stages of the inversion we do not need all the data or very accurate PDE solves. We base our method on an existing preconditioned Krylov solver (CARP-CG) and use ideas from stochastic optimization to formulate a gradient-based (quasi-Newton) optimization algorithm that works with small subsets of the right-hand sides and uses inexact PDE solves for the gradient calculations. We propose novel heuristics to adaptively control both the accuracy and the number of right-hand sides. We illustrate the algorithms on synthetic benchmark models for which significant computational gains can be made without being sensitive to noise and without losing the accuracy of the inverted model.}, keywords = {block-cg, Helmholtz equation, inexact gradient, Kaczmarz method, preconditioning, Seismic inversion}, doi = {10.1137/130918629}, url = {http://epubs.siam.org/doi/abs/10.1137/130918629}, url2 = {https://www.slim.eos.ubc.ca/Publications/Public/Journals/SIAM_Journal_on_Scientific_Computing/2014/vanLeeuwen2014SISC3Dfds/vanLeeuwen2014SISC3Dfds.pdf}, author = {Tristan van Leeuwen and Felix J. Herrmann} } @article {BurkeLO05, author = {James V. Burke and Adrian S. Lewis and Michael L. Overton}, title = {A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization}, journal = {{SIAM} Journal on Optimization}, volume = {15}, number = {3}, pages = {751--779}, year = {2005}, url = {http://dx.doi.org/10.1137/030601296}, doi = {10.1137/030601296}, timestamp = {Mon, 28 Jun 2010 08:52:21 +0200}, biburl = {http://dblp2.uni-trier.de/rec/bib/journals/siamjo/BurkeLO05}, bibsource = {dblp computer science bibliography, http://dblp.org} } @unpublished {peters2015SEGrwi, title = {Regularizing waveform inversion by projections onto convex sets {\textendash}- application to the {2D} {Chevron} 2014 synthetic blind-test dataset}, year = {2015}, note = {(submitted to the SEG conference)}, abstract = {A framework is proposed for regularizing the waveform inversion problem by projections onto intersections of convex sets. Multiple pieces of prior information about the geology are represented by multiple convex sets, for example limits on the velocity or minimum smoothness conditions on the model. The data-misfit is then minimized, such that the estimated model is always in the intersection of the convex sets. Therefore, it is clear what properties the estimated model will have at each iteration. This approach does not require any quadratic penalties to be used and thus avoids the known problems and limitations of those types of penalties. It is shown that by formulating waveform inversion as a constrained problem, regularization ideas such as Tikhonov regularization and gradient filtering can be incorporated into one framework. The algorithm is generally applicable, in the sense that it works with any (differentiable) objective function and does not require significant additional computation. The method is demonstrated on the inversion of the 2D marine isotropic elastic synthetic seismic benchmark by Chevron using an acoustic modeling code. To highlight the effect of the projections, we apply no data pre-processing.}, keywords = {blind-test, private, projection, regularization, SEG, Wavefield Reconstruction Inversion, waveform inversion}, url = {https://www.slim.eos.ubc.ca/Publications/Private/Conferences/SEG/2015/peters2015SEGrwi/peters2015SEGrwi.html}, author = {Bas Peters and Zhilong Fang and Brendan Smithyman and Felix J. Herrmann} } @unpublished {louboutin2015SEGtcs, title = {Time compressively sampled full-waveform inversion with stochastic optimization}, year = {2015}, note = {(submitted to the SEG conference)}, abstract = {Time-domain Full-Waveform Inversion (FWI) aims to image the subsurface of the earth accurately from field recorded data and can be solved via the reduced adjoint-state method. However, this method requires access to the forward and adjoint wavefields that are meet when computing gradient updates. The challenge here is that the adjoint wavefield is computed in reverse order during time stepping and therefore requires storage or other type of mitigation because storing the full time history of the forward wavefield is too expensive in realistic 3D settings. To overcome this challenge, we propose an approximate adjoint-state method where the wavefields are subsampled randomly, which drastically the amount of storage needed. By using techniques from stochastic optimization, we control the errors induced by the subsampling. Examples of the proposed technique on a synthetic but realistic 2D model show that the subsampling-related artifacts can be reduced significantly by changing the sampling for each source after each model update. Combination of this gradient approximation with a quasi-Newton method shows virtually artifact free inversion results requiring only 5\% of storage compared to saving the history at Nyquist. In addition, we avoid having to recompute the wavefields as is required by checkpointing.}, keywords = {acoustic, Full-waveform inversion, inversion, private, SEG, Stochastic optimization, Subsampling, Time-domain}, url = {https://www.slim.eos.ubc.ca/Publications/Private/Conferences/SEG/2015/louboutin2015SEGtcs/louboutin2015SEGtcs.html}, author = {Mathias Louboutin and Felix J. Herrmann} } @MISC{Sava06time-shiftimaging, author = {Paul Sava and Sergey Fomel}, title = {Time-Shift Imaging Condition in Seismic Migration}, year = {2006} } @article{CurtQue13, author = {Curtis, F. E. and Que, X.}, title = {{An Adaptive Gradient Sampling Algorithm for Nonsmooth Optimization}}, journal = {Optimization Methods and Software}, volume = {28}, number = {6}, pages = {1302--1324}, year = {2013}, url = {http://coral.ie.lehigh.edu/~frankecurtis/wp-content/papers/CurtQue13.pdf} } @article{CurtQue15, author = {Curtis, F. E. and Que, X.}, title = {{A Quasi-Newton Algorithm for Nonconvex, Nonsmooth Optimization with Global Convergence Guarantees}}, journal = {Mathematical Programming Computation}, volume = {DOI: 10.1007/s12532-015-0086-2}, number = {}, pages = {}, year = {2015}, url = {http://coral.ie.lehigh.edu/~frankecurtis/wp-content/papers/CurtQue15.pdf} }