Strong Impossibility Results for Sparse Signal Processing

    Authors

    V. Y. F. Tan;G. K. Atia

    Comments

    Authors: contact us about adding a copy of your work at [email protected]

    Abbreviated Journal Title

    IEEE Signal Process. Lett.

    Keywords

    Blowing-up lemma; noisy group testing; sparse signal processing; strong; converse; support set; BOUNDS; Engineering, Electrical & Electronic

    Abstract

    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.

    Journal Title

    Ieee Signal Processing Letters

    Volume

    21

    Issue/Number

    3

    Publication Date

    1-1-2014

    Document Type

    Article

    Language

    English

    First Page

    260

    Last Page

    264

    WOS Identifier

    WOS:000330294300002

    ISSN

    1070-9908

    Share

    COinS
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.