High-girth matrices and polarization

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.