### Abstract

The 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 2461-2465 |

Number of pages | 5 |

ISBN (Electronic) | 9781467377041 |

DOIs | |

State | Published - Sep 28 2015 |

Event | IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2015-June |

ISSN (Print) | 2157-8095 |

### Other

Other | IEEE International Symposium on Information Theory, ISIT 2015 |
---|---|

Country | Hong Kong |

City | Hong Kong |

Period | 6/14/15 → 6/19/15 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

## Fingerprint Dive into the research topics of 'High-Girth matrices and polarization'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015*(pp. 2461-2465). [7282898] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282898