Identifiability and stability in blind deconvolution under minimal assumptions

Yanjun Li, Kiryung Lee, Yoram Bresler

Research output: Contribution to journalArticlepeer-review


Blind deconvolution (BD) arises in many applications. Without assumptions on the signal and the filter, BD does not admit a unique solution. In practice, subspace or sparsity assumptions have shown the ability to reduce the search space and yield the unique solution. However, existing theoretical analysis on uniqueness in BD is rather limited. In an earlier paper, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in Cn, with subspace constraints of dimensions m1 and m2, respectively, a sample complexity of n ≥ m1m2 is sufficient. This result is suboptimal, since the number of degrees of freedom is merely m1 + m2 - 1. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In this paper, taking advantage of the recent progress on the informationtheoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (respectively, all pairs) of vectors in Cn, with sparsity constraints of sparsity levels s1 and s2, a sample complexity of n > s1+s2 [respectively, n > 2(s1+s2)] is sufficient.We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in this paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.

Original languageEnglish (US)
Article number7890476
Pages (from-to)4619-4633
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2017


  • Bilinear inverse problem
  • low-rank matrix recovery
  • sample complexity
  • sparse recovery
  • uniqueness.

ASJC Scopus subject areas

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


Dive into the research topics of 'Identifiability and stability in blind deconvolution under minimal assumptions'. Together they form a unique fingerprint.

Cite this