2022/02/09 by TianQi Hou, Yuhao Liu, Hou, TianQi +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #94-08 #Cooperative Communication and Network Coding #DNA and Biological Computing #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2202.04541
openalex publication_date 2022/02/09 · openalex created_date 2022/11/12 · openalex updated_date 2026/07/28
Sparse superposition codes were originally proposed as a capacity-achieving communication scheme over the gaussian channel, whose coding matrices were made of i.i.d. gaussian entries.We extend this coding scheme to more generic ensembles of rotational invariant coding matrices with arbitrary spectrum, which include the gaussian ensemble as a special case. We further introduce and analyse a decoder based on vector approximate message-passing (VAMP).Our main findings, based on both a standard replica symmetric potential theory and state evolution analysis, are the superiority of certain structured ensembles of coding matrices (such as partial row-orthogonal) when compared to i.i.d. matrices, as well as a spectrum-independent upper bound on VAMP's threshold. Most importantly, we derive a simple "spectral criterion " for the scheme to be at the same time capacity-achieving while having the best possible algorithmic threshold, in the "large section size" asymptotic limit. Our results therefore provide practical design principles for the coding matrices in this promising communication scheme.