2021/11/05 by Flinth, Axel, Roth, Ingo, Groß, Benedikt +2
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2111.03486
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∈ ℝμ is assumed to be s-sparse, and the signal b ∈ ℝn is taken to be σ-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 s2σlog(μ)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σ up to log-factors.