Greedy Separate Testing Sparse Inputs

Thursday, February 16, 2012 - 3:15pm - 3:45pm
Keller 3-180
Mikhail Malyutov (Northeastern University)
A staggering amount of attention was recently devoted to the study
of compressed sensing and related areas using sparse priors in over
parameterized linear models under versions of linear programming (LP) analysis.
More recently popularity of the sparsity approach for the classical model of
group testing also increased.
The threshold phenomenon was empirically observed in early papers of
Donoho et al : as the dimension of a random instance of a problem
grows there is a sharp transition from successful recovery to failure as a
function of the number of observations versus the dimension and sparsity
of the unknown signal. There are strong parallels between this threshold
behavior and earlier Shannon's justification for similar phenomenon in
terms of the capacity of the information transmission.
We outline sharp asymptotical bounds for general models obtained
by 1979 that were inspired by the Multi-Access Capacity Region
construction that can greatly enhance the current understanding of recovery
of active inputs in sparse compressive sensing. These bounds were obtained for
asymptotically optimal designs which include random designs and
thus imply upper bounds for performance of recovery under arbitrary designs.
These optimal designs are a natural choice in settings where the experiment
can be predesigned, providing in addition a competitive performance of a simplified
analysis method: separate testing of inputs (STI). STI originated in 1959 and can be
further traced back to Fisher's idea of randomization in estimation.
The STI capacity exceeds that of LP relaxation for
randomized designs in a wide range of models and admits several straightforward
generalizations including significantly more powerful and still computationally
feasible greedy version. This will be demonstrated in our simulations.
MSC Code: