Statistical limits of spiked tensor models

DOI10.1214/19-AIHP960zbMath1439.62073arXiv1612.07728OpenAlexW3004687303MaRDI QIDQ2179237

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

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

zbMATH Keywords

contiguitysecond moment methodspiked tensor model

Mathematics Subject Classification ID

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

Related Items

An optimal statistical and computational framework for generalized tensor estimation ⋮ Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model ⋮ Inference for low-rank tensors -- no need to debias ⋮ Strong replica symmetry in high-dimensional optimal Bayesian inference ⋮ An information-percolation bound for spin synchronization on general graphs ⋮ Statistical thresholds for tensor PCA ⋮ Free energy subadditivity for symmetric random Hamiltonians ⋮ A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists ⋮ When random tensors meet random matrices ⋮ Bernstein-type bounds for beta distribution ⋮ Long random matrices and tensor unfolding ⋮ High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Phase transition in random tensors with multiple independent spikes ⋮ The all-or-nothing phenomenon in sparse linear regression ⋮ Algorithmic thresholds for tensor PCA ⋮ Unnamed Item ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

Uses Software

• DLMF

Cites Work

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