2013 | OriginalPaper | Buchkapitel
Search for Sparse Active Inputs: A Review
verfasst von : Mikhail Malyutov
Erschienen in: Information Theory, Combinatorics, and Search Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The theory of Compressed Sensing (highly popular in recent years) has a close relative that was developed around thirty years earlier and has been almost forgotten since – the design of screening experiments. For both problems, the main assumption is sparsity of active inputs, and the fundamental feature in both theories is the threshold phenomenon: reliable recovery of sparse active inputs is possible when the rate of design is less than the so-called capacity threshold, and impossible with higher rates.
Another close relative of both theories is
multi-access information transmission
. We survey a collection of tight and almost tight screening capacity bounds for both
adaptive
and
non-adaptive
strategies which correspond to either having or not having feedback in information transmission. These bounds are inspired by results from multi-access capacity theory. We also compare these bounds with the simulated performance of two analysis methods: (i) linear programming relaxation methods akin to basis pursuit used in compressed sensing, and (ii) greedy methods of low complexity for both non-adaptive and adaptive strategies.