A Caltech Library Service

Hierarchical restricted isometry property for Kronecker product measurements

Roth, Ingo and Flinth, Axel and Kueng, Richard and Eisert, Jens and Wunder, Gerhard (2018) Hierarchical restricted isometry property for Kronecker product measurements. In: 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE , Piscataway, NJ, pp. 632-638. ISBN 978-1-5386-6596-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Hierarchically sparse signals and Kronecker product structured measurements naturally arise in a variety of applications. The simplest example of a hierarchical sparsity structure is two-level (s,σ)-hierarchical sparsity which features s-block-sparse signals with σ-sparse blocks. For a large class of algorithms recovery guarantees can be derived based on the restricted isometry property (RIP) of the measurement matrix and modelbased variants thereof. We show that given two matrices A and B having the standard s-sparse and σ-sparse RIP their Kronecker product A⊗B has two-level (s,σ)hierarchically sparse RIP (HiRIP). This result can be recursively generalized to signals with multiple hierarchical sparsity levels and measurements with multiple Kronecker product factors. As a corollary we establish the efficient reconstruction of hierarchical sparse signals from Kronecker product measurements using the HiHTP algorithm. We argue that Kronecker product measurement matrices allow to design large practical compressed sensing systems that are deterministically certified to reliably recover signals in a stable fashion. We elaborate on their motivation from the perspective of applications.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2018 IEEE. AF acknowledges support from the DFG (Grant KU 1446/18-1) and ANR JCJC OMS, IR and JE by the DFG (SPP 1914 COSIP EI 519/9-1), the Templeton Foundation and the ERC (TAQ), and GW by DFG SPP 1914 COSIP WU 598/8-1, 8-2, the Heisenberg fellowship WU 598/11-1, and the EU H2020 5GPPP project ONE5G (
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)KU 1446/18-1
Agence Nationale pour la Recherche (ANR)UNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)SPP 1914 COSIP EI 519/9-1
John Templeton FoundationUNSPECIFIED
European Research Council (ERC)UNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)SPP 1914 COSIP WU 598/8-1
Deutsche Forschungsgemeinschaft (DFG)WU 598/11-1
European UnionONE5G
Record Number:CaltechAUTHORS:20190328-113742589
Persistent URL:
Official Citation:I. Roth, A. Flinth, R. Kueng, J. Eisert and G. Wunder, "Hierarchical restricted isometry property for Kronecker product measurements," 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 2018, pp. 632-638. doi: 10.1109/ALLERTON.2018.8635829
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94248
Deposited By: Tony Diaz
Deposited On:28 Mar 2019 18:45
Last Modified:16 Nov 2021 17:03

Repository Staff Only: item control page