Seismology meets compressive sampling Felix J. Herrmann Seismic Laboratory for Imaging and Modeling Department of Earth and Ocean Sciences University of British Columbia (Canada) slim.eos.ubc.ca IPAM, UCLA, October 29 General trend (Seismic) data sets are becoming larger and larger Demand for more information to be inferred from data Data collection is expensive Distilling information is time consuming Industry ripe for recent developments in applied harmonic analysis and information theory Today’s topics Problems in seismic imaging acquisition, processing & imaging costs Compressive sampling in exploration seismology wavefield recovery from jittered sampling compressive wavefield extrapolation road ahead: compressive computations DNOISE: an academic-industry-NSERC partnership truly interdisciplinary academic collaboration knowledge dissemination 01 2 3 4 tim e [s ] -3000 -2000 -1000 offset [m] Seismic data acquisition Exploration seismology • create images of the subsurface • need for higher resolution/deeper • clutter and data incompleteness • image repeatability <=> monitoring 0 1 2 3 km 0 1 2 3 4 5 6 7 D ep th (k m ) Today’s challenges Seismic data volumes are extremely large (5-D, tera-peta bytes) incomplete and noisy operators expensive to apply Physics & mathematics not fully understood linearization PDE constrained optimization is remote Infusion of math has been a bumpy road inward looking after “the fact” proofs really understand problems that can not be tailored industry wants results not proofs ... DNOISE Felix J. Herrmann SLIM Michael Friedlander CS Ozgur Yilmaz Math IMA,IPAM BIRS,AIM BG BP Chevron Exxxon Mobil Shell Industry My research program Successfully leverage recent developments in applied computational harmonic analysis and information theory multi-directional transforms such as curvelets new construction that did not exist in seismology theory of compressive sampling existed before BUT without proof & (fundamental) understanding theory of pseudodifferential operators “invented” independently without proofs Combining these developments underlies the success of my research program Seismic wavefield reconstruction joint work with Gilles Hennenfent “Curvelet-based seismic data processing: a multiscale and nonlinear approach” to appear in Geophysics, “Non-parametric seismic data recovery with curvelet frames” & “Simply denoise: wavefield reconstruction via jittered undersampling” Seismic Laboratory for Imaging and Modeling Model spatial sampling: 12.5 m Seismic Laboratory for Imaging and Modeling avg. spatial sampling: 62.5 m Data 20% traces remaining Seismic Laboratory for Imaging and Modeling Interpolated result using CRSI* spatial sampling: 12.5 m SNR = 16.92 dB * CRSI: Curvelet Reconstruction with Sparsity-promoting Inversion Seismic Laboratory for Imaging and Modeling Difference spatial sampling: 12.5 m SNR = 16.92 dB Seismic Laboratory for Imaging and Modeling Problem statement Consider the following (severely) underdetermined system of linear equations Is it possible to recover x0 accurately from y? unknown data (measurements/ observations) x0 Ay = Seismic Laboratory for Imaging and Modeling Perfect recovery conditions – A obeys a type of uncertainty principle – x0 is sufficiently sparse procedure performance – S-sparse vectors recovered from roughly on the order of S measurements (to within constant and log factors) min x ‖x‖1 ︸ ︷︷ ︸ sparsity s.t. Ax = y ︸ ︷︷ ︸ perfect reconstruction x0 Ay = REFERENCES Bednar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Seismic migration. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematic , 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. Donoho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust modeling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Custom Computing Machines, IEEE, 207–216. Hennenfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- multiple separation with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation and deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- metricAnalysis, 7. Stoffa, P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migration: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 Seismic Laboratory for Imaging and Modeling Nonlinear wavefield sampling sparsifying transform – typically localized in the time-space domain to handle the complexity of seismic data – preserves edges/wavefronts advantageous coarse sampling – generates incoherent random undersampling “noise” in the sparsifying domain – does not create large gaps • because of the limited spatiotemporal extend of transform elements used for the reconstruction sparsity-promoting solver – requires few matrix-vector multiplications – scales to number of unknowns exceeding 230 (“small”) Seismic Laboratory for Imaging and Modeling Representations for seismic data curvelet transform – multi-scale: tiling of the FK domain into dyadic coronae – multi-directional: coronae sub-partitioned into angular wedges, # of angle doubles every other scale – anisotropic: parabolic scaling principle – local Transform Underlying assumption FK plane waves linear/parabolic Radon transform linear/parabolic events wavelet transform point-like events (1D singularities) curvelet transform curve-like events (2D singularities) k1 k2 angular wedge 2j 2j/2 Seismic Laboratory for Imaging and Modeling 3D curvelets ~2 j ~2 j/2 (1,α l ,β l ) ω1 ω2 ω3 (a) (b) Figure 3. 3D frequency tilings. (a) Schematic plot for the frequency tiling of continuous 3D curvelets. (b) Discrete frequency tiling. ω1, ω2 and ω3 are three axes of the frequency cube. Smooth frequency window eUj,! extracts the frequency content near the shaded wedge which has center slope (1,α!,β!). This frame of discrete curvelets has all the required properties of the continuous curvelet transform in Section 2. Figure 2(b) shows one typical curvelet in the spatial domain. To summarize, the algorithm of the 2D discrete curvelet transform is as follows: 1. Apply the 2D FFT and obtain Fourier samples f̂(ω1,ω2), −n/2 ≤ ω1,ω2 < n/2. 2. For each scale j and angle ", form the product Ũj,!(ω1,ω2)f̂(ω1,ω2). 3. Wrap this product around the origin and obtain W(Ũj,!f̂)(ω1,ω2), where the range for ω1 and ω2 is now −L1,j,!/2 ≤ ω1 < L1,j,!/2 and −L2,j,!/2 ≤ ω2 < L2,j,!/2. For j = j0 and je, no wrapping is required. 4. Apply a L1,j,!×L2,j,! inverse 2D FFT to each W(Ũj,!f̂), hence collecting the discrete coefficients cD(j, ", k). 4. 3D DISCRETE CURVELET TRANSFORM The 3D curvelet transform is expected to preserve the properties of the 2D transform. Most importantly, the frequency support of a 3D curvelet shall be localized near a wedge which follows the parabolic scaling property. One can prove that this implies that the 3D curvelet frame is a sparse basis for representing functions with surface- like singularities (which is of codimension one in 3D) but otherwise smooth. For the continuous transform, we window the frequency content as follows. The radial window smoothly extracts the frequency near the dyadic corona {2j−1 ≤ r ≤ 2j+1}, this is the same as the radial windowing used in 2D. For each scale j, the unit sphere S2 which represents all the directions in R3 is partitioned into O(2j/2 · 2j/2) = O(2j) smooth angular windows, each of which has a disk-like support with radius O(2−j/2), and the squares of which form a partition of unity on S2 (see Figure 3(a)). Like the 2D discrete transform, the 3D discrete curvelet transform takes as input a 3D Cartesian grid of the form f(n1, n2, n3), 0 ≤ n1, n2, n3 < n, and outputs a collection of coefficients cD(j, l, k) defined by cD(j, ", k) := ∑ n1,n2,n3 f(n1, n2, n3)ϕDj,!,k(n1, n2, n3) where j, " ∈ Z and k = (k1, k2, k3). Seismic Laboratory for Imaging and Modeling CRSIn reformulation of the problem Curvelet Reconstruction with Sparsity-promoting Inversion – look for the sparsest/most compressible, physical solution signal =y + n noise curvelet representation of ideal data PCH x0 (P0) x̃= arg sparsity constraint︷ ︸︸ ︷ min x ‖x‖0 s.t. ‖y−PC Hx‖2 ≤ ! f̃= CH x̃ (P1) x̃= argminx ‖Wx‖1 s.t. ‖y−PCHx‖2 ≤ ε f̃= CH x̃ (P0) x̃= arg sparsity constraint︷ ︸︸ ︷ min x ‖x‖0 s.t. data misfit︷ ︸︸ ︷ ‖y PCHx‖2 ! f̃= CH x̃ k1 k2 W2W2 f k KEY POINT OF THE RECOVERY Seismic Laboratory for Imaging and Modeling Nonlinear wavefield sampling sparsifying transform – typically localized in the time-space domain to handle the complexity of seismic data – preserves edges/wavefronts advantageous coarse sampling – generates incoherent random undersampling “noise” in the sparsifying domain – does not create large gaps • because of the limited spatiotemporal extend of transform elements used for the reconstruction sparsity-promoting solver – requires few matrix-vector multiplications – scales to number of unknowns exceeding 230 (“small”) Lustig et. al 2007 Seismic Laboratory for Imaging and Modeling Localized transform elements & gap size v v ✓ ✗ x̃ = arg min x ||x||1 s.t. y = Ax Seismic Laboratory for Imaging and Modeling Sampling Fourier transform ✓ ✗ 3-fold under-sampling significant coefficients detected ambiguity few significant coefficients Fourier transform Fourier transform Seismic Laboratory for Imaging and Modeling “noise” – due to AHA ≠ I – defined by AHAx0-αx0 = AHy-αx0 Undersampling “noise” less acquired data 3 detectable Fourier modes 2 detectable Fourier modes 1 out of 2 1 out of 4 1 out of 6 1 out of 8 D.L. Donoho et.al. ‘06 Seismic Laboratory for Imaging and Modeling Discrete random jittered undersampling receiver positions receiver positions PDF receiver positions PDF receiver positions PDF [Hennenfent and Herrmann ‘07] Typical spatial convolution kernel (amplitudes) Averaged spatial convolution kernel (amplitudes) Sampling schemeType po or ly jit ter ed op tim all y jit ter ed ra nd om re gu lar Seismic Laboratory for Imaging and Modeling Model Seismic Laboratory for Imaging and Modeling Regular 3-fold undersampling SNR = 12.98 dB Seismic Laboratory for Imaging and Modeling SNR = 12.98 dB Regular 3-fold undersampling Seismic Laboratory for Imaging and Modeling Optimally-jittered 3-fold undersampling SNR = 15.22 dB Seismic Laboratory for Imaging and Modeling Optimally-jittered 3-fold undersampling SNR = 15.22 dB Seismic Laboratory for Imaging and Modeling Data nominal spatial sampling ~ 112.5m Seismic Laboratory for Imaging and Modeling CRSI spatial sampling ~ 12.5m Seismic Laboratory for Imaging and Modeling Observations sparsity is a powerful property that offers striking benefits for signal reconstruction BUT it is not enough in the sparsifying domain, interpolation is a denoising problem – regular undersampling: harmful coherent undersampling “noise”, i.e., aliases – random & jittered undersamplings: harmless incoherent random undersampling “noise” nonlinear wavefield sampling – sparsifying transform: curvelet transform – coarse sampling scheme: jittered undersampling – sparsity-promoting solver: iterative soft thresholding with cooling open problem: optimal (non-random) sampling schemes, large- scale solvers & hard CS results for frames Seismic Laboratory for Imaging and Modeling observations continued CS ideas already existed in exploration seismology (Sacchi ‘98) New insights give solid proofs that – (hopefully) help convince management – engineers will do their implementations => innovation Results for seismic wavefield reconstruction – very encouraging – industry calls for commercialization/industrialization – looking into a startup Real-life implementation requires substantial investment – understanding the real problem & QC – infrastrcuture – solution that scales Real-life implementations require – parallelization of algorithms – massive IO – run on 10.000 CPU plus clusters ... Compressed wavefield extrapolation joint work with Tim Lin “Compressed wavefield extrapolation” in Geophysics Problem statement Goal: employ the 1-Way wavefield extrapolation based on factorization of the Helmholtz operator Problem: computation & storage complexity creating and storing is trivial however is not trivial to compute and store = e∓j∆xH1W± H1 H1 =H2 = H2 H2 = H1H1 REFERENCES Bednar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Seismic migration. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematics, 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. Donoho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edg s: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust modeling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Custom Computing Machines, IEEE, 207–216. Hennenfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- multiple separation with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation and deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- metricAnalysis, 7. Stoffa, P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migration: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 Modal domain In this case is computed by eigenvalue decomposition requires, per frequency: 1 eigenvalue problem (O(n4)) 2 full matrix-vector for eigenspace transform (O(n2)) W L Λ LT L LT W± = H2 = LΛLT = e−j √ Λ∆x3 Our approach Computation requires similar approach to However, for , , so computation trivial with FFT W± L Λ LT D = LΛLT = L LT S = D L = DFT e−j ∆x 2pi Λ Our approach Consider a related, but simpler problem: shifting (or translating) signal operator is is differential operator S = e−j ∆x 2pi D D D = restricted sampling signal in time domain restricted sampling signal in time domain signal in Fourier domain F restricted sampling signal in time domain signal in Fourier domain restricted signal in Fourier domain (real) F R restricted sampling signal in time domain signal in Fourier domain restricted signal in Fourier domain (real) recovered signal in time domain F L1 R signal in space domain signal in space domain F L1 shifted signal in Fourier domain incomplete and shifted signal in Fourier domain shifted signal in space domain Straightforward Computation Compressed Processing F shifted signal in space domain e−j ∆x 2pi Λ e−j ∆x 2pi ΛRF Compressed Sensing “Computation” In a nutshell: Trades the cost of L1 solvers for a compressed operator that is cheaper to compute, store, and synthesize L1 solver research is currently a hot topic in applied mathematics REFERENCES Bednar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Seismic migration. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematics, 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. Donoho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust modeling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Custom Computing Machines, IEEE, 207–216. Hennenfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- multiple separation with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation and deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- metricAnalysis, 7. Stoffa, P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migration: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 REFERENCES Bednar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Seismic migration. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematics, 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let tran forms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. Donoho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust modeling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Custom Computing Machines, IEEE, 207–216. Hennenfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- multiple separation with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation and deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- metricAnalysis, 7. Stoffa, P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migration: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 REFERENCES B dnar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style c mparison: 76th Annual I ternational Meeting, SEG, ExpandedAbstracts, 2343–2347. B rkhout, A. J., 1982, Seismic migration. Imag ng f acoustic energy by wave field xtrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British C lumbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematics, 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. D noho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery fro in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust m deling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. d Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Custom Computing Machines, IEEE, 207–216. Hennenfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- multiple separation with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation and deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- metricAnalysis, 7. Stoffa, P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migration: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 REFERENCES Bednar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Sei mic migration. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès E. J., and L. Demanet, 2005, The curvelet representation f wave propagators is ti ally arse: Comm nications on Pure and Applie Mathe atics, 58, 147 –1528. Ca dès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeli g nd Simulation, 5, 861–899. J., and D. L. Donoho, 2000a, Cu vele s —Asurprisingly effectiv nonadaptive representatio for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Pres . ——–, 2000b, Recovering edges in ill-posed problem : Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames f curvelets a d optim l representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Ca dès, E. J., D. L. Donoh , L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 197 , Robust modeling with erratic data: Geo- physics, 38, 826– 44. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Roussea , and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wave et transform approach to seismic processing: Ph.D. thesis, Delft University f Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- wa e: http://sparselab.sta ford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. El d, M., J. Starck, P. Querre, and D. Donoh , 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: G ophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Custom Computing Machines, IEEE, 207–216. Hen enfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Versc uur, 2007, Nonlinear primary- multiple sep ration with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. K m, and S. B yd, 2007, Simple matlab solver for 11-re ular- ized least squa es problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Ge physics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies i frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation an deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minim entropy dec nvolution with frequency-domain constraints: Geophysics, 59, 938–945. Sant sa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier i tegral operator : Journal of G o- metricAnalysis, 7. Stoffa, P. L. J. T Fokkema, R. M. e Luna Freire, and W. P. Kessi ger, 1990, Split-step Fourier migra ion: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J C Walker 1982 Analytic minimum entropy d convolu- tion: G ophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Confere ce Proceedings, 591413. Zwartjes, P., and A. isolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 REFERENCES Bednar, J. B., C. J. Bednar, and C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Seismic migration. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematics, 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. Donoho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communications On Pure andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust modeling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial approximations for the three-dimensional wave equation: SIAM Journal on Scientific Computing, 16, 1019–1048. Daubechies, I., M. Defrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for sparse reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wa enaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prospecting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 45 –1462. Discussion and reply by authors in GEO-58- -1 05-1206. He, C., M. Lu, and C. Sun, 2004, Accel ing seismic migration using FPGA-b sed coproces or platform: 12th Annual Symposium on Field- Progr mmabl Custom Computing Machines, IEEE, 207–216. Henn nfent, G., and F. J. Herrmann, 2006a, Application of stable signal re- c very to seismic i t rpolation: 76th Annual Internation l Meeting, SEG, ExpandedAbstracts, 2797–2801. ——–, 2006b, Seismic denoising with non-uniformly sampled curvelets: Computing in Science and Engineering, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- multiple separation with directional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~tibs/lasso.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- netotelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, How to choose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- national, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavelet estimation and deconvolution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- metricAnalysis, 7. Stoffa, P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migration: Geophysics, 55, 410–421. Taylor, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selection operator, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolation with curvelets SM93 REFERENCES Bednar, J. B., C. J. Bednar, a d C. Shin, 2006, Two-way versus one-way: A case study style comparison: 76th Annual International Meeting, SEG, ExpandedAbstracts, 2343–2347. Berkhout, A. J., 1982, Seismic migrati n. Imaging of acoustic energy by wave field extrapolation: Elsevier. Candès, E., 2007, Compressive sensing: Presented at the Institute of Applied Mathematics Seminars, University of British Columbia. Candès, E. J., and L. Demanet, 2005, The curvelet representation of wave propagators is optimally sparse: Communications on Pure and Applied Mathematics, 58, 1472–1528. Candès, E., L. Demanet, D. Donoho, and L. Ying, 2006a, Fast discrete curve- let transforms: SIAM Multiscale Modeling and Simulation, 5, 861–899. Candès, E. J., and D. L. Donoho, 2000a, Curvelets —Asurprisingly effective nonadaptive representation for objects with edges: in L. L. Schumaker et al., eds., Curves and surfaces: Vanderbilt University Press. ——–, 2000b, Recovering edges in ill-posed problems: Optimality of curve- let frames: Annals of Statistics, 30, 784–842. ——–, 2004, New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities: Communic tions On Pur andAp- plied Mathematics, 57, 219–266. Candès, E. J., D. L. Donoho, L. Demanet, and L. Ying, 2005, Fast discrete curvelet transform: http://www.curvelet.org/papers/FDCT.pdf. Candès, E. J., and J. Romberg, 2005, !1-magic. Software: http://www.acm. caltech.edu/limagic/. Candès, E., J. Romberg, and T. Tao, 2006b, Stable signal recovery from in- complete and inaccurate measurements: Communications On Pure and Applied Mathematics, 59, 1207–1223. Chauris, H., 2006, Seismic imaging in the curvelet domain and its implica- tions for the curvelet design: 76thAnnual International Meeting, SEG, Ex- pandedAbstracts, 2406–2410. Chen, S. S., D. L. Donoho, and M. A. Saunders, 2001, Atomic decomposition by basis pursuit: SIAM Journal on Scientific Computing, 43, 129–159. Claerbout, J. F., 1971, Toward a unified theory of reflector mapping: Geo- physics, 36, 467–481. Claerbout, J., and F. Muir, 1973, Robust modeling with erratic data: Geo- physics, 38, 826–844. Collino, F., and P. Joly, 1995, Splitting of operators, alternate directions, and paraxial a proximations for the three-dimensional wave equation: SI M Journal on Scientific Computing, 16, 1019–1048. Daubechies, I , M. efrise, and C. de Mol, 2005, An iterative thresholding al- gorithm for linear inverse problems with a sparsity constrains: Communi- cations On Pure andApplied Mathematics, 58, 1413–1457. de Hoop, M., J. L. Rousseau, and R.-S. Wu, 2000, Generalization of the phase-screen approximation f r the scattering of acoustic waves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavelet transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, Compressed sensing: IEEE Transactions on Informa- tion Theory, 52, 1289–1306. Donoho, D. L., I. Drori, V. Stodden, and Y. Tsaig, 2005, SparseLab, Soft- ware: http://sparselab.stanford.edu/. Douma, H., and M. de Hoop, 2006, Leading-order seismic imaging using curvelets: 76th Annual International Meeting, SEG, Expanded Abstracts, 2411–2415. Elad, M., J. Starck, P. Querre, and D. Donoho, 2005, Simultaneous cartoon and texture image inpainting using morphological component analysis !MCA": Applied and Computational HarmonicAnalysis, 19, 340–358. Figueiredo, M., and R. Nowak, 2003, An EM algorithm for wavelet-based image restoration: IEEE Transactions on Image Processing, 12, 906–916. Figueiredo, M., R. D. Nowak, and S. J. Wright, 2007, Gradient projection for spar e reconstruction, Software: http://www.lx.it.pt/~mtf/GPSR/. Grimbergen, J., F. Dessing, and C. Wapenaar, 1998, Modal expansion of one- way operator on laterally varying media: Geophysics, 63, 995–1005. Guitton, A., and D. J. Verschuur, 2004, Adaptive subtraction of multiples us- ing the !1-norm: Geophysical Prosp cting, 52, 27–27. Hale, D., N. R. Hill, and J. Stefani, 1992, Imaging salt with turning seismic waves: Geophysics, 57, 1453–1462. Discussion and reply by authors in GEO-58-8-1205-1206. He, C., M. Lu, and C. Sun, 2004, Accelerating seismic migration using FPGA-based coprocessor platform: 12th Annual Symposium on Field- Programmable Cust m C mputing Machines, IEEE, 207–216. Hennenf nt, G., and F. J. Herrmann, 2006a, Ap lication of stable signal re- covery to seismic interpolation: 76th Annual International Meeting, SEG, Expand Abstr cts, 2797–2801. ——–, 2006b, Seismic de oising with non-uniformly sampled curvelets: Co uting in Science nd Engine ring, 8, 16–25. Herrmann, F. J., U. Boeniger, and D. J. Verschuur, 2007, Nonlinear primary- m ltiple separation with d rectional curvelet frames: Geophysical Journal International, 17, 781–799. Koh, K., S. J. Kim, and S. Boyd, 2007, Simple matlab solver for 11-regular- ized least squares problems, Software: http://www-stat.stanford.edu/ ~ti s/la so.html. Levy, S., D. Oldenburg, and J. Wang, 1988, Subsurface imaging using mag- n totelluric data: Geophysics, 53, 104–117. Mulder, W., and R. Plessix, 2004, H w to ch ose a subset of frequencies in frequency-domain finite-difference migration: Geophysical Journal Inter- nati nal, 158, 801–812. Oldenburg, D. W., S. Levy, and K. P. Whittall, 1981, Wavel t estimati and deco volution: Geophysics, 46, 1528–1542. Paige, C. C., and M. A. Saunders, 1982, LSQR: An algorithm for sparse lin- ear equations and sparse least squares: Transactions on Mathematical Software, 8, 43–71. Plessix, R., and W. Mulder, 2004, Frequency-domain finite difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oosterlee, 2006, A new iterative solver for the time-harmonic wave equation: Geo- physics, 71, no. 5, E57–E63. Sacchi, M. D., T. J. Ulrych, and C. Walker, 1998, Interpolation and extrapola- tion using a high resolution discrete Fourier transform: IEEE Transactions on Signal Processing, 46, 31–38. Sacchi, M. D., D. R. Velis, and A. H. Cominguez, 1994, Minimum entropy deconvolution with frequency-domain constraints: Geophysics, 59, 938–945. Santosa, F., and W. Symes, 1986, Linear inversion of band-limited reflection seismogram: SIAM Journal of Scientific Computing, 7. Smith, H., 1997, Ahardy space for fourier integral operators: Journal of Geo- m tricAnalysis, 7. Stoffa P. L., J. T. Fokkema, R. M. de Luna Freire, and W. P. Kessinger, 1990, Split-step Fourier migr tion: Geophysics, 55, 410–421. Tayl r, H. L., S. Banks, and J. McCoy, 1979, Deconvolution with the !1 norm: Geophysics, 44, 39. Tibshirani, R., 1996, Least absolute shrinkage and selectio operat r, Soft- ware: http://www-stat.stanford.edu/~tibs/lasso.html. Tsaig, Y., and D. Donoho, 2006, Extensions of compressed sensing: Signal Processing, 86, 549–571. Ulrych, T. J., and C. Walker, 1982, Analytic minimum entropy deconvolu- tion: Geophysics, 47, 1295–1302. Ying, L., L. Demanet, and E. Candès, 2005, 3D discrete curvelet transform: Wavelets XI, SPIE, Conference Proceedings, 591413. Zwartjes, P., and A. Gisolf, 2006, Fourier reconstruction of marine-streamer data in four spatial coordinates: Geophysics, 71, no. 6, V171–V186. Compressed extrapolatio with curvelets SM93 wavefield in space-time domain L back-extrapolated wavefield in H2 domain Straightforward 1-Way inverse Wavefield Extrapolation Compressed 1-Way Wavefield Extrapolation L back-extrapolated to impulse source in space-time domain wavefield in space-time domain back-extrapolated to impulse source in space-time domain incomplete back-extrapolated wavefield in H2 domain e−j √ Λ∆x3LT e−j √ Λ∆x3RLT Compressed wavefield extrapolation Randomly subsample & phase rotation in Modal domain Recover by norm-one minimization Capitalize on the incoherence modal functions and point scatterers reduced explicit matrix size constant velocity <=> Fourier recovery y = RLHu A = RejΛ 1/2 ∆x3LH x̃ = arg minx ‖x‖1 s.t. Ax = y ṽ = x̃ 0 2 4 6 8 10 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 propagated 1.5km down Compressed wavefield extrapolation 0 2 4 6 8 10 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 recovered though L1 inverson simple 1-D space/time propagation example with point scatters Restricted L transform to ~0.01 of original coefficients Observations Compressed wavefield extrapolation reduction in synthesis cost mutual coherence curvelets and eigenmodes performance of norm-one solver keep the constants under control ... Open problems fast “random” eigensolver incoherence eigenfunctions and sparsity transform Double-role CS matrix is cool ... upscaling to “real-life” is a challenge .... DNOISE: an academic- industry-NSERC partnership DNOISE Felix J. Herrmann SLIM Michael Friedlander CS Ozgur Yilmaz Math IMA,IPAM BIRS,AIM BG BP Chevron Exxxon Mobil Shell Industry Industry consortia Since early 80’s in exploration seismology Consortia work on common set of problems No secret research Hurdles data access QC IT infrastructure University Liaison offices being interdisciplinary sounds easier than it is .. DNOISE DNOISE: Dynamic nonlinear optimization for imaging in seismic exploration NSERC Collaborative Research & Development Grant Matches SINBAD Consortium supported by industry organized by ITF (non-profit technology broker in the UK) supported by BG, BP, Chevron, ExxonMobil and Shell $70 k annually per company total budget $500-600 k annually Involves Dr. Michael Friedlander (CS) and Ozgur Yilmaz (Math) as co-PI’s 2-3 postdocs 8 graduate students 2 undergraduate students 2 programmers 1 part-time admin person Challenges Development of common language amongst Geophysics Computer Science Math Difference in mentality/approach Geophysicist throws everything at a problem and if it works ... it works Mathematicians/computer scientists narrow problem to proof theorems may not be relevant do not necessary understand what “deliverables” are do not speak the same language Knowledge dissemination Dissemination SPARCO: a test suite for norm-one problems framework for setting up small-size CS problems first step towards performance benchmarks www.cs.ubc.ca/labs/scl/sparco SLIMPy: “compiler” for abstract numerical algorithms operator overloading in Python integration with scalable seismic processing packages Madagascar: public-domain seismic processing package reproducible research slim.eos.ubc.ca/ rsf.sourceforge.nethyperlink Seismic Laboratory for Imaging and Modeling Nonlinear wavefield sampling sparsifying transform – typically localized in the time-space domain to handle the complexity of seismic data – preserves edges/wavefronts advantageous coarse sampling – generates incoherent random undersampling “noise” in the sparsifying domain – does not create large gaps • because of the limited spatiotemporal extend of transform elements used for the reconstruction sparsity-promoting solver – requires few matrix-vector multiplications – scales to number of unknowns exceeding 230 (“small”) SPARCO: Sparse Reconstruction Test Suite http://www.cs.ubc.ca/labs/scl/sparco Gaussian ensemble, spikes signal A = Gaussian b = 1200×5120 Candés, Romberg, & Tao ’05 Matrix-vector products Pareto curve 0 50 100 150 200 10 0 10 1 10 2 10 3 10 4 10 5 GPSR SPGL1 L1LS L1!Magic Sparselab 0 50 100 150 200 10 0 Pareto GPSR SPGL1 L1LS L1!Magic Sparselab one-norm x l2 norm residual one norm x # matrix vector products Seismic Laboratory for Imaging and Modeling Optimization paths Pareto curve SPGL1 ISTc Seismic Laboratory for Imaging and Modeling Madagascar Report/paper (SCons + LaTeX) Processing flow (SCons + Python) Program (C) Program (Fortran) Program (C++) Program (Python) Program (Mathematica) Program (Matlab) Report/paper (SCons + LaTeX) Book (SCons + LaTeX) Processing flow (SCons + Python) Processing flow (SCons + Python) D ocum entation (PD F & H TM L) Processing flow s Program (Delphi) Program (SU) Program (SEP) Seismic Laboratory for Imaging and Modeling Madagascar Report/paper (SCons + LaTeX) Processing flow (SCons + Python) Program (C) Program (Fortran) Program (C++) Program (Python) Program (Mathematica) Program (Matlab) Report/paper (SCons + LaTeX) Book (SCons + LaTeX) Processing flow (SCons + Python) Processing flow (SCons + Python) D ocum entation (PD F & H TM L) Processing flow s Program (Delphi) Program (SU) Program (SEP) SLIMpy app y = vector(‘data.rsf’) A1 = fdct2(domain=y.space).adj() A2 = fft2(domain=y.space).adj() A = aug_oper([A1, A2]) solver = GenThreshLandweber(10,5,thresh=None) x=solver.solve(A,y) Abstraction Let data be a vector y ∈ Rn. Let A1 := CT ∈ Cn×M be the inverse curvelet transform and A2 := FH ∈ Cn×n the inverse Fourier transform. Define A := [ A1 A2 ] and x = [ xT1 xT2 ]T Solve x̃ = arg min x ‖x‖1 s.t. ‖Ax− y‖2 ≤ ! Conclusions Math institutes have been instrumental exposure to the latest of the latest establish a research network Success research program depends on understanding the problems engineering & software development disseminate results (reproducible research) Science:Extension CS towards more general (nonlinear) problems compressive computations .... For the future: Redirection of emphasis away from “Let’s gather as much data as we can and let’s analyze it all” to “What are we looking for and how can we best sample....” Acknowledgments The audience for listening and the organizers for putting this great workshop together .... The authors of CurveLab (Demanet, Ying, Candes, Donoho) This work was in part financially supported by the Natural Sciences and Engineering Research Council of Canada Discovery Grant (22R81254) and the Collaborative Research and Development Grant DNOISE (334810-05) of F.J.H. This research was carried out as part of the SINBAD project with support, secured through ITF (the Industry Technology Facilitator), from the following organizations: BG Group, BP, Chevron,ExxonMobil and Shell.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Faculty Research and Publications /
- Seismology meets compressive sampling
Open Collections
UBC Faculty Research and Publications
Seismology meets compressive sampling Herrmann, Felix J. 2007
pdf
Page Metadata
Item Metadata
Title | Seismology meets compressive sampling |
Creator |
Herrmann, Felix J. |
Contributor | University of British Columbia. Seismic Laboratory for Imaging and Modeling |
Publisher | Institute for Pure & Applied Mathematics. University of California, Los Angeles. |
Date Issued | 2007 |
Description | Presented at Cyber-Enabled Discovery and Innovation: Knowledge Extraction as a success story lecture. See for more detail https://www.ipam.ucla.edu/programs/cdi2007/ |
Extent | 6017736 bytes |
Subject |
DNOISE pseudodifferential operators sparsity seismic wavefield reconstruction nonlinear sampling SPARCO Computer science Geophysics compressed wavefield extrapolation |
Genre |
Presentation |
Type |
Text Still Image |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-03-20 |
Provider | Vancouver : University of British Columbia Library |
Rights | All rights reserved |
DOI | 10.14288/1.0107423 |
URI | http://hdl.handle.net/2429/603 |
Affiliation |
Science, Faculty of Earth and Ocean Sciences, Department of |
Citation | Herrmann, Felix J. 2007. Seismology meets compressive sampling. Cyber-Enabled Discovery and Innovation: Knowledge Extraction. Institute for Pure & Applied Mathematics. University of California, Los Angeles. |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty |
Copyright Holder | Herrmann, Felix J. |
AggregatedSourceRepository | DSpace |
Download
- Media
- 52383-herrmann07Cyber.pdf [ 5.74MB ]
- Metadata
- JSON: 52383-1.0107423.json
- JSON-LD: 52383-1.0107423-ld.json
- RDF/XML (Pretty): 52383-1.0107423-rdf.xml
- RDF/JSON: 52383-1.0107423-rdf.json
- Turtle: 52383-1.0107423-turtle.txt
- N-Triples: 52383-1.0107423-rdf-ntriples.txt
- Original Record: 52383-1.0107423-source.json
- Full Text
- 52383-1.0107423-fulltext.txt
- Citation
- 52383-1.0107423.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.52383.1-0107423/manifest