Abstract

The engineering and scientific study of large-scale systems is now a major focus in technology, biology, sociology, and cognitive science. Deciding where, when, what and how to sense or measure is a crucial question in the scientific study of such systems. The most common approaches to experimental design are non-adaptive in the sense that all data are collected prior to analysis and processing. One can envision, however, adaptive strategies in which information gleaned from previously collected data is used to guide the selection of new data. ... In this talk I will discuss the role of adaptive experimental designs in the context large-scale multiple hypothesis testing problems, which are of central importance in the biological sciences today. Formally, consider p independent tests of the form H0: X _{N(0,1) vs. H1: X} N(m,1), for m>0. It is well known reliable decisions are possible only if m, the signal amplitude, exceeds sqrt(2 log p), when p is very large. This is simply because the magnitude of the largest of p independent N(0,1) noises is on the order of sqrt(2 log p). All standard techniques in multiple testing (e.g., Bonferroni, FDR ) are limited by this fact. However, I’ll show that this limitation only exists because all the data are collected prior to testing. What if we could collect and test a bit of data first, then refine our data collection by focusing only on the most promising cases? ... Distilled Sensing (DS) is an adaptive multi-stage experimental design and testing procedure that implements this refinement idea. Given the same experimental budget, DS is capable of reliably detecting far weaker signals than possible from non-adaptive measurements. I’ll show that reliable detection is possible so long as the signal amplitudes exceed any arbitrarily slowly growing function of p. For practical purposes, this means that DS is capable of reliable detection at signal-to-noise ratios that are roughly log(p) weaker than that required by non-adaptive methods. If one were interesting in testing p=10000 genes, for example, then DS can handle noise levels 10 times greater than the limits of non-adaptive methods. This is joint work with J. Haupt and R. Castro. A related manuscript is online at http://arxiv.org/abs/1001.5311.

http://www.ece.wisc.edu/~nowak/