Blind Recovery of Sparse Signals From Subsampled Convolution

Kiryung Lee, Yanjun Li, Marius Junge, Yoram Bresler

Research output: Contribution to journalArticlepeer-review


Subsampled blind deconvolution is the recovery of two unknown signals from samples of their convolution. To overcome the ill-posedness of this problem, solutions based on priors tailored to specific practical application have been developed. In particular, sparsity models have provided promising priors. However, in spite of the empirical success of these methods in many applications, existing analyses are rather limited in two main ways: by disparity between the theoretical assumptions on the signal and/or measurement model versus practical setups; or by failure to provide a performance guarantee for parameter values within the optimal regime defined by the information theoretic limits. In particular, it has been shown that a naive sparsity model is not a strong enough prior for identifiability in the blind deconvolution problem. Instead, in addition to sparsity, we adopt a conic constraint, which enforces spectral flatness of the signals. Under this prior together with random dictionary models, we show that the unknown sparse signals can be recovered from samples of their convolution at a rate scaling near optimally with the problem parameters. We also propose an iterative algorithm that is guaranteed to provide robust recovery at the same near optimal sample complexity provided that certain projection steps in the algorithm are successful. In our analysis, we have not verified the success of these projection steps, but these steps are inactive with high probability. Numerical results show the empirical performance of the iterative algorithm agrees with the performance guarantee.

Original languageEnglish (US)
Article number7774998
Pages (from-to)802-821
Number of pages20
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Feb 2017


  • Blind deconvolution
  • alternating minimization
  • compressed sensing
  • sparsity
  • subsampling

ASJC Scopus subject areas

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


Dive into the research topics of 'Blind Recovery of Sparse Signals From Subsampled Convolution'. Together they form a unique fingerprint.

Cite this