Skip to main content
release_alert
Welcome to the new Scholars 3.0! Read about new features and let us know what you think.
cancel

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

Publication ,  Conference
Reeves, G; Xu, J; Zadik, I
Published in: 2019 Ieee 8th International Workshop on Computational Advances in Multi Sensor Adaptive Processing, Camsap 2019 Proceedings
December 1, 2019

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.

Duke Scholars

Published In

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

DOI

ISBN

9781728155494

Publication Date

December 1, 2019

Start / End Page

654 / 658
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reeves, G., Xu, J., & Zadik, I. (2019). All-or-Nothing Phenomena: From Single-Letter to High Dimensions. In 2019 Ieee 8th International Workshop on Computational Advances in Multi Sensor Adaptive Processing, Camsap 2019  Proceedings (pp. 654–658). https://doi.org/10.1109/CAMSAP45676.2019.9022473
Reeves, G., J. Xu, and I. Zadik. “All-or-Nothing Phenomena: From Single-Letter to High Dimensions.” In 2019 Ieee 8th International Workshop on Computational Advances in Multi Sensor Adaptive Processing, Camsap 2019  Proceedings, 654–58, 2019. https://doi.org/10.1109/CAMSAP45676.2019.9022473.
Reeves G, Xu J, Zadik I. All-or-Nothing Phenomena: From Single-Letter to High Dimensions. In: 2019 Ieee 8th International Workshop on Computational Advances in Multi Sensor Adaptive Processing, Camsap 2019  Proceedings. 2019. p. 654–8.
Reeves, G., et al. “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, 2019, pp. 654–58. Scopus, doi:10.1109/CAMSAP45676.2019.9022473.
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. 2019. p. 654–658.

Published In

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

DOI

ISBN

9781728155494

Publication Date

December 1, 2019

Start / End Page

654 / 658