This website uses cookies to improve your experience. If you continue without changing your settings, you consent to our use of cookies in accordance with our cookie policy. You can disable cookies at any time.

×

Why projection over convex sets works and how to make it better

Authors:

Projection over convex sets (POCS) is one of the most widely used algorithms to interpolate seismic data sets. A formal understanding of the underlying objective function and the associated optimization process is, however, lacking to date in the literature. Here, POCS is shown to be equivalent to the application of the half-quadratic splitting (HQS) method to the L0 norm of an orthonormal projection of the sought after data, constrained on the available traces. Similarly, the apparently heuristic strategy of using a decaying threshold in POCS is revealed to be the result of the continuation strategy that HQS must use to converge to a solution of the minimizer. In light of this theoretical understanding, another methods able to solve this convex optimization problem, namely the Chambolle-Pock primal-dual algorithm, is shown to lead to a new POCS-like method with superior interpolation capabilities at nearly the same computational cost of the industry-standard POCS method.

REFERENCES

  • Abma, R., 2009, Issues in multidimensional interpolation: 79th Annual International Meeting, SEG, Expanded Abstracts, 1152–1156, doi: 10.1190/1.3255056.AbstractGoogle Scholar
  • Abma, R., and N. Kabir, 2006, 3D interpolation of irregular data with a POCS algorithm: Geophysics, 71, no. 6, E91–E97, doi: 10.1190/1.2356088.GPYSA70016-8033AbstractWeb of ScienceGoogle Scholar
  • Boyd, S., 2010, Distributed optimization and statistical learning via the alternating direction method of multipliers: Foundations and Trends in Machine Learning, 3, 1–122, doi: 10.1561/2200000016.CrossrefGoogle Scholar
  • Candes, E., and M. Wakin, 2008, An introduction to compressive sampling: IEEE Signal Processing Magazine, 25, 21–30, doi: 10.1109/MSP.2007.914731.ISPRE61053-5888CrossrefWeb of ScienceGoogle Scholar
  • Chambolle, A., and T. Pock, 2010, A first-order primal-dual algorithm for convex problems with applications to imaging: Journal of Mathematical Imaging and Vision, 40, 120–145, doi: 10.1007/s10851-010-0251-1.CrossrefWeb of ScienceGoogle Scholar
  • Gao, J., A. Stanton, M. Naghizadeh, M. D. Sacchi, and X. Chen, 2012, Convergence improvement and noise attenuation considerations for beyond alias projection onto convex sets reconstruction: Geophysical Prospecting, 61, 138–151, doi: 10.1111/j.1365-2478.2012.01103.x.GPPRAR0016-8025CrossrefWeb of ScienceGoogle Scholar
  • Gao, J.-J., X.-H. Chen, J.-Y. Li, G.-C. Liu, and J. Ma, 2010, Irregular seismic data reconstruction based on exponential threshold model of POCS method: Applied Geophysics, 7, 229–238, doi: 10.1007/s11770-010-0246-5.CrossrefWeb of ScienceGoogle Scholar
  • Ge, Z.-J., J.-Y. Li, S.-L. Pan, and X.-H. Chen, 2015, A fast-convergence POCS seismic denoising and reconstruction method: Applied Geophysics, 12, 169–178, doi: 10.1007/s11770-015-0485-1.CrossrefWeb of ScienceGoogle Scholar
  • Geman, D., and C. Yang, 1995, Nonlinear image recovery with half-quadratic regularization: IEEE Transactions on Image Processing, 4, 932–946, doi: 10.1109/83.392335.IIPRE41057-7149CrossrefWeb of ScienceGoogle Scholar
  • Gerchberg, R. W., 1972, A practical algorithm for the determination of phase from image and diffraction plane pictures: Optik, 35, 237–246.OTIKAJ0030-4026Web of ScienceGoogle Scholar
  • Hennenfent, G., and F. J. Herrmann, 2008, Simply denoise: Wavefield reconstruction via jittered undersampling: Geophysics, 73, no. 3, V19–V28, doi: 10.1190/1.2841038.GPYSA70016-8033AbstractWeb of ScienceGoogle Scholar
  • Menke, W., 1991, Applications of the POCS inversion method to interpolating topography and other geophysical fields: Geophysical Research Letters, 18, 435–438, doi: 10.1029/90GL00343.GPRLAJ0094-8276CrossrefWeb of ScienceGoogle Scholar
  • O’Connor, D., and L. Vandenberghe, 2014, Primal-dual decomposition by operator splitting and applications to image deblurring: SIAM Journal on Imaging Sciences, 7, 1724–1754, doi: 10.1137/13094671X.CrossrefWeb of ScienceGoogle Scholar
  • Parikh, N., 2014, Proximal algorithms: Foundations and Trends in Optimization, 1, 127, doi: 10.1561/2400000003.CrossrefGoogle Scholar
  • Ravasi, M., and I. Vasconcelos, 2020, PyLops — A linear-operator Python library for scalable algebra and optimization: SoftwareX, 11, 100361, doi: 10.1016/j.softx.2019.100361.CrossrefWeb of ScienceGoogle Scholar
  • Wang, B., R.-S. Wu, Y. Geng, and X. Chen, 2014, Dreamlet-based interpolation using POCS method: Journal of Applied Geophysics, 109, 256–265, doi: 10.1016/j.jappgeo.2014.08.008.JAGPEA0926-9851CrossrefWeb of ScienceGoogle Scholar
  • Zhang, H.Zhang, H., J. Zhang, Y. Hao, and B. Wang, 2020, An anti-aliasing POCS interpolation method for regularly undersampled seismic data using curvelet transform: Journal of Applied Geophysics, 172, 103894, doi: 10.1016/j.jappgeo.2019.103894.JAGPEA0926-9851CrossrefWeb of ScienceGoogle Scholar