TY - JOUR
T1 - The all-or-nothing phenomenon in sparse tensor PCA
AU - Niles-Weed, Jonathan
AU - Zadik, Ilias
N1 - Funding Information:
JNW acknowledges the support of the Institute for Advanced Study, where a portion of this research was conducted. IZ is supported by a CDS Moore-Sloan postdoctoral fellowship.
Publisher Copyright:
© 2020 Neural information processing systems foundation. All rights reserved.
PY - 2020
Y1 - 2020
N2 - We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive gaussian noise, a Gaussian additive model also known as sparse tensor PCA. We show that for Bernoulli and Bernoulli-Rademacher distributed signals and for all sparsity levels which are sublinear in the dimension of the signal, the sparse tensor PCA model exhibits a phase transition called the all-or-nothing phenomenon. This is the property that for some signal-to-noise ratio (SNR) SNRc and any fixed e > 0, if the SNR of the model is below (1 - e) SNRc, then it is impossible to achieve any arbitrarily small constant correlation with the hidden signal, while if the SNR is above (1 + e) SNRc, then it is possible to achieve almost perfect correlation with the hidden signal. The all-or-nothing phenomenon was initially established in the context of sparse linear regression, and over the last year also in the context of sparse 2-tensor (matrix) PCA, Bernoulli group testing and generalized linear models. Our results follow from a more general result showing that for any Gaussian additive model with a discrete uniform prior, the all-or-nothing phenomenon follows as a direct outcome of an appropriately defined “near-orthogonality” property of the support of the prior distribution.
AB - We study the statistical problem of estimating a rank-one sparse tensor corrupted by additive gaussian noise, a Gaussian additive model also known as sparse tensor PCA. We show that for Bernoulli and Bernoulli-Rademacher distributed signals and for all sparsity levels which are sublinear in the dimension of the signal, the sparse tensor PCA model exhibits a phase transition called the all-or-nothing phenomenon. This is the property that for some signal-to-noise ratio (SNR) SNRc and any fixed e > 0, if the SNR of the model is below (1 - e) SNRc, then it is impossible to achieve any arbitrarily small constant correlation with the hidden signal, while if the SNR is above (1 + e) SNRc, then it is possible to achieve almost perfect correlation with the hidden signal. The all-or-nothing phenomenon was initially established in the context of sparse linear regression, and over the last year also in the context of sparse 2-tensor (matrix) PCA, Bernoulli group testing and generalized linear models. Our results follow from a more general result showing that for any Gaussian additive model with a discrete uniform prior, the all-or-nothing phenomenon follows as a direct outcome of an appropriately defined “near-orthogonality” property of the support of the prior distribution.
UR - http://www.scopus.com/inward/record.url?scp=85101427840&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85101427840&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85101427840
SN - 1049-5258
VL - 2020-December
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 34th Conference on Neural Information Processing Systems, NeurIPS 2020
Y2 - 6 December 2020 through 12 December 2020
ER -