讲座名称：Large scale linear programming decoding via the alternating direction method of multipliers
Stark Draper is a Professor of ECE at the University of Toronto (UofT). He received his undergraduate degrees (BS in EE and BA in history) from Stanford University and his MS and PhD degrees in EECS from MIT. He completed postdocs at the University of Toronto and University of California, Berkeley. He then worked at the Mitsubishi Electric Research Labs (MERL). Before returning to Toronto he was an assistant and associate professor at the University of Wisconsin, Madison. Professor Draper’s research interests include information and coding theory, optimization and security, and the application of these disciplines to problems in communications, computing, and learning. Recent industrial collaborations include with Huawei, AMD, Disney Research, and MERL. He chairs the new “Machine Intelligence” major at UofT and serves on the IEEE Information Theory Society Board of Governors. He is spending the 2019-20 academic year on sabbatical visiting the Chinese University of Hong Kong, Shenzhen.
In this talk we apply the alternating direction method of multipliers (ADMM) to solve the linear programming (LP) relaxation of maximum likelihood decoding for error-correction codes in an efficient and parallelizable manner. The core technical innovation is a novel characterization of the parity polytope, the fundamental convex object of interest in relaxations of the constraints of error-correction codes. In comparison to state-of-the art techniques based on message passing, our algorithm has significantly stronger theoretical guarantees. These guarantees are especially pertinent to ultra-high-reliability applications such as optical transport networks. As well as the basic theory and results I will detail our fixed-point implementation in a field-programmable gate array (FPGA).