Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints

Yanjun Li, Kiryung Lee, Yoram Bresler

Research output: Contribution to journalArticlepeer-review


Blind deconvolution (BD), the resolution of a signal and a filter given their convolution, arises in many applications. Without further constraints, BD is ill-posed. In practice, subspace or sparsity constraints have been imposed to reduce the search space, and have shown some empirical success. However, the existing theoretical analysis on uniqueness in BD is rather limited. In an effort to address the still open question, we derive sufficient conditions under which two vectors can be uniquely identified from their circular convolution, subject to subspace or sparsity constraints. These sufficient conditions provide the first algebraic sample complexities for BD. We first derive a sufficient condition that applies to almost all bases or frames. For BD of vectors in Cn , with two subspace constraints of dimensions m1 and m2, the required sample complexity is n ≥ m1 m2. Then, we impose a sub-band structure on one basis, and derive a sufficient condition that involves a relaxed sample complexity n≥ m1+m2-1 , which we show to be optimal. We present the extensions of these results to BD with sparsity constraints or mixed constraints, with the sparsity level replacing the subspace dimension. The cost for the unknown support in this case is an extra factor of 2 in the sample complexity.

Original languageEnglish (US)
Article number7470462
Pages (from-to)4266-4275
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2016


  • bilinear inverse problem
  • channel identification
  • equalization
  • multipath channel
  • uniqueness

ASJC Scopus subject areas

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


Dive into the research topics of 'Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints'. Together they form a unique fingerprint.

Cite this