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

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Reeves, G; Xu, J; Zadik, I

Published Date

  • December 1, 2019

Published In

  • 2019 Ieee 8th International Workshop on Computational Advances in Multi Sensor Adaptive Processing, Camsap 2019 Proceedings

Start / End Page

  • 654 - 658

International Standard Book Number 13 (ISBN-13)

  • 9781728155494

Digital Object Identifier (DOI)

  • 10.1109/CAMSAP45676.2019.9022473

Citation Source

  • Scopus