Skip to main content

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

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

Publication Date

December 1, 2019

Start / End Page

654 / 658