Fundamental limits of symmetric low-rank matrix estimation
Marc Lelarge、Léo Miolane111M.L. and L.M. are with INRIA-ENS, Paris France, emails: and
Abstract
We consider the high-dimensional inference problem where the signal is a low-rank symmetric matrix which is corrupted by an additive Gaussian noise. Given a probabilistic model for the low-rank matrix, we compute the limit in the large dimension setting for the mutual information between the signal and the observations, as well as the matrix minimum mean square error, while the rank of the signal remains constant. We also show that our model extends beyond the particular case of additive Gaussian noise and we prove an universality result connecting the community detection problem to our Gaussian framework. We unify and generalize a number of recent works on PCA, sparse PCA, submatrix localization or community detection by computing the information-theoretic limits for these problems in the high noise regime. In addition, we show that the posterior distribution of the signal given the observations is characterized by a parameter of the same dimension as the square of the rank of the signal (i.e. scalar in the case of rank one). This allows to locate precisely the information-theoretic thresholds for the above mentioned problems. Finally, we connect our work with the hard but detecta
中文速览
低秩矩阵从高斯噪声中的恢复是机器学习与信号处理的核心难题：给定一个被加性高斯噪声污染的低秩对称矩阵观测值，究竟能在多大程度上还原原始信号？本文从信息论角度出发，严格证明了在高维极限下互信息与矩阵最小均方误差（MMSE）的精确表达式，证实了此前统计物理领域的一个猜想。核心发现是：整个后验分布的几何结构可以被一个标量参数 $q^*(\lambda)$ 完整刻画——它决定了后验样本与真实信号之间的重叠程度，并精确给出了信息论阈值 $\lambda_c$：低于该阈值任何算法都无法优于"瞎猜"，高于该阈值则可有效估计信号。这一统一框架将主成分分析（PCA）、稀疏 PCA、子矩阵定位、社区发现等多个近年热点问题纳入同一体系，并通过普适性定理将结果从高斯信道推广到伯努利信道，意义在于为上述一大类推断问题划定了任何算法都无法逾越的最优性能边界。
原文 arXiv:1611.03888;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1611.03888v3