Paper Info
Title
Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints
Abstract
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 $ \\mathbb {C}^{n}$ , with two subspace constraints of dimensions $m_{1}$ and $m_{2}$ , the required sample complexity is $n\\geq m_{1}m_{2}$ . Then, we impose a sub-band structure on one basis, and derive a sufficient condition that involves a relaxed sample complexity $n\\geq m_{1}+m_{2}-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.
Year
DOI
Venue
2015
10.1109/TIT.2016.2569578
IEEE Trans. Information Theory
Keywords
Field
DocType
Deconvolution,Convolution,Complexity theory,Dictionaries,Subspace constraints,Sparse matrices
Discrete mathematics,Uniqueness,Combinatorics,Blind deconvolution,Subspace topology,Convolution,Identifiability,Deconvolution,Circular convolution,Sparse matrix,Mathematics
Journal
Volume
Issue
ISSN
abs/1505.03399
7
0018-9448
Citations 
PageRank 
References 
13
0.70
14
Authors
3
Name
Order
Citations
PageRank
Yanjun Li1917.47
Kiryung Lee231525.42
Yoram Bresler31104119.17