Recent Presentations

2010 PASI:

Concentration of measure: fundamentals and tools

Tyrone Vincent, Luis Tenorio and Michael Wakin

Abstract: This talk provides a tutorial covering basic material on concentration inequalities of functions of

independent random variables around their mean. We will start with the inequalities of Markov, Chernoff and

Hoeffding and end with the logarithmic Sobolev inequalities of Ledoux. We will also discuss other inequalities

that apply to Gaussian processes. The focus will be on inequalities that play a role in applications to signal

processing and compressive sensing and thus we will provide examples that show the practical use of the

results.

Applications of concentration of measure in signal processing

Tyrone Vincent, Michael Wakin and Luis Tenorio

Abstract: This talk presents applications of concentration of measure phenomena in the emerging ﬁeld of

Compressive Sensing (CS). CS builds on the premise that a signal having a sparse representation in some

basis can be recovered from a small number of linear measurements of that signal. Many of the most

effective constructions for the linear measurement operator involve random matrices, and at the heart of

much analysis in CS is a precise statistical characterization of the product of a random matrix with a sparse

signal. Building on a simple concentration of measure inequality, for example, it is possible to generalize

the Johnson-Lindenstrauss lemma and ensure an approximate distance-preserving embedding for an entire

family of sparse signals. This ”Restricted Isometry Property” for the measurement operator has been shown

in CS to permit stable recovery of sparse signals from small numbers of measurements. We will also discuss

a related problems in Compressive Signal Processing (CSP), in which the goal is not to recover (high-

complexity question) a sparse signal (low-dimensional model) but rather to answer low-complexity questions

about arbitrary high-dimensional signals. We will discuss how concentration of measure inequalities can be

used to give performance guarantees for problems such as compressive detection and estimation.