Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions

DOI10.1109/TIT.2017.2689779zbMATH Open1370.94582arXiv1507.01308OpenAlexW2964036861MaRDI QIDQ5358591FDOQ5358591

Authors: Yanjun Li, Kiryung Lee, Yoram Bresler 

Publication date: 21 September 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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 almost all bases or frames. We showed that for BD of a pair of vectors in $mathbb{C}^n$, with subspace constraints of dimensions $m_1$ and $m_2$, respectively, a sample complexity of $ngeq{m}_1{m}_2$ is sufficient. This result is suboptimal, since the number of degrees of freedom is merely $m_1+m_2-1$. We provided analogus 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 information-theoretic 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 (resp. all pairs) of vectors in $mathbb{C}^n$, with sparsity constraints of sparsity levels $s_1$ and $s_2$, a sample complexity of $n>s_1+s_2$ (resp. $n>2(s_1+s_2)$) 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 the paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.

Full work available at URL: https://arxiv.org/abs/1507.01308

Mathematics Subject Classification ID

Convolutional codes (94B10)

Cited In (11)

• Sufficient output conditions for identifiability in blind equalization
• Multichannel blind deconvolution via maximum likelihood estimator: application in neural recordings
• Blind deconvolution when noise is symmetric: Existence and examples of solutions
• BLIM's identifiability and parameter invariance under backward and forward transformations
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• Identifiability of the deconvolution problem
• Geometry and symmetry in short-and-sparse deconvolution
• $L_1$-Norm Regularization for Short-and-Sparse Blind Deconvolution: Point Source Separability and Region Selection
• Blind deconvolution by a steepest descent algorithm on a quotient manifold
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems

This page was built for publication: Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358591)