The rank of sparse random matrices

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book , Other literature type , Preprint , Conference object 01 Jan 2020Embargo end date: 01 Jun 2019 Germany, Germany English Publisher:WileyJournal:Random Structures & Algorithms, volume 62, pages 68-130 (issn: 1042-9832, eissn: 1098-2418,

Copyright policy )Funded by:ARC | Discovery Projects - Gran..., NSF | AF: SMALL: Beyond Worst-C..., ARC | Discovery Early Career Re...

Authors: Amin Coja-Oghlan; Alperen Ali Ergür; Pu Gao; Samuel Hetterich; Maurice Rolvien;

doi: 10.1002/rsa.21085 , 10.1137/1.9781611975994.35 , 10.48550/arxiv.1906.05757 , 10.17877/de290r-24179

arXiv: 1906.05757

The rank of sparse random matrices

- Summary
- Subjects
- Metrics

Abstract

AbstractWe determine the asymptotic normalized rank of a random matrix over an arbitrary field with prescribed numbers of nonzero entries in each row and column. As an application we obtain a formula for the rate of low‐density parity check codes. This formula vindicates a conjecture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations.

Countries

Germany, Germany

Related Organizations

University of Waterloo
Canada
Carnegie Mellon University
United States
Goethe University Frankfurt
Germany
The University of Texas at San Antonio
United States
Johann Wolfgang Goethe-Universitaet
Germany

View all View all

Keywords

ddc:004, FOS: Computer and information sciences, Random matrices (algebraic aspects), Discrete Mathematics (cs.DM), random matrices, 510, Random constraint satisfaction, FOS: Mathematics, Mathematics - Combinatorics, random constraint satisfaction, finite field, ddc:510, sparse matrices, Probability (math.PR), Finite field, Rank, 004, Random matrices (probabilistic aspects), rank, Sparse matrices, Combinatorics (math.CO), Random matrices, 05C80, 60B20, 94B05, Mathematics - Probability, Computer Science - Discrete Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	13
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%