Statistical limits of spiked tensor models

DOI10.1214/19-AIHP960MaRDI QIDQ2179237zbMATH OpenOpenAlexFDO

Authors Amelia Perry, Alexander S. Wein, Afonso S. Bandeira

Publication date 12 May 2020

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07728, https://projecteuclid.org/euclid.aihp/1580720488

zbMATH Keywords

contiguitysecond moment methodspiked tensor model

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Factor analysis and principal components; correspondence analysis (62H25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Functional limit theorems; invariance principles (60F17)

Abstract: We study the statistical limits of both detecting and estimating a rank-one deformation of a symmetric random Gaussian tensor. We establish upper and lower bounds on the critical signal-to-noise ratio, under a variety of priors for the planted vector: (i) a uniformly sampled unit vector, (ii) i.i.d. $pm1$ entries, and (iii) a sparse vector where a constant fraction $ho$ of entries are i.i.d. $pm1$ and the rest are zero. For each of these cases, our upper and lower bounds match up to a $1+o(1)$ factor as the order $d$ of the tensor becomes large. For sparse signals (iii), our bounds are also asymptotically tight in the sparse limit $hoo0$ for any fixed $d$ (including the $d=2$ case of sparse PCA). Our upper bounds for (i) demonstrate a phenomenon reminiscent of the work of Baik, Ben Arous and P'ech'e: an `eigenvalue' of a perturbed tensor emerges from the bulk at a strictly lower signal-to-noise ratio than when the perturbation itself exceeds the bulk; we quantify the size of this effect. We also provide some general results for larger classes of priors. In particular, the large $d$ asymptotics of the threshold location differs between problems with discrete priors versus continuous priors. Finally, for priors (i) and (ii) we carry out the replica prediction from statistical physics, which is conjectured to give the exact information-theoretic threshold for any fixed $d$. Of independent interest, we introduce a new improvement to the second moment method for contiguity, on which our lower bounds are based. Our technique conditions away from rare `bad' events that depend on interactions between the signal and noise. This enables us to close $sqrt2$-factor gaps present in several previous works.

Recommendations

• Statistical thresholds for tensor PCA
• Phase transition in the spiked random tensor with Rademacher prior
• Phase transition in random tensors with multiple independent spikes
• The landscape of the spiked tensor model
• Algorithmic thresholds for tensor PCA

Cites work

• scientific article; zbMATH DE number 3169867 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1033851 (Why is no real title available?)
• scientific article; zbMATH DE number 1998876 (Why is no real title available?)
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Almost all regular graphs are hamiltonian
• Asymptotic mutual information for the balanced binary stochastic block model
• Asymptotic power of sphericity tests for high-dimensional data
• Broken replica symmetry bounds in the mean field spin glass model
• Catching the \(k\)-NAESAT threshold
• Community detection in dense random networks
• Community detection in sparse random networks
• Exact solution of the gauge symmetric \(p\)-spin glass model on a complete graph
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Free energy of the spherical mean field model
• Fundamental limits of symmetric low-rank matrix estimation
• Going after the \(k\)-SAT threshold
• Information, Physics, and Computation
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
• Locally sub-Gaussian random variables and the strong law of large numbers
• Mutual Information and Minimum Mean-Square Error in Gaussian Channels
• NIST digital library of mathematical functions
• NIST handbook of mathematical functions
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• On the distribution of the largest eigenvalue in principal components analysis
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Random matrices and complexity of spin glasses
• Reconstruction and estimation in the planted partition model
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Tensor decompositions for learning latent variable models
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The Parisi formula
• The asymptotic k-SAT threshold
• The complexity of spherical p-spin models: a second moment approach
• The condensation transition in random hypergraph 2-coloring
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalue of small rank perturbations of Hermitian random matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations

Cited in

(29)

• The landscape of the spiked tensor model
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
• When random tensors meet random matrices
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Fundamental limits of detection in the spiked Wigner model
• Phase transition in the spiked random tensor with Rademacher prior
• Usefulness of signed eigenvalue/vector distributions of random tensors
• Tensor clustering with planted structures: statistical optimality and computational limits
• Fundamental limits of symmetric low-rank matrix estimation
• Bernstein-type bounds for beta distribution
• An optimal statistical and computational framework for generalized tensor estimation
• Inference for low-rank tensors -- no need to debias
• Free energy subadditivity for symmetric random Hamiltonians
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• Mutual information for low-rank even-order symmetric tensor estimation
• Long random matrices and tensor unfolding
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Strong replica symmetry in high-dimensional optimal Bayesian inference
• scientific article; zbMATH DE number 7415122 (Why is no real title available?)
• Phase transition in random tensors with multiple independent spikes
• Algorithmic thresholds for tensor PCA
• On the error exponent of a random tensor with orthonormal factor matrices
• Statistical query lower bounds for tensor PCA
• The all-or-nothing phenomenon in sparse linear regression
• Limiting behavior of largest entry of random tensor constructed by high-dimensional data
• An information-percolation bound for spin synchronization on general graphs
• Statistical thresholds for tensor PCA

Describes a project that uses

Uses Software

• DLMF

This page was built for publication: Statistical limits of spiked tensor models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2179237)