Statistical limits of spiked tensor models

DOI10.1214/19-AIHP960zbMATH Open1439.62073arXiv1612.07728OpenAlexW3004687303MaRDI QIDQ2179237FDOQ2179237

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)

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.

Full work available at URL: https://arxiv.org/abs/1612.07728

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

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)

Cites Work

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

Cited In (29)

• 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
• Bernstein-type bounds for beta distribution
• Fundamental limits of symmetric low-rank matrix estimation
• Free energy subadditivity for symmetric random Hamiltonians
• An optimal statistical and computational framework for generalized tensor estimation
• Inference for low-rank tensors -- no need to debias
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• Long random matrices and tensor unfolding
• Mutual information for low-rank even-order symmetric tensor estimation
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Title not available (Why is that?)
• Strong replica symmetry in high-dimensional optimal Bayesian inference
• Phase transition in random tensors with multiple independent spikes
• On the error exponent of a random tensor with orthonormal factor matrices
• Algorithmic thresholds for tensor PCA
• Statistical query lower bounds for tensor PCA
• The all-or-nothing phenomenon in sparse linear regression
• An information-percolation bound for spin synchronization on general graphs
• Statistical thresholds for tensor PCA
• Limiting behavior of largest entry of random tensor constructed by high-dimensional data
• 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

Uses Software

• Digital Library of Mathematical Functions

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)