Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 67, Issue 12, Pages 8140-8153Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3111992
Keywords
Support recovery; compressed sensing; joint sparsity; sample complexity
Funding
- 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
Recommended
No Data Available