Nuit Blanche: Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints

Tuesday, May 19, 2015

Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints

Here is some new sample complexity results for blind deconvolution, a certain kind of matrix factorization technique.

Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints by Yanjun Li, Kiryung Lee, Yoram Bresler

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 $n\geq m_1m_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.

Image Credit: NASA/JPL-Caltech
This image was taken by Navcam: Left B (NAV_LEFT_B) onboard NASA's Mars rover Curiosity on Sol 987 (2015-05-17 08:39:24 UTC).
Full Resolution

Join the CompressiveSensing subreddit or the Google+ Community and post there !