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.

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

稀疏带宽矩阵估计中的全有或全无统计计算相变