[talks] 4:30pm Thu Mar 8 talk on sparse recovery over networks in B205

Jennifer Rexford jrex at CS.Princeton.EDU
Thu Mar 8 10:21:27 EST 2012


Speaker: A. Kevin Tang, Cornell University
Title: Sparse Recovery over Networks
Date/time: 4:30pm Thursday, March 8th
Room: E-Quad B-205
Host: Mung Chiang


Given that large scale networks such as the Internet and power grids have
become ever more crucial for our society, it is critical to keep monitoring
states of such networks to avoid possible system failure and to optimize
performance. The scale and complexity of such systems raise the need to quickly
infer component characteristics from a relatively small number of indirect
aggregate measurements.

Motivated by tomography problems in information networks, we first discuss
sparse recovery with graph constraints in the sense that we can take additive
measurements over nodes only if they induce a connected subgraph. We provide
explicit measurement constructions for several special graphs including line,
2-D grid and tree. A general measurement construction algorithm is also
proposed and evaluated. For any given graph G with n nodes, we derive order
optimal upper bounds of the minimum number of measurements needed to recover
any k-sparse vector over G.

Second, to deal with bad data detection in power grids, an iterative mixed L1
and L2 convex programming is used to estimate the true state by locally
linearizing the nonlinear measurements. We give conditions under which the
solution of the iterative algorithm converges to the true state. We also
numerically evaluate our solution to perform bad data detections in nonlinear
electrical power networks problems.

Besides their clear applications, both formulations significantly generalize
the current compressive sensing framework: from complete graph to arbitrary
graph (first part of the talk) and from additive linear measurements to
nonlinear measurements (second part of the talk).


A. Kevin Tang received his undergraduate degree in electronics engineering from
Tsinghua University, Beijing, China, and his Ph.D. in electrical engineering
with a minor in applied and computational mathematics from the California
Institute of Technology. He is currently an Assistant Professor in the School
of Electrical and Computer Engineering at Cornell, where his research interests
focus on control and optimization of various networks, including communication
networks, power networks, and on-chip networks. His recent awards include a
Michael Tien'72 Excellence in Teaching Award from the college of engineering at
Cornell in 2011 and a Young investigator award from the US Air Force's Office
of Scientific Research in 2012.

More information about the talks mailing list