Published 2010
| Published
Book Section - Chapter
Open
Iterative weighted ℓ_1 Optimization for compressed sensing and coding
Abstract
We introduce a novel algorithm for decoding binary linear codes by linear programming. We build on the LP decoding algorithm of Feldman et al. and introduce a post-processing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity.
Additional Information
©2010 IEEE. This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747 and by Caltech's Lee Center for Advanced Networking.Attached Files
Published - 05757668.pdf
Files
05757668.pdf
Files
(330.2 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:7b0763b2a7a46d1623dc451d1b3e11ca
|
330.2 kB | Preview Download |
Additional details
- Eprint ID
- 55134
- Resolver ID
- CaltechAUTHORS:20150224-074009355
- NSF
- CCF-0729203
- NSF
- CNS-0932428
- NSF
- CCF-1018927
- Office of Naval Research (ONR)
- N00014-08-1-0747
- Caltech's Lee Center for Advanced Networking
- Created
-
2015-02-25Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field