Liu Bie Ju Centre for Mathematical Sciences
City University of Hong Kong
Mathematical Analysis and its Applications
Colloquium

Organized by Prof. Philippe G. Ciarlet and Prof. Roderick Wong

From Discrete Hodge Theory to Finding Sparse Sensor Covers

by
Professor Ali Jadbabaie
Skirkanich Associate Professor of Innovation
Electrical and Systems Engineering Dept. & GRASP Lab
University of Pennsylvania

Date: Dec 11, 2009 (Friday)
Time:4:30 pm to 5:30 pm
Venue: Room B6605 (College Conference Room)
Blue Zone, Level 6, Academic Building
City University of Hong Kong

ABSTRACT: In this talk, I will demonstrate how tools from algebraic topology (specifically homology theory and discrete Hodge theory) can be used to verify coverage in blind (GPS-free) mobile sensor networks in a purely decentralized fashion and without location information. First, I will show that coverage verification questions can be cast in the language of algebraic topology. Using discrete Hodge theory and combinatorial Laplacian operators, I will present an algorithm for decentralized coverage verification. Next, I will use linear programming and l1-norm minimization to search for sparsest generators of homology groups and show that this heuristic for sparsity optimization is in fact exact in certain special cases. Some possible connections to the Compressive Sensing literature will be explored. Finally, I show that the same technique in higher dimensions can be used to find sparse sensor covers by finding sparse generators of second homology groups relative to the boundary, and turning off redundant sensors.

** All interested are welcome **

For enquiry: 2788-9816