Structured Local Optima in Sparse Blind Deconvolution

DOI10.1109/TIT.2019.2940657MaRDI QIDQ5211609zbMATH OpenOpenAlexFDO

Authors

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.00338

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Blind deconvolution is a ubiquitous problem of recovering two unknown signals from their convolution. Unfortunately, this is an ill-posed problem in general. This paper focuses on the {em short and sparse} blind deconvolution problem, where the one unknown signal is short and the other one is sparsely and randomly supported. This variant captures the structure of the unknown signals in several important applications. We assume the short signal to have unit $el{l}^2$ norm and cast the blind deconvolution problem as a nonconvex optimization problem over the sphere. We demonstrate that (i) in a certain region of the sphere, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic short signal of length $k$, when the sparsity of activation signal $hetalesssim{k}^{-2/3}$ and number of measurements $mgtrsimpoly(k)$, a simple initialization method together with a descent algorithm which escapes strict saddle points recovers a near shift truncation of the ground truth kernel.

Cited in

(5)

• Testing that a local optimum of the likelihood is globally optimum using reparameterized embeddings. Applications to wavefront sensing
• Geometry and symmetry in short-and-sparse deconvolution
• Pursuit of a discriminative representation for multiple subspaces via sequential games
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Optimal vintage factor analysis with deflation varimax

This page was built for publication: Structured Local Optima in Sparse Blind Deconvolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211609)