SCHEDULE      PARTICIPANTS  VENUE                                                                                                                         Graphical Models, Statistical Inference and Algorithms                                                                        Title:  Optimal Bounds and Algorithms for Support recovery and Approximation in Compressed Sensing. Abstract: In this talk we will motivate several instances of signal  sparsity that not only arise naturally but also by design. These  examples will be drawn from image processing, channel estimation, gene networks, multi-access communications and cognitive radios. We will  then present fundamental information theoretic tradeoffs between SNR,  signal sparsity, sensing diversity, and compression rates for random noisy projections of data. We will show a dichotomy in how noise  enters the system, in particular between measurement noise and process  noise. We show that the former situation leads to significantly larger  compressibility relative to the latter. We show that this result has  fundamental  implications for design and operation of sensor networks.  In the rest of the talk we will describe a novel algorithm based on  thresholding the solution to basis pursuit for support recovery and  approximation.  Our result offers a sharp characterization in that neither the SNR nor  the sparsity ratio can be significantly improved in comparison to the  information theoretic bounds.