All-or-Nothing Phenomena: From Single-Letter to High Dimensions
We consider the problem of estimating a p -dimensional vector beta from n observations Y=Xbeta+W, where beta-jmathopsimmathrmi.i.d.pi for a real-valued distribution pi with zero mean and unit variance' X-ijmathopsimmathrmi.i.d.mathcalN(0,1), and W-imathopsimmathrmi.i.d.mathcalN(0, sigma2). In the asymptotic regime where n/prightarrowdelta and p/sigma2rightarrow snr for two fixed constants delta, mathsfsnrin(0, infty) as prightarrowinfty, the limiting (normalized) minimum mean-squared error (MMSE) has been characterized by a single-letter (additive Gaussian scalar) channel. In this paper, we show that if the MMSE function of the single-letter channel converges to a step function, then the limiting MMSE of estimating beta converges to a step function which jumps from 1 to 0 at a critical threshold. Moreover, we establish that the limiting mean-squared error of the (MSE-optimal) approximate message passing algorithm also converges to a step function with a larger threshold, providing evidence for the presence of a computational-statistical gap between the two thresholds.
