Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

DOI10.1109/TIT.2021.3111992MaRDI QIDQ5032650zbMATH OpenOpenAlexFDO

Authors Lekshmi Ramesh, Chandra R. Murthy, Himanshu Tyagi

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.11247

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Data samples from $mathbb{R}^d$ with a common support of size $k$ are accessed through $m$ random linear projections (measurements) per sample. It is well-known that roughly $k$ measurements from a single sample are sufficient to recover the support. In the multiple sample setting, do $k$ overall measurements still suffice when only $m$ measurements per sample are allowed, with $m<k$? We answer this question in the negative by considering a generative model setting with independent samples drawn from a subgaussian prior. We show that $n=Theta((k^2/m^2)cdotlogk(d-k))$ samples are necessary and sufficient to recover the support exactly. In turn, this shows that when $m<k$, $k$ overall measurements are insufficient for support recovery; instead we need about $m$ measurements each from $k^2/m^2$ samples, i.e., $k^2/m$ overall measurements are necessary.

This page was built for publication: Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032650)