2023/06/02 by Farzad Pourkamali, Jean Barbier, Pourkamali, Farzad +3 · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #Information Theory (cs.IT) #Quantum Information and Cryptography #Quantum Mechanics and Applications #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2306.01412
openalex publication_date 2023/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The inference of a large symmetric signal-matrix S ∈ ℝN× N corrupted by additive Gaussian noise, is considered for two regimes of growth of the rank M as a function of N. For sub-linear ranks M=Θ(Nα) with α∈(0,1) the mutual information and minimum mean-square error (MMSE) are derived for two classes of signal-matrices: (a) S=XX^\intercal with entries of X∈ℝN× M independent identically distributed; (b) S sampled from a rotationally invariant distribution. Surprisingly, the formulas match the rank-one case. Two efficient algorithms are explored and conjectured to saturate the MMSE when no statistical-to-computational gap is present: (1) Decimation Approximate Message Passing; (2) a spectral algorithm based on a Rotation Invariant Estimator. For linear ranks M=Θ(N) the mutual information is rigorously derived for signal-matrices from a rotationally invariant distribution. Close connections with scalar inference in free probability are uncovered, which allow to deduce a simple formula for the MMSE as an integral involving the limiting spectral measure of the data matrix only. An interesting issue is whether the known information theoretic phase transitions for rank-one, and hence also sub-linear-rank, still persist in linear-rank. Our analysis suggests that only a smoothed-out trace of the transitions persists. Furthermore, the change of behavior between low and truly high-rank regimes only happens at the linear scale α=1.