##### Department of Mathematics,

University of California San Diego

****************************

### Math 288 - Probability and Statistics Seminar

## Arian Maleki

#### Rice University

## Fundamental limits of sparse recovery algorithms

##### Abstract:

Compressed sensing refers to a growing body of techniques that `undersample' high-dimensional signals and yet recover them accurately using efficient non-linear reconstruction algorithms. Instead of sampling a signal at a rate proportional to its frequency bandwidth, such techniques use a sampling rate proportional to the `information content' of the signal. There exist several useful theories in the literature that promise improvements over ordinary sampling rules in recovering sparse signals. However, most questions regarding the fundamental performance limits of the recovery algorithms are widely open. Such questions are of particular interest in the applications where we need to design the parameters of the systems in advance. In this talk, I present a new framework that settles such questions for a large class of algorithms including the famous $\ell_1$-penalized least squares (LASSO). As a special case of our result, we will derive tight bounds on the noise sensitivity of the LASSO. Furthermore, I will explain the implications and contributions of the new framework for some applications. This talk is based on a joint work with David Donoho, Iain Johnstone and Andrea Montanari.

Host: Ery Arias-Castro

### February 10, 2012

### 10:00 AM

### AP&M 7321

****************************