Bisparse Blind Deconvolution through Hierarchical Sparse Recovery

The bi-sparse blind deconvolution problem is studied -- that is, from the knowledge of $h*(Qb)$, where $Q$ is some linear operator, recovering $h$ and $b$, which are both assumed to be sparse. The approach rests upon lifting the problem to a linear one, and then applying the hierarchical sparsity framework. In particular, the efficient HiHTP algorithm is proposed for performing the recovery. Then, under a random model on the matrix $Q$, it is theoretically shown that an $s$-sparse $h \in \mathbb{K}^\mu$ and $\sigma$-sparse $b \in \mathbb{K}^n$ with high probability can be recovered when $\mu \succcurlyeq s\log(s)^2\log(\mu)\log(\mu n) + s\sigma \log(n)$.