We determine statistical and computational limits for estimation of a
rank-one matrix (the spike) corrupted by an additive gaussian noise matrix, in
a sparse limit, where the underlying hidden vector (that constructs the
rank-one matrix) has a number of non-zero components that scales sub-linearly
with the total dimension of the vector, and the signal-to-noise ratio tends to
infinity at an appropriate speed. We prove explicit low-dimensional variational
formulas for the asymptotic mutual information between the spike and the
observed noisy matrix and analyze the approximate message passing algorithm in
the sparse regime. For Bernoulli and Bernoulli-Rademacher distributed vectors,
and when the sparsity and signal strength satisfy an appropriate scaling
relation, we find all-or-nothing phase transitions for the asymptotic minimum
and algorithmic mean-square errors. These jump from their maximum possible
value to zero, at well defined signal-to-noise thresholds whose asymptotic
values we determine exactly. In the asymptotic regime the
statistical-to-algorithmic gap diverges indicating that sparse recovery is hard
for approximate message passing.

本文研究在一个稀疏极限下，当底层隐藏向量（构建排名为一的矩阵）非零组成部分数与向量总维数的比例为亚线性，信噪比以适当的速度趋于无穷大时，估计被加性高斯噪声矩阵污染的排名为一的矩阵的统计和计算限制，并证明了渐近互信息的显式低维变分公式，分析了稀疏状态下的近似消息传递算法。对于伯努利和伯努利 - 拉德马赫分布向量，当稀疏度和信号强度满足适当的比例关系时，我们发现渐近最小和算法均方误差的全有或全无相变。在渐近情况下，统计与算法之间的差距发散，表明近似消息传递对于稀疏恢复是非常困难的。