Videos

Greedy Separate Testing Sparse Inputs

Presenter
February 16, 2012
Keywords:
  • Sparse matrices
MSC:
  • 65F50
Abstract
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.