Compressed Wavefield Extrapolation with Curvelets Tim T.Y. Lin and Felix J. Herrmann University of British Columbia SEG 2007 San Antonio, Sept 25 Introduction Concerned with explicit forms of wavefield propagator of the linearized forward model Would like to find explicit suitable for wave- equation migration: simultaneously operates on sets of traces fully incorporates velocity information of medium no parabolic approximations s+W- R+ W+P- x3 > 0 = ∑ ∆x3 W W Introduction Goal: employ the complete 1-Way Helmholtz operator for Problem: computation & storage complexity creating and storing is trivial however is not trivial to compute and store W = 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 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 Introduction 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 Introduction Band-diagonalization techniques like parabolic approximation trades for speed with approximations Is there another way? 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 = 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 Suppose FFT does not exist yet s(x) ... ... Fω=1,2,3,4,...s(k) Our approach suppose some nodes didn’t finish their jobs s(x) ... ... s(k) Fω=1,4,... Our approach mathematically, the system is incomplete evidently some information of original is invariably lost. Or is it? = s(x) Fω=1,4,... s(k) s(x) Compressed Sensing states that given system of the form measured signal =y sparse representation of original data x̃ = argmin x !x!1 = " i = 1 N #xi# s.t. Ax = y , $2% with the symbol ˜ hereby reserved for quantities obtained by solv- ing an optimization problem. The argminx stands for the argument of the minimum, i.e., the value of the given argument for which the val- ue of the expression attains its minimum value. This recovery is suc- cessful when the measurement and sparsity representations are inco- herent and when m is large enough compared to the number of non- zero entries in x0. Because m!N, this recovery involves the inver- sion of an underdetermined system.As long as the vector x0 is sparse enough, recovery according to equation 2 is successful. Typically, for Fourier measurements, five coefficients per nonzero entry are sufficient for full recovery !Candès, 2007". Instead of asking ourselves the question of how to recover x0 from incomplete data, suppose now that we ask ourselves how to apply an integer shift by ! to an arbitrary, but sparse, vector x0, without hav- ing to shift each single entry. Shifts translate to phase rotations in the Fourier domain and the Fourier basis functions !rows of the Fourier matrixF" are incoherent with the Dirac basis I. More formally, con- sider the approximate shift operation defined in terms of the expo- nentiation of the discrete difference matrix D!RM"M. In that case, the shift by ! can be written as u = e−D! v = Lej!!LHv , $3% where the decomposition matrix LH, with the symbol H denoting the Hermitian transpose, is derived from the eigenvalue problem D = L!LH. $4% In this expression, ! is a diagonal matrix with the eigenvalues # = diag$!% on its diagonal. These eigenvalues correspond to the an- gular frequencies, while the orthonormal !de"composition matrices LH, L correspond, when applying Neumann boundary conditions, to the forward and inverse discrete cosine transforms, respectively. The accuracy of this discrete approximation of the shift operator depends on the type and order of the finite-difference approximation in D. Be- cause the eigenvectors of the above shift operation correspond to the rows of the Fourier-like !discrete cosine" measurement matrix of the previously posed recovery problem, we can define an alternative compressed procedure for applying the shift by solving the follow- ing nonlinear optimization program: &y! = Rej!!Fv = RM!v ũ = argminu!u!1 s.t. Au = y! ', $5% in which we took the liberty to overload the symbolF with the dis- crete cosine transform. The input for this nonlinear program is given by the phase-rotated Fourier transform of v, restricted to a !small" random set of m frequencies. The symbol ! is hereby reserved for phase-rotated quantities. The shifted spike train is obtained by non- linear recovery of the phase-rotated measurement vector y. Instead of applying a full matrix-vector multiplication involving all tempo- ral frequency components as in equation 3, the shift according to the above program involves the repeated evaluation of the matrix A !Cm"N and its transpose. In the extreme case of a vector with a single nonzero entry for v, the matrix A will usually only need to be of size 5"N, leading to a significant reduction for the size of the matrix.An example of the above procedure is included in Figure 1 where five spikes with random positions and amplitudes in a vector of length N = 200 are circularly shifted by 20 samples. Comparison of the re- sults of applying the full shift operator !cf. equation 3" and the com- pressed shift operator according to equation 5 shows that these re- sults are identical. Only 15 random Fourier measurements were nec- essary for the recovery of the shifted spike train. Instead of applying a full 200"200 operator, application of the compressed operator of size 15"200 is sufficient. These results were calculated with the !1-solver of basis pursuit !BP" !Chen et al., 2001". The idea of norm-one sparsity-based recovery is not exactly new to the seismic imaging community. For instance, there exists a large body of literature on sparsity-promoting penalty functions. Since the seminal work of Claerbout and Muir !1973", norm-one regularized inversion problems have been prevalent in the formulation of geo- physical inverse problems with applications including deconvolu- tion !Taylor et al., 1979; Oldenburg et al., 1981; Ulrych and Walker, 1982; Santosa and Symes, 1986; Levy et al., 1988; Sacchi et al., 1994", filtering and seismic data regularization based on high-reso- lution Fourier !Sacchi et al., 1998; Zwartjes and Gisolf, 2006", cur- velet transforms !see e.g. Hennenfent and Herrmann, 2006a", non- parametric seismic data recovery !F. J. Herrmann and G. Hennen- fent, personal communication, 2007", adaptive subtraction for mul- tiple attenuation !Guitton and Verschuur, 2004; Herrmann et al., 2007", and Bayesian approaches with priors consisting of long- tailed Cauchy distributions !Sacchi and Ulrych, 1996". What is new in compressed sensing is the insight into the criteria of successful recovery. For example, compressed sensing looks for the existence of a transform that compresses the !inverse" extrapolat- ed wavefield and is incoherent with the measurement basis. In that case, the wavefield can be recovered from a relatively small subset of measurements. We leverage these new insights toward the formula- tion of the !inverse" wavefield extrapolation problem by identifying the eigenfunctions of the modal transform !Grimbergen et al., 1998" as the measuring basis and curvelet frames !Candès and Donoho, a) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 b) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 c) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 Figure 1. Example of compressed shifting of length 200 with five ar- bitrary spikes. !a" The five spikes. !b" Shifted spikes by 20 samples according to equation 3. !c" The same, but according to the com- pressed program of equation 5. Notice that there is virtually no dif- ference. SM78 Lin and Herrmann x̃ = argmin x !x!1 = " i = 1 N #xi# s.t. Ax = y , $2% with the symbol ˜ hereby reserved for quantities obtained by solv- ing an optimization problem. The argminx stands for the argument o the minimum, i.e., the value of the given argument for which the val- ue of he expression attains its minimum value. This recovery is suc- cessful when the measurement and sparsity representations are inco- herent and when m is large enough compared to the number of non- zero entries in x0. Because m!N, th s recovery involves the inver- sion of an underdetermined system.As long as the vector x0 is sparse enough, recovery according to equation 2 is successful. Typically, for Fourier measurements, five coefficients per nonzero entry are sufficient for full recovery !Candès, 2007". Instead of asking ourselves the question of how to recover x0 from incomplete data, suppose now that we ask ourselves how to apply an integer shift by ! to an arbitrary, but sparse, vector x0, without hav- ing to shift each single entry. Shifts translate to phase rotations in the Fourier domain and the Fourier basis functions !rows of he Fourier matrixF" are incoherent with the Dirac basis I. More formally, con- sider the approximate shift operation defined in terms of the expo- nentiation of the discrete difference matrix D!RM"M. In that case, the shift by ! can be written as u = e−D! v = Lej!!LHv , $3% where the decomposition matrix LH, with the symbol H denoting the Hermitian transpose, is derived from the eigenvalue problem D = L!LH. $4% In this expression, ! is a diagonal matrix with the eigenvalues # = diag$!% on its diagonal. These eigenvalues correspond to the an- gular frequencies, while the orthonormal !de"composition matrices LH, L correspond, when applying Neumann boundary conditions, to the forward nd inverse discret cosine transforms, respectively. The accuracy of this discrete approximation of the shift operator depends on the type and order of the finite-difference approximation in D. Be- cause the eigenvectors of the above shift operation correspond to the rows of the Fourier-like !discrete cosine" measurement matrix of the previously pos d recovery problem, we can define an alternative compressed procedure for applying the shift by solving the follow- ing nonlinear optimization program: &y! = Rej!!Fv = RM!v ũ = argminu!u!1 s.t. Au = y! ', $5% in which we took the liberty to overload the symbolF with the dis- crete cosine transform. The input for this nonlinear program is given by the phase-rotated Fourier transform of v, restricted to a !small" random set of m frequencies. The symbol ! is hereby reserved for phase-rotated quantities. The shifted pike train is obtained by non- linear recovery of the phase-rotated measurement vector y. Instead of applying a full matrix-vector multiplication involving all tempo- ral frequency components as in equation 3, the shift according to the above program involves the repeated evaluation of the matrix A !Cm"N and its t anspose. In the extreme case of a vector with a single nonzero entry for v, the matrix A will usually only need to be of size 5"N, leading to a significant reduction for the size of the matrix.An example of the above procedure is included in Figure 1 where five spikes with random positions and amplitudes in a vector of length N = 200 are circularly shifted by 20 s mples. Comparison of the re- sults of applying the full shift operator !cf. equation 3" and the com- pressed shift operator according to equation 5 shows that these re- sults are identical. Only 15 random Fourier measurements were nec- essary for the recovery of the shifted spike train. Instead of applying a full 200"200 operator, application of t e compressed operator of size 15"200 is sufficient. These results were calculated with the !1-solver of basis pursuit !BP" !Chen et al., 2001". The idea of norm-one sparsity-based recovery is not exactly new to the seismic imaging community. For instance, there exists a large body of literature on sparsity-promoting penalty functions. Since the seminal work of Claerbout and Muir !1973", norm-one regularized inversion problems have been prevalent in the formulation of geo- physical inverse problems with applications including deconvolu- tion !Taylor et al., 1979; Oldenburg et al., 1981; Ulrych and Walker, 1982; Santosa and Symes, 1986; Levy et al., 1988; Sacchi et al., 1994", filtering and seismic data regu arization based on high-reso- lution Fourier !Sacchi et al., 1998; Zwartjes and Gisolf, 2006", cur- velet transforms !see e.g. Hennenfent and Herrmann, 2006a", non- parametric seismic data recovery !F. J. Herrmann and G. Hennen- fent, personal communication, 2007", adaptive subtraction for mul- tipl attenuation !Guitton and Verschuur, 2004; Herrmann et al., 2007", and Bayesian approaches with priors consisting of long- tailed Cauchy distributions !Sacchi and Ulrych, 1996". What is new in compressed sensing is the insight into the criteria of successful recovery. For example, compressed sensing looks for the existence of a transform that compresses the !inverse" extrapolat- ed wavefield and is incoherent with the measurement basis. In that case, the wavefield can be recovered from a relatively small subset of measurements. We leverage these new insights toward the formula- tion of the !inverse" wavefield extrapolation problem by identifying the eigenfunctions of the modal transform !Grimbergen et al., 1998" as the meas ing basis and curvelet frames !Candès and Donoho, a) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 b) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 c) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 Figure 1. Example of compressed shifting of length 200 with five ar- bitrary spikes. !a" The five spikes. !b" Shifted spikes by 20 samples according to equation 3. !c" The same, but according to the com- pressed program of equation 5. Notice that there is virtually no dif- ference. SM78 Lin and Herrmann linear model of restricted measurement process (measurement basis) Compressed Sensing states that given system of the form can exactly “recover” x from y by solving L1 problem measured signal =y sparse representation of original data x̃ = argmin x !x!1 = " i = 1 N #xi# s.t. Ax = y , $2% with the symbol ˜ hereby reserved for quantities obtained by solv- ing an optimization problem. The argminx stands for the argument of the minimum, i.e., the value of the given argument for which the val- ue of the expression attains its minimum value. This recovery is suc- cessful when the measurement and sparsity representations are inco- herent and when m is large enough compared to the number of non- zero entries in x0. Because m!N, this recovery involves the inver- sion of an underdetermined system.As long as the vector x0 is sparse enough, recovery according to equation 2 is successful. Typically, for Fourier measurements, five coefficients per nonzero entry are sufficient for full recovery !Candès, 2007". Instead of asking ourselves the question of how to recover x0 from incomplete data, suppose now that we ask ourselves how to apply an integer shift by ! to an arbitrary, but sparse, vector x0, without hav- ing to shift each single entry. Shifts translate to phase rotations in the Fourier domain and the Fourier basis functions !rows of the Fourier matrixF" are incoherent with the Dirac basis I. More formally, con- sider the approximate shift operation defined in terms of the expo- nentiation of the discrete difference matrix D!RM"M. In that case, the shift by ! can be written as u = e−D! v = Lej!!LHv , $3% where the decomposition matrix LH, with the symbol H denoting the Hermitian transpose, is derived from the eigenvalue problem D = L!LH. $4% In this expression, ! is a diagonal matrix with the eigenvalues # = diag$!% on its diagonal. These eigenvalues correspond to the an- gular frequencies, while the orthonormal !de"composition matrices LH, L correspond, when applying Neumann boundary conditions, to the forward and inverse discrete cosine transforms, respectively. The accuracy of this discrete approximation of the shift operator depends on the type and order of the finite-difference approximation in D. Be- cause the eigenvectors of the above shift operation correspond to the rows of the Fourier-like !discrete cosine" measurement matrix of the previously posed recovery problem, we can define an alternative compressed procedure for applying the shift by solving the follow- ing nonlinear optimization program: &y! = Rej!!Fv = RM!v ũ = argminu!u!1 s.t. Au = y! ', $5% in which we took the liberty to overload the symbolF with the dis- crete cosine transform. The input for this nonlinear program is given by the phase-rotated Fourier transform of v, restricted to a !small" random set of m frequencies. The symbol ! is hereby reserved for phase-rotated quantities. The shifted spike train is obtained by non- linear recovery of the phase-rotated measurement vector y. Instead of applying a full matrix-vector multiplication involving all tempo- ral frequency components as in equation 3, the shift according to the above program involves the repeated evaluation of the matrix A !Cm"N and its transpose. In the extreme case of a vector with a single nonzero entry for v, the matrix A will usually only need to be of size 5"N, leading to a significant reduction for the size of the matrix.An example of the above procedure is included in Figure 1 where five spikes with random positions and amplitudes in a vector of length N = 200 are circularly shifted by 20 samples. Comparison of the re- sults of applying the full shift operator !cf. equation 3" and the com- pressed shift operator according to equation 5 shows that these re- sults are identical. Only 15 random Fourier measurements were nec- essary for the recovery of the shifted spike train. Instead of applying a full 200"200 operator, application of the compressed operator of size 15"200 is sufficient. These results were calculated with the !1-solver of basis pursuit !BP" !Chen et al., 2001". The idea of norm-one sparsity-based recovery is not exactly new to the seismic imaging community. For instance, there exists a large body of literature on sparsity-promoting penalty functions. Since the seminal work of Claerbout and Muir !1973", norm-one regularized inversion problems have been prevalent in the formulation of geo- physical inverse problems with applications including deconvolu- tion !Taylor et al., 1979; Oldenburg et al., 1981; Ulrych and Walker, 1982; Santosa and Symes, 1986; Levy et al., 1988; Sacchi et al., 1994", filtering and seismic data regularization based on high-reso- lution Fourier !Sacchi et al., 1998; Zwartjes and Gisolf, 2006", cur- velet transforms !see e.g. Hennenfent and Herrmann, 2006a", non- parametric seismic data recovery !F. J. Herrmann and G. Hennen- fent, personal communication, 2007", adaptive subtraction for mul- tiple attenuation !Guitton and Verschuur, 2004; Herrmann et al., 2007", and Bayesian approaches with priors consisting of long- tailed Cauchy distributions !Sacchi and Ulrych, 1996". What is new in compressed sensing is the insight into the criteria of successful recovery. For example, compressed sensing looks for the existence of a transform that compresses the !inverse" extrapolat- ed wavefield and is incoherent with the measurement basis. In that case, the wavefield can be recovered from a relatively small subset of measurements. We leverage these new insights toward the formula- tion of the !inverse" wavefield extrapolation problem by identifying the eigenfunctions of the modal transform !Grimbergen et al., 1998" as the measuring basis and curvelet frames !Candès and Donoho, a) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 b) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 c) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 Figure 1. Example of compressed shifting of length 200 with five ar- bitrary spikes. !a" The five spikes. !b" Shifted spikes by 20 samples according to equation 3. !c" The same, but according to the com- pressed program of equation 5. Notice that there is virtually no dif- ference. SM78 Lin and Herrmann x̃ = argmin x !x!1 = " i = 1 N #xi# s.t. Ax = y , $2% with the symbol ˜ hereby reserved for quantities obtained by solv- ing an optimization problem. The argminx stands for the argument o the minimum, i.e., the value of the given argument for which the val- ue of he expression attains its minimum value. This recovery is suc- cessful when the measurement and sparsity representations are inco- herent and when m is large enough compared to the number of non- zero entries in x0. Because m!N, th s recovery involves the inver- sion of an underdetermined system.As long as the vector x0 is sparse enough, recovery according to equation 2 is successful. Typically, for Fourier measurements, five coefficients per nonzero entry are sufficient for full recovery !Candès, 2007". Instead of asking ourselves the question of how to recover x0 from incomplete data, suppose now that we ask ourselves how to apply an integer shift by ! to an arbitrary, but sparse, vector x0, without hav- ing to shift each single entry. Shifts translate to phase rotations in the Fourier domain and the Fourier basis functions !rows of he Fourier matrixF" are incoherent with the Dirac basis I. More formally, con- sider the approximate shift operation defined in terms of the expo- nentiation of the discrete difference matrix D!RM"M. In that case, the shift by ! can be written as u = e−D! v = Lej!!LHv , $3% where the decomposition matrix LH, with the symbol H denoting the Hermitian transpose, is derived from the eigenvalue problem D = L!LH. $4% In this expression, ! is a diagonal matrix with the eigenvalues # = diag$!% on its diagonal. These eigenvalues correspond to the an- gular frequencies, while the orthonormal !de"composition matrices LH, L correspond, when applying Neumann boundary conditions, to the forward nd inverse discret cosine transforms, respectively. The accuracy of this discrete approximation of the shift operator depends on the type and order of the finite-difference approximation in D. Be- cause the eigenvectors of the above shift operation correspond to the rows of the Fourier-like !discrete cosine" measurement matrix of the previously pos d recovery problem, we can define an alternative compressed procedure for applying the shift by solving the follow- ing nonlinear optimization program: &y! = Rej!!Fv = RM!v ũ = argminu!u!1 s.t. Au = y! ', $5% in which we took the liberty to overload the symbolF with the dis- crete cosine transform. The input for this nonlinear program is given by the phase-rotated Fourier transform of v, restricted to a !small" random set of m frequencies. The symbol ! is hereby reserved for phase-rotated quantities. The shifted pike train is obtained by non- linear recovery of the phase-rotated measurement vector y. Instead of applying a full matrix-vector multiplication involving all tempo- ral frequency components as in equation 3, the shift according to the above program involves the repeated evaluation of the matrix A !Cm"N and its t anspose. In the extreme case of a vector with a single nonzero entry for v, the matrix A will usually only need to be of size 5"N, leading to a significant reduction for the size of the matrix.An example of the above procedure is included in Figure 1 where five spikes with random positions and amplitudes in a vector of length N = 200 are circularly shifted by 20 s mples. Comparison of the re- sults of applying the full shift operator !cf. equation 3" and the com- pressed shift operator according to equation 5 shows that these re- sults are identical. Only 15 random Fourier measurements were nec- essary for the recovery of the shifted spike train. Instead of applying a full 200"200 operator, application of t e compressed operator of size 15"200 is sufficient. These results were calculated with the !1-solver of basis pursuit !BP" !Chen et al., 2001". The idea of norm-one sparsity-based recovery is not exactly new to the seismic imaging community. For instance, there exists a large body of literature on sparsity-promoting penalty functions. Since the seminal work of Claerbout and Muir !1973", norm-one regularized inversion problems have been prevalent in the formulation of geo- physical inverse problems with applications including deconvolu- tion !Taylor et al., 1979; Oldenburg et al., 1981; Ulrych and Walker, 1982; Santosa and Symes, 1986; Levy et al., 1988; Sacchi et al., 1994", filtering and seismic data regu arization based on high-reso- lution Fourier !Sacchi et al., 1998; Zwartjes and Gisolf, 2006", cur- velet transforms !see e.g. Hennenfent and Herrmann, 2006a", non- parametric seismic data recovery !F. J. Herrmann and G. Hennen- fent, personal communication, 2007", adaptive subtraction for mul- tipl attenuation !Guitton and Verschuur, 2004; Herrmann et al., 2007", and Bayesian approaches with priors consisting of long- tailed Cauchy distributions !Sacchi and Ulrych, 1996". What is new in compressed sensing is the insight into the criteria of successful recovery. For example, compressed sensing looks for the existence of a transform that compresses the !inverse" extrapolat- ed wavefield and is incoherent with the measurement basis. In that case, the wavefield can be recovered from a relatively small subset of measurements. We leverage these new insights toward the formula- tion of the !inverse" wavefield extrapolation problem by identifying the eigenfunctions of the modal transform !Grimbergen et al., 1998" as the meas ing basis and curvelet frames !Candès and Donoho, a) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 b) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 c) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 Figure 1. Example of compressed shifting of length 200 with five ar- bitrary spikes. !a" The five spikes. !b" Shifted spikes by 20 samples according to equation 3. !c" The same, but according to the com- pressed program of equation 5. Notice that there is virtually no dif- ference. SM78 Lin and Herrmann linear model of restricted measurement process (measurement basis) x̃ = argmin x !x!1 = " i = 1 N #xi# s.t. Ax = y , $2% with the symbol ˜ hereby reserved for quantities obtained by solv- ing an optimization problem. The argminx stands for the argument of the minimum, i.e., the value of the given argument for which the al- ue of the expression attains its minimum value. This recovery is suc- cessful when the measurement and sparsity representations are inco- herent and when m is large enough compared to the number of non- zero entries in x0. Because m!N, this recovery involves the inver- sion of an underdetermined system.As long as the vector x0 is sparse enough, recovery according to equation 2 is successful. Typically, for Fourier measurements, five coefficients per nonzero entry are sufficient for full recovery !Candès, 2007". Instead of asking ourselves the question of how to recover x0 from incomplete data, suppose now that we ask ourselves how to apply an integer shift by ! to an arbitrary, but sparse, vector x0, without hav- ing to shift each single entry. Shifts translate to phase rotatio s in the Fourier domain and the Fourier basis functions !rows of the Fourier matrixF" are incoherent with the Dirac basis I. More formally, con- sider the approximate shift operation defined in terms of the expo- nentiation of the discrete difference matrix D!RM"M. In that case, the shift by ! can be written as u = e−D! v = Lej!!LHv , $3% where the decomposition matrix LH, with the symbol H denoting the Hermitian transpose, is derived from the eigenvalue problem D = L!LH. $4% In this expression, ! is a diagonal matrix with the eigenvalues # = diag$!% on its diagonal. These eigenvalues correspond to the an- gular frequencies, while the orthonormal !de"composition matrices LH, L correspond, when applying Neumann bou dary conditions, to the forward and inverse discrete cosine transforms, respectively. The accuracy of this discre e approximation of the shift operator depends on the type and order of the finite-difference approximation in D. Be- cause the eigenvectors of the above shift operation correspond to the rows of the Fourier-like !discrete cosine" measurement matrix of the previously posed recovery problem, we can define an alternative compressed procedure for applying the shift by solving the follow- ng n nlinear optimization program: &y! = Rej!!Fv = RM!v ũ = argminu!u!1 s.t. Au = y! ', $5% in which we took the liberty to overload the symbolF with the dis- crete cosine transfor . Th input for this nonlin ar program is given by the phase-rotated Fourier transform of v, restricted to a !small" random set of m frequencies. The symbol ! is hereby reserved for phase-rotated quantities. T e shifted spike train is obtained by non- linear recovery of the phase-rotated measurement vector y. Instead of applying a full matrix-vector multiplication involving all tempo- ral f quency components as in equation 3, th shift according o the above program involves the repeated evaluation of the matrix A !Cm"N and its transpose. In the extreme case of a vector with a single nonzero entry for v, the matrix A will usually only need to be of size 5"N, leading to a significant reduction for the size of the matrix.An example of the above procedure is included in Figure 1 where five spikes with random positions and amplitudes in a vector of length N = 200 are circularly shifted by 20 samples. Comparison of the re- sults of applying the full shift operator !cf. equation 3" and th m- pressed shif operator according to equation 5 shows that these re- sults are identical. Only 15 random Fourier measurements were nec- essary for the recovery of the shifted spike train. Instead of applying a full 200"200 operator, application of he compressed operator of size 15"200 is sufficient. These results were calculated with the !1-solver of basis pursuit !BP" !Chen et al., 2001". The idea of norm-one sparsity-based recovery is not exactly n w to the seismic imaging community. For instance, there exists a large body of literature on sparsity-promoting penalty functions. Since the seminal work of Claerbout and Muir !1973", norm-one regularized inversion problems have been prevalent in the formulation of geo- physical inverse problems with applications i cluding deconvolu- tion !Taylor et al., 1979; Oldenburg et al., 1981; Ulrych and Walker, 1982; Santosa and Symes, 1986; Levy et al., 1988; Sacchi et al., 1994", filtering and seismic data regularization based on high-reso- lution Fourier !Sacchi et al., 1998; Zwartjes and Gisolf, 2006", cur- velet transforms !see e.g. Hennenfent and Herrmann, 2006a", non- parametric seismic data recovery !F. J. Herrm nn and G. Hennen- f nt, personal communication, 2007", adaptive subtraction for mul- tiple attenuation !Guitton and Verschuur, 2004; Herrmann et al., 2007", and Bayesian approaches with priors consisting of long- tailed Cauchy distributions !Sacchi and Ulrych, 1996". What is new in compressed sensing is the insight into the crite ia of successful recovery. For example, compressed sensing looks for the existence of a transform that compresses the !inverse" extrapolat- ed wavefield and is incoherent with the measurement basis. In that case, the wavefield can be recovered from a relatively small subset of measurements. We leverage these new insights toward the formula- tion of the !inverse" wavefield extrapolation problem by identifying the eigenfunctions of the modal transform !Grimbergen et al., 1998" as the measuring basis and curvelet frames !Candès and Donoho, a) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 b) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 c) 1.0 0.8 0.6 0.4 0.2 0 Am pl itu de 200 150 100 Time index 50 0 Figure 1. Example of compressed shifting of length 200 with five ar- bitrary spikes. !a" The five spikes. !b" Shifted spikes by 20 samples according to equation 3. !c" The same, but according to the com- pressed program of equation 5. Notice that there is virtually no dif- ference. SM78 Lin and Herrmann 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 Pr ss. ——–, 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 li ear inver e 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 aves: Wave Motion, 31, 43–70. Dessing, F. J., 1997, A wavel t transform approach to seismic processing: Ph.D. thesis, Delft University of Technology. Donoho, D. L., 2006, C mpressed 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 Tra sactions 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 olver fo 11-regular- ized least squares problems, Software: http://www-stat.stanfo d. du/ ~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 fin t difference ampli- tude-preserving migration: Geophysical Journal International, 157, 975–987. Riyanti, C., Y. Eriangga, R. Plessix, W. Mulder, C. Vulk, and C. Oo t rlee, 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 sei mogram: SIAM Journal of Scientific Computi g, 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 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 Compressed Sensing x has to be sparse A has to be Fourier transform Compressed sensing theory gives us strict bounds on regions of recoverability Enables deliberate incomplete computations Compressed Sensing “Computation” if we “shift” s(k) with , what happens when we recover s(x) using s’(k)? = s(x) Fω=1,4,... s′(k) = s(k)s(k)e−j ∆x 2pi Λ e−j ∆x 2pi Λ Compressed Sensing “Computation” if we “shift” s(k) with , what happens when we recover s(x) using s’(k)? Answer: we recover a shifted s(x)! = s(x) Fω=1,4,... s′(k) = s(k)s(k)e−j ∆x 2pi Λ e−j ∆x 2pi Λ signal in space domain signal in space domain F R L1 L1 incomplete signal in Fourier domain incomplete and shifted signal in Fourier domain shifted signal in space domain signal in space domain Compressed Sensing Compressed Processing e−j ∆x 2pi Λe j x 2piRF 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 deconv lution wi h 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 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 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. Bed ar, and C. Shin, 2006, Two-way v rsus 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 opti ally parse: Comm nications on Pure and Applied Mathematics, 58, 147 –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. 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, Rec vering 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 mappi g: Geo- physics, 36, 467–481. Clae bout, J., and F. Muir, 197 , 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, 10 –1048. Daubechies, I., M. D frise, a d C. d Mol, 2005, An iterative thresholding al- gorithm for lin ar inverse problems with a sparsity constrains: C mmuni- ations On Pure andApplied Mathematics, 58, 14 3–1457. de Hoop, M., J. L. Rouss a , and R.-S. Wu, 2000, Generalization of the phase-screen approximation for the scattering of acoustic waves: Wave M tion, 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.stanford.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 in freque cy-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, Minim entropy dec nvolution with frequency-domain con traints: 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 i tegral operators: Journal of G o- metricAnalysis, 7. Stoffa, P. L. J. T Fokkema, R. M. e Luna F eire, 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: Si nal 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 reco struction, 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, 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 polation: 76th Annual Internation l Meeting, SEG, ExpandedAbstr cts, 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. S in, 2006, Tw -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: 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 approximations 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. Stefan , 1992, Imaging salt with turning seismic waves: G ophysics, 57, 1453–1462. Discussion nd reply by authors in GEO-58-8-1205-1206. H , 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. Hennenfent, 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: C 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 Compressed Wavefield Extrapolation Recall the similarity between andW± S L LT W± = S = e−j ∆x 2pi ΛF FT D = e−j √ Λ∆x3 H2 = Compressed Wavefield Extrapolation Structure of analytically discretely H2 = H1H1 H1 H2 = C+D2 H2 = ( ω c1 )2 0 · · · 0 0 ( ω c2 )2 · · · 0 ... ... . . . ... 0 0 · · · ( ω cn1 )2 +D2 H2 = k2(x) + ∂µ∂µ H2 = LΛLT H1 = LΛ1/2LT 0 5 10 15 20 25 Eigenvalue Index Compressed Wavefield extrapolation Asymptotically identical to the Cosine transform eigenfunctions of at 30 Hz for constant velocity mediumH2 0 50 100 150 200 250 2400 2600 2800 3000 3200 3400 3600 3800 4000 4200 4400 Position Index W av e V elo civ ty (m /s) Compressed Wavefield extrapolation eigenfunctions of at 30 Hz for Marmousi velocity mediumH2 0 5 10 15 20 25 Eigenvalue Index Compressed Wavefield extrapolation fairly close to the Cosine transform eigenfunctions of at 30 Hz for Marmousi velocity mediumH2 wavefield in space-time domain L1 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 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 Compressed wavefield extrapolation 2400 3200 4000 simple 1-D space/time propagation example with point scatters 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 Sparsity through curvelets for extrapolation to reflectivity, we first transform signal into a sparsifies reflectivity we know reflectivity are sparse in curvelets 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 Example (Canadian overthrust) original reflectivity downward extrapolated 50m inverse extrapolated explicitly Example (Canadian overthrust) inverse extrapolated explicitly inverse extrapolated with compressed computation ~15% coefficients used Discussions Bottom line: synthesis, operation, and storage cost savings versus L1-solver cost require good sparsity-promoting basis (ie Curvelets) potential to apply same technique to a variety of different operators Conclusions 1) Take linear operator with suitable structure for compressed sensing, having a diagonalizing basis which is incoherent with the signal basis 2) Compressed sensing theory tells us how much computation we can throw away while still recovering full signal with L1 solver 3) Then we can take advantage of results in compressed sampling for compressed computation Take home point: Exploit compressed sensing theory for gains in scientific computation Still awake? Check-out the full paper at: Lin, T.T.Y. and F. Herrmann, 2007, Compressed wavefield extrapolation: Geophysics, 72, SM77-SM93 Compressed wavefield extrapolation Randomly subsample in the Modal domain Recover by norm-one minimization Capitalize on the incoherence between modal functions and impulse sources reduced explicit matrix size y = Re−jω √ Λ∆x3LTu x̃ = arg minx ‖x‖1 s.t. RLTx = y ũ′ = x̃ Compressed wavefield extrapolation with curvelets Original and reconstructed signals remain in the curvelet domain Original curvelet transform must be done outside of the algorithm y = Re−jω √ Λ∆x3LTCTu x̃ = arg minx ‖x‖1 s.t. RLTCTx = y ũ′ = x̃
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Faculty Research and Publications /
- Compressed wavefield extrapolation with curvelets
Open Collections
UBC Faculty Research and Publications
Compressed wavefield extrapolation with curvelets Lin, Tim T. Y.; Herrmann, Felix J. 2007
pdf
Page Metadata
Item Metadata
Title | Compressed wavefield extrapolation with curvelets |
Creator |
Lin, Tim T. Y. Herrmann, Felix J. |
Contributor | University of British Columbia. Seismic Laboratory for Imaging and Modeling |
Publisher | Society of Exploration Geophysicists |
Date Issued | 2007 |
Description | An \emph {explicit} algorithm for the extrapolation of one-way wavefields is proposed which combines recent developments in information theory and theoretical signal processing with the physics of wave propagation. Because of excessive memory requirements, explicit formulations for wave propagation have proven to be a challenge in {3-D}. By using ideas from ``\emph{compressed sensing}'', we are able to formulate the (inverse) wavefield extrapolation problem on small subsets of the data volume{,} thereby reducing the size of the operators. According {to} compressed sensing theory, signals can successfully be recovered from an imcomplete set of measurements when the measurement basis is \emph{incoherent} with the representation in which the wavefield is sparse. In this new approach, the eigenfunctions of the Helmholtz operator are recognized as a basis that is incoherent with curvelets that are known to compress seismic wavefields. By casting the wavefield extrapolation problem in this framework, wavefields can successfully be extrapolated in the modal domain via a computationally cheaper operatoion. A proof of principle for the ``compressed sensing'' method is given for wavefield extrapolation in {2-D}. The results show that our method is stable and produces identical results compared to the direct application of the full extrapolation operator. |
Extent | 2684048 bytes |
Subject |
Helmholtz operator compressed sensing wavefield extrapolation eigenfunctions curvelets incoherent compressed processing compressed wavefield extrapolation |
Genre |
Conference Paper |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-03-20 |
Provider | Vancouver : University of British Columbia Library |
Rights | All rights reserved |
DOI | 10.14288/1.0107427 |
URI | http://hdl.handle.net/2429/607 |
Affiliation |
Science, Faculty of Earth and Ocean Sciences, Department of |
Citation | Herrmann, Felix J., Lin, Tim T.Y. 2007. Compressed wavefield extrapolation with curvelets. SEG 77th Annual Meeting and Exposition. |
Peer Review Status | Unreviewed |
Scholarly Level | Graduate Faculty |
Copyright Holder | Herrmann, Felix J. |
Aggregated Source Repository | DSpace |
Download
- Media
- 52383-lin07SEG.pdf [ 2.56MB ]
- Metadata
- JSON: 52383-1.0107427.json
- JSON-LD: 52383-1.0107427-ld.json
- RDF/XML (Pretty): 52383-1.0107427-rdf.xml
- RDF/JSON: 52383-1.0107427-rdf.json
- Turtle: 52383-1.0107427-turtle.txt
- N-Triples: 52383-1.0107427-rdf-ntriples.txt
- Original Record: 52383-1.0107427-source.json
- Full Text
- 52383-1.0107427-fulltext.txt
- Citation
- 52383-1.0107427.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:
http://iiif.library.ubc.ca/presentation/dsp.52383.1-0107427/manifest