We explore a sharp phase transition known as the "all-or-nothing" phenomenon in estimation problems. This phenomenon arises when there exists a critical signal to noise ratio (SNR) such that below this threshold it is impossible to achieve any positive correlation with the hidden signal, whereas above this threshold it is possible to achieve almost perfect correlation with the hidden signal. This phenomenon has been observed in a few different models and settings, but with no unified explanation. We give a sharp characterization of this phenomenon in the presence of Gaussian noise and give general conditions under which it holds. As a corollary, we obtain the all-or-nothing phenomenon for the sparse tensor PCA theorem, Bernoulli group testing, and the planted Gaussian perceptron problem.

加入 Zoom 会议
https://us02web.zoom.us/j/85713979068?pwd=ckJ2YXlzRStlbnNKMHd1RjBkdDhkQT09
Zoom ID：857 1397 9068
Password：151914