Strong Impossibility Results for Sparse Signal Processing
Abbreviated Journal Title
IEEE Signal Process. Lett.
Blowing-up lemma; noisy group testing; sparse signal processing; strong; converse; support set; BOUNDS; Engineering, Electrical & Electronic
This letter derives strong impossibility results for several sparse signal processing problems. It is shown that regardless of the allowed error probability in identifying the salient support set (as long as this probability is below one), the required number of measurements is almost the same as that required for the error probability to be arbitrarily small. Our proof technique involves the use of the blowing-up lemma and can be applied to diverse problems from noisy group testing to graphical model selection as long as the observations are discrete.
Ieee Signal Processing Letters
"Strong Impossibility Results for Sparse Signal Processing" (2014). Faculty Bibliography 2010s. 6159.