Structured Local Optima in Sparse Blind Deconvolution

Yuqian Zhang, Han Wen Kuo, John Wright

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Blind deconvolution is a ubiquitous problem aiming to recover a convolution kernel a0ϵ R k and an activation signal x0ϵRm from their convolution yϵRm. Unfortunately, this is an ill-posed problem in general. This paper focuses on the short and sparse blind deconvolution problem, where the convolution kernel is short(k<<ll m) and the activation signal is sparsely and randomly supported (|x0|0 << m). This variant captures the structure of the convolutional signals in several important application scenarios. In this paper, we normalize the convolution kernel to have unit Frobenius norm and then cast the blind deconvolution problem as a nonconvex optimization problem over the kernel 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 unit kernel a0, when the sparsity of activation signal satisfies θ ≤ k-2/3 and number of measurements m≥poly (k), the proposed initialization method together with a descent algorithm which escapes strict saddle points recovers some shift truncation of the ground truth kernel.

Original languageEnglish (US)
Article number8830413
Pages (from-to)419-452
Number of pages34
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Blind deconvolution
  • nonconvex optimization


Dive into the research topics of 'Structured Local Optima in Sparse Blind Deconvolution'. Together they form a unique fingerprint.

Cite this