The problem of decomposing a given dataset as superpositions of basic motifs arises from several important applications, including microscopy image analysis, image deblurring. Such motif finding problem can be phrased as ‘"short-and-sparse" blind deconvolution, in which the goal is to recover a short motif (convolution kernel) from its convolution with a random spike train. We assume the kernel to have unit Frobenius norm, and formulate it as a nonconvex optimization problem over the sphere. By analyzing the optimization landscape, we argue that when the target spike train is sufficiently sparse, then on a region of the sphere, every local minimum is equivalent to the ground truth. This geometric characterization implies that efficient methods obtain the ground truth under the same conditions.

This presentation is part of Minisymposium “MS42 - Low dimensional structures in imaging science (3 parts)”
organized by: Wenjing Liao (Georgia Institute of Technology) , Haizhao Yang (Duke University) , Zhizhen Zhao (University of Illinois Urbana-Champaign) .

Authors:

Yuqian Zhang (Columbia University)

Keywords: