Publications by Galen Reeves.

Papers Published

  1. Reeves, G; Xu, J; Zadik, I, All-or-Nothing Phenomena: From Single-Letter to High Dimensions, 2019 Ieee 8th International Workshop on Computational Advances in Multi Sensor Adaptive Processing, Camsap 2019 Proceedings (December, 2019), pp. 654-658 [doi] .
    (last updated on 2021/04/20)

    Abstract:
    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.