All-or-Nothing Phenomena: From Single-Letter to High Dimensions

We consider the linear regression problem of estimating a $p$-dimensional vector $\beta$ from $n$ observations $Y=X\beta +W$, where $\beta_j \stackrel{$\text{i.i.d.}$}{\sim} \pi$forareal-valueddistribution$\pi$ with zero mean and unit variance, $X_{ij} \stackrel{$\text{i.i.d.}$}{\sim} $\mathcal{N}$(0,1)$,and$W_i\stackrel{$\text{i.i.d.}$}{\sim} $\mathcal{N}$(0, \sigma^2)$\mathrm{.}Intheasymptoticregimewhere$n/p \to \delta$and$ p/ \sigma^2 \to $\mathsf{s}\mathsf{n}\mathsf{r}$$fortwofixedconstants$\delta, $\mathsf{s}\mathsf{n}\mathsf{r}$\in (0, \infty)$as$p \to \infty$, the limiting (normalized) minimum mean-squared error (MMSE) has been characterized by the MMSE of an associated 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$ in the linear regression problem 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.