Skip to main content

High-Girth matrices and polarization

Author(s): Abbe, Emmanuel; Wigderson, Y

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAbbe, Emmanuel-
dc.contributor.authorWigderson, Y-
dc.identifier.citationAbbe, E, Wigderson, Y. (2015). High-Girth matrices and polarization. 2015-June (2461 - 2465. doi:10.1109/ISIT.2015.7282898en_US
dc.description.abstractThe girth of a matrix is the least number of linearly dependent columns, in contrast to the rank which is the largest number of linearly independent columns. This paper considers the construction of high-girth matrices, whose probabilistic girth is close to their rank. Random matrices can be used to show the existence of high-girth matrices. This paper uses a recursive construction based on conditional ranks (inspired by polar codes) to obtain a deterministic and efficient construction of high-girth matrices for arbitrary relative ranks. Interestingly, the construction is agnostic to the underlying field and applies to both finite and continuous fields with the same binary matrix. The construction gives in particular the following: (i) over the binary field, high-girth matrices are equivalent to capacity-achieving codes, and our construction turns out to match exactly the BEC polar codes (even at finite block length). It hence gives a different interpretation of BEC polar codes, using the parity-check matrix instead of the generator matrix, and basic linear algebra instead of the mutual information, and generalizes to larger fields; (ii) for the BSC, our construction gives an operational meaning to the Bhattacharyya upper-bound process used in polar codes; (iii) for the reals, it gives an explicit candidate matrix for sparse recovery.en_US
dc.format.extent2461 - 2465en_US
dc.relation.ispartofIEEE International Symposium on Information Theory - Proceedingsen_US
dc.rightsAuthor's manuscripten_US
dc.titleHigh-Girth matrices and polarizationen_US
dc.typeConference Articleen_US

Files in This Item:
File Description SizeFormat 
High-Girth matrices and polarization.pdf254.52 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.