Identifiability in Blind Deconvolution With Subspace or Sparsity Constraints

DOI10.1109/TIT.2016.2569578MaRDI QIDQ2976728zbMATH OpenOpenAlexFDO

Authors Yanjun Li, Kiryung Lee, Yoram Bresler

Publication date 28 April 2017

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

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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, existing theoretical analysis on uniqueness in BD is rather limited. As an effort to address the still mysterious 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 blind deconvolution of vectors in $mathbb{C}^n$, with two subspace constraints of dimensions $m_1$ and $m_2$, the required sample complexity is $ngeq{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 $ngeq{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.

Cited in

(15)

• Blind three dimensional deconvolution via convex optimization
• Multichannel blind deconvolution via maximum likelihood estimator: application in neural recordings
• Self-calibration and bilinear inverse problems via linear least squares
• Geometry and symmetry in short-and-sparse deconvolution
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Multi-target detection with application to cryo-electron microscopy
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• The numerics of phase retrieval
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Recent Theoretical Advances in Non-Convex Optimization
• Levenberg-Marquardt hard thresholding pursuit for sparse bilinear inverse problems
• Identifiability of the deconvolution problem

This page was built for publication: Identifiability in Blind Deconvolution With Subspace or Sparsity Constraints

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