Phase transition in random tensors with multiple spikes

Abstract

This thesis is concerned with the problem of detecting and recovering a low-rank tensor in noise. A spiked random tensor is composed of a symmetric Gaussian p-tensor and a fixed number of spikes. Each spike is a rank one p-tensor formed by a vector whose entries are drawn i.i.d. from a probability measure on the real line with bounded support. Each spike is weighted by a signal-to-noise ratio (SNR). For a random tensor with a single spike, it is possible to detect the presence of the spike when the SNR exceeds a critical threshold, and impossible when the SNR is below this threshold. For a random tensor with multiple spikes, detection of the low-rank structure is possible when the SNR of at least one spike exceeds its critical threshold. Additionally, recovery of the spikes by the minimum mean square error estimator has the same phase transition. When at least one SNR is above its critical threshold, the minimum mean square error estimator performs better than a random guess. It is shown that the spike detection problem is equivalent to distinguishing between the high- and low-temperature regimes of certain mean field spin glass models. The set of SNRs for which detection is impossible is equal to the high-temperature regime of a certain $p$-spin model. Thus the main tools to investigate the detection problem come from the study of spin glasses.