MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
复制标题
概率低秩矩阵估计的 MMSE：相对于输出通道的普遍性
DOI：
10.1109/allerton.2015.7447070
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
L. Zdeborová
中科院分区：
文献类型：
--
作者：
T. Lesieur;Florent Krzakala;L. Zdeborová
本文考虑了低秩矩阵的概率估计，从其元素的非线性逐元素测量。我们推导出相应的近似消息传递（AMP）算法及其状态演化。依赖于非严格的，但标准的假设，统计物理学的动机，我们的最小均方误差（MMSE）可实现的信息理论和AMP算法的特点。与线性估计的相关问题不同，在本设置中，MMSE仅通过单个参数-其Fisher信息依赖于输出信道。我们说明了这一惊人的发现，通过分析子矩阵本地化，并检测隐藏在一个密集的随机块模型的社区。在这个例子中，我们定位了计算和统计边界，这些边界对于大于4的秩是不相等的。
This paper considers probabilistic estimation of a low-rank matrix from non-linear element-wise measurements of its elements. We derive the corresponding approximate message passing (AMP) algorithm and its state evolution. Relying on non-rigorous but standard assumptions motivated by statistical physics, we characterize the minimum mean squared error (MMSE) achievable information theoretically and with the AMP algorithm. Unlike in related problems of linear estimation, in the present setting the MMSE depends on the output channel only trough a single parameter - its Fisher information. We illustrate this striking finding by analysis of submatrix localization, and of detection of communities hidden in a dense stochastic block model. For this example we locate the computational and statistical boundaries that are not equal for rank larger than four.