Bisparse blind deconvolution through hierarchical sparse recovery

Abstract The hierarchical sparsity framework , and in particular the HiHTP algorithm(Hierarchical Hard Thresholding Pursuit), has been successfully applied to many relevant communication engineering problems recently, particularly when the signal space is hierarchically structured. In this paper, the applicability of the HiHTP algorithm for solving the bi-sparse blind deconvolution problem is studied. The bi-sparse blind deconvolution setting here consists of recovering $$\varvec{h}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>h</mml:mi> </mml:mrow> </mml:math> and $$\varvec{b}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>b</mml:mi> </mml:mrow> </mml:math> from the knowledge of $$\varvec{h}\varvec{*}\varvec{(Qb)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>h</mml:mi> </mml:mrow> <mml:mrow> <mml:mrow/> <mml:mo>∗</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>Q</mml:mi> <mml:mi>b</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$\varvec{Q}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Q</mml:mi> </mml:mrow> </mml:math> is some linear operator, and both $$\varvec{b}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>b</mml:mi> </mml:mrow> </mml:math> and $$\varvec{h}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>h</mml:mi> </mml:mrow> </mml:math> are assumed to be sparse. The approach rests upon lifting the problem to a linear one, and then applying HiHTP, through the hierarchical sparsity framework . Then, for a Gaussian draw of the random matrix $$\varvec{Q}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Q</mml:mi> </mml:mrow> </mml:math> , it is theoretically shown that an $$\varvec{s}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> </mml:mrow> </mml:math> -sparse $$\varvec{h} \varvec{\in } \varvec{\mathbb {K}}^{\varvec{\mu }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>h</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>∈</mml:mo> </mml:mrow> <mml:msup> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>μ</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> and $$\varvec{\sigma }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> </mml:mrow> </mml:math> -sparse $$\varvec{b} \varvec{\in } \varvec{\mathbb {K}}^{\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>b</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>∈</mml:mo> </mml:mrow> <mml:msup> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> with high probability can be recovered when $$\varvec{\mu } \varvec{\gtrsim } \varvec{s}\, \varvec{\log }\varvec{(s)}^{\varvec{2}}\, \varvec{\log }\varvec{(\mu )}\, \varvec{\log }\varvec{(\mu n)} \varvec{+} \varvec{s}\varvec{\sigma }\, \varvec{\log }\varvec{(n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>μ</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>≳</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>s</mml:mi> </mml:mrow> <mml:mspace/> <mml:mrow> <mml:mo>log</mml:mo> </mml:mrow> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mspace/> <mml:mrow> <mml:mo>log</mml:mo> </mml:mrow>