Reliable Recovery of Hierarchically Sparse Signals for Gaussian and Kronecker Product Measurements

Roth I, Kliesch M, Flinth A, Wunder G, Eisert J (2020)

Publication Type: Journal article

Publication year: 2020

Journal

IEEE Transactions on Signal Processing Institute of Electrical and Electronics Engineers (IEEE)

Book Volume: 68

Pages Range: 4002-4016

Article Number: 9120242

DOI: 10.1109/TSP.2020.3003453

Abstract

We propose and analyze a solution to the problem of recovering a block sparse signal with sparse blocks from linear measurements. Such problems naturally emerge inter alia in the context of mobile communication, in order to meet the scalability and low complexity requirements of massive antenna systems and massive machine-type communication. We introduce a new variant of the Hard Thresholding Pursuit (HTP) algorithm referred to as HiHTP. We provide both a proof of convergence and a recovery guarantee for noisy Gaussian measurements that exhibit an improved asymptotic scaling in terms of the sampling complexity in comparison with the usual HTP algorithm. Furthermore, hierarchically sparse signals and Kronecker product structured measurements naturally arise together in a variety of applications. We establish the efficient reconstruction of hierarchically sparse signals from Kronecker product measurements using the HiHTP algorithm. Additionally, we provide analytical results that connect our recovery conditions to generalized coherence measures. Again, our recovery results exhibit substantial improvement in the asymptotic sampling complexity scaling over the standard setting. Finally, we validate in numerical experiments that for hierarchically sparse signals, HiHTP performs significantly better compared to HTP.

Involved external institutions

Freie Universität Berlin

Germany (DE) Heinrich-Heine-Universität Düsseldorf

Germany (DE) University of Gothenburg / Göteborgs universitet

Sweden (SE)

How to cite

APA:

Roth, I., Kliesch, M., Flinth, A., Wunder, G., & Eisert, J. (2020). Reliable Recovery of Hierarchically Sparse Signals for Gaussian and Kronecker Product Measurements. IEEE Transactions on Signal Processing, 68, 4002-4016. https://dx.doi.org/10.1109/TSP.2020.3003453

MLA:

Roth, Ingo, et al. "Reliable Recovery of Hierarchically Sparse Signals for Gaussian and Kronecker Product Measurements." IEEE Transactions on Signal Processing 68 (2020): 4002-4016.

BibTeX: Download