An optimization-based framework for deconvolution: theoretical guarantees and practical algorithms

New York University, New York NY

Investigators

Abstract

Deconvolution is an inverse problem that consists of teasing apart the contributions of different signal sources in data. While these problems are common across the applied sciences, this project will focus on three examples. In neuroscience, recordings of neuron activity using extracellular electrodes measure the action potentials or spikes of adjacent cells. Spike sorting, or equivalently multi-waveform deconvolution, is the problem of identifying the signals corresponding to each cell and deconvolving them to reveal the separate spiking patterns. Super-resolution fluorescence microscopy allows one to obtain images or videos of complex cell structures at high resolution from low-resolution data. In computer vision, blurred pictures, such as ones taken from a cellphone, are well approximated by the convolution of a sharp image with a motion-blur kernel. The aim of this project is to develop and analyze algorithms to tackle these problems, with special emphasis on adapting these methods so that they can be applied efficiently to large amounts of data. Most recent literature on underdetermined linear inverse problems under sparsity constraints focuses on randomized sensing schemes, which do not allow to model convolution problems such as super-resolution, spike sorting in neuroscience, or blind deconvolution in computer vision. The main goal of this project is to develop optimization-based methods for deterministic deconvolution problems, as well as to derive theoretical guarantees on their performance and their robustness to noise. This will require developing novel proof techniques, which do not rely on probabilistic tools, to characterize the conditioning of convolution operators and the optimality conditions of L1-norm minimization problems. Building upon these optimization-based methods, practical algorithms will be designed to operate in big-data regimes where it is not computationally tractable to apply sophisticated processing uniformly across the data.