Guaranteed blind deconvolution and demixing via hierarchically sparse reconstruction

Abstract

The blind deconvolution problem amounts to reconstructing both a signal and a filter from the convolution of these two. It constitutes a prominent topic in mathematical and engineering literature. In this work, we analyze a sparse version of the problem: The filter $h\in {\mathbb{R}}^{\mu }$ is assumed to be $s$-sparse, and the signal $b\in {\mathbb{R}}^n$ is taken to be $\sigma$-sparse, both supports being unknown. We observe a convolution between the filter and a linear transformation of the signal. Motivated by practically important multi-user communication applications, we derive a recovery guarantee for the simultaneous demixing and deconvolution setting. We achieve efficient recovery by relaxing the problem to a hierarchical sparse recovery for which we can build on a flexible framework. At the same time, for this we pay the price of some sub-optimal guarantees compared to the number of free parameters of the problem. The signal model we consider is sufficiently general to capture many applications in a number of engineering fields. Despite their practical importance, we provide first rigorous performance guarantees for efficient and simple algorithms for the bi-sparse and generalized demixing setting. We complement our analytical results by presenting results of numerical simulations. We find evidence that the sub-optimal scaling $s^2\sigma \log (\mu )\log (n)$ of our derived sufficient condition is likely overly pessimistic and that the observed performance is better described by a scaling proportional to $s\sigma$ up to log-factors.

arXiv comment6 pages, 5 figures

References in corpus (7)

• A note on the group lasso and a sparse group lasso
• Self-Calibration and Biconvex Compressive Sensing
• C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
• Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements
• Semi-device-dependent blind quantum tomography
• Performance of Hierarchical Sparse Detectors for Massive MTC
• Hierarchical Isometry Properties of Hierarchical Measurements