ACHIEVING COMPLEX GLOBAL OBJECTIVES VIA SIMPLE LOCAL RULES: APPLICATIONS IN NETWORKING AND MEDICAL IMAGING
Speaker: Yi Lu , Stanford University
Date: April 13 2009
Time: 3:00PM to 4:00PM
Location: 34-401A - Grier A. Conference Room
Host: Dina Katabi, CSAIL
Contact: Dina Katabi, 617-324-6027, Dina@csail.mit.edu
Abstract: The performance of complex systems depends on joint decision-making by a large number of components. As the system size increases, designs that require global coordination do not scale well, while designs based on just local knowledge perform poorly. Using examples from networking and medical imaging, I will show that global objectives
can be achieved via simple local rules that exchange the right amount of information.
The first application concerns data measurement in networks. Networks collect detailed statistics on the data (bytes, packets, etc) sent by each flow. This requires large and fast memories for housing the counters. However, such memories are prohibitively expensive. We introduce a novel architecture, called Counter Braids, which allows counters to be shared among the flows. While sharing leads to a large reduction in the space requirement, it diffuses flow size information across the entire architecture. A simple, local message passing algorithm subsequently recovers all flow sizes exactly.
Another application concerns the separation of water and fat signals in magnetic resonance imaging (MRI). A key step in this problem is the estimation of the field inhomogeneity map across the whole image from pixel-level observations. The large size of the data has prompted several local algorithms, which suffer from estimation error propagation. We present an algorithm, called JIGSAW, which estimates the field map by spreading pixel-level information via simple local exchanges. It outperforms existing techniques to produce uniform water-fat separation in several challenging and clinically important imaging scenarios.
Bio: Yi Lu is a Ph.D. student in the Electrical Engineering Dept, Stanford University. She is interested in architectures and algorithms for high-performance networks, medical imaging, and inference on graphical models. She is a recipient of the Cisco Stanford Graduate Fellowship and a co-recipient of the Best Paper Award at ACM SIGMETRICS 2008.
See other events that are part of
See other events happening in April 2009
