Events Calendar

Decomposition Methods for Large Scale LP Decoding

Speaker: Stark Draper, University of Wisconsin, Madison

Talk Title: Decomposition Methods for Large Scale LP Decoding

Abstract: Feldman et al. showed that linear programming (LP) can be used to decode linear error correcting codes. The bit-error-rate performance of LP decoding is comparable to state-of-the- art decoders based on message passing, but has significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this talk we draw on decomposition methods from optimization theory to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a nearly linear time algorithm for two-norm projection onto the parity polytope. This allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently.

Joint work with Siddarth Barman, Xishuo Liu, and Benjamin Recht


Biography: Stark Draper is an Assistant Professor at the University of Wisconsin, Madison. Prior to joining UW he worked at the Misubishi Electric Research Labs (MERL) in Cambridge, MA. He did his graduate work at MIT and postdoctoral work at UC-Berkeley and the University of Toronto. His research interests include communications and information theory, statistical signal processing, optimization, security, and the application of these disciplines to computer architecture.

Host: Prof. Andreas Molisch, molisch@usc.edu, x04670

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos