4.5 Article

Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

Journal

IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 67, Issue 12, Pages 8140-8153

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3111992

Keywords

Support recovery; compressed sensing; joint sparsity; sample complexity

Funding

  1. Ministry of Electronics and Information Technology, Government of India

Ask authors/readers for more resources

In the scenario where only m measurements per sample are allowed, a total of k overall measurements are not sufficient for support recovery in a generative model setting with independent samples drawn from a subgaussian prior. Instead, about m measurements each from k(2)/m(2) samples are necessary for accurate support recovery.
Data samples from 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)) . log k(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, and therefore k(2)/m overall measurements are necessary.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available