Deconvolution via Convex Programming

In this project we consider using convex optimization to solve the deconvolution problem: estimating a superposition of point sources from samples of the convolution with a known kernel. This problem has many applications, including spectroscopy, neuroscience, geophysics, ultrasound, and optics. Below we depict the true signal, the convolution, and the sampled data for the Ricker wavelet.



In [1] we establish exact recovery guarantees for the Ricker wavelet and the Gaussian kernel under noiseless conditions and prove the approach is robust to dense noise and sparse additive noise. Our dual certificate-based proof requires us to interpolate an arbitrary sign pattern on the spikes using a superposition of kernels centered at the samples. We show this interpolation is always possible if the spikes are sufficiently separated and each spike has a pair of nearby samples. The proof uses a novel technique we call bumps and waves which is depicted below for the Ricker wavelet.



The left image shows a sign pattern on the spikes t_1,t_2,t_3, and weighted Ricker wavelets centered at the 6 samples. The superposition, which we call a dual combination, interpolates the sign pattern +1,-1,+1. In the right image we reparametrize this superposition to bumps and waves centered at each spike. The weights on the bumps and waves are easier to control.

This work was funded by NSF award DMS-1616340.

Papers

Talks

A Sampling Theorem for Deconvolution (video)

  • Ecole des Mines, Paris, June 2017

  • Summer School on Structured Regularization for High-Dimensional Data Analysis, Paris, June 2017

  • 12th International Conference on Sampling Theory and Applications (SampTA), Tallinn (Estonia), July 2017

  • Asilomar Conference on Signals, Systems, and Computers, October 2017