Loading [MathJax]/jax/output/CommonHTML/jax.js

The All-or-Nothing Phenomenon in Sparse Tensor PCA

Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

AuthorFeedback Bibtex MetaReview Paper Review Supplemental

Authors

Jonathan Niles-Weed, Ilias Zadik

Abstract

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 \emph{for all} sparsity levels which are sublinear in the dimension of the signal, the sparse tensor PCA model exhibits a phase transition called the \emph{all-or-nothing phenomenon}. This is the property that for some signal-to-noise ratio (SNR) SNRc and any fixed ϵ>0, if the SNR of the model is below (1ϵ)SNRc, then it is impossible to achieve any arbitrarily small constant correlation with the hidden signal, while if the SNR is above (1+ϵ)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 and Bernoulli group testing. 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.