This research draws upon techniques from large-scale optimization to develop new decoding algorithms for error-correcting codes. Initial results yield a scalable decoding algorithm for linear programming decoding that runs as fast as state-of-the-art decoders, has a simple schedule, robust convergence guarantees, and achieves better empirical performance than standard decoding algorithms when the signal-to-noise ratio is high. The decoding algorithm will have a transformative effect on the types of codes used in high-reliability applications including storage, optical networks, and microprocessor architectures.
This project will develop further results, analyzing in detail algorithmic behavior in the "error floor regime" where the signal-to-noise ratio is high. It will examine the algorithmic robustness to the specifics of hardware implementation, and investigate other applications in coding such as high-density, non-binary, and rank-metric codes. The PIs will extend the algorithmic methods to applications beyond decoding error-correcting codes, investigating large-scale data processing applications in graphical models and statistical estimation. The research thrusts of the project are well suited for incorporation into the PIs' courses in digital communication, optimization, and information processing for "big data" problems more broadly.
