Algorithmic thresholds for tensor PCA

DOI10.1214/19-AOP1415zbMath1444.62080arXiv1808.00921OpenAlexW3044069306MaRDI QIDQ782415

Aukosh Jagannath, Reza Gheissari, Gérard Ben Arous

Publication date: 27 July 2020

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

spin glassesLangevin dynamicsgradient descentfree energy wellsplanted signal recoveryspiked tensor modeltensor estimationtensor principal component analysis (PCA)

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Point estimation (62F10) Parametric inference under constraints (62F30) Markov processes: estimation; hidden Markov models (62M05) Monte Carlo methods (65C05) Applications of stochastic analysis (to PDEs, etc.) (60H30) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44) Applications of functional analysis in probability theory and statistics (46N30)

Related Items (20)

Computational barriers to estimation from low-degree polynomials ⋮ Statistical thresholds for tensor PCA ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Unnamed Item ⋮ Local minima in disordered mean-field ferromagnets ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Random geometric graph: some recent developments and perspectives ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Long random matrices and tensor unfolding ⋮ Shattering versus metastability in spin glasses ⋮ High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ Phase transition in random tensors with multiple independent spikes ⋮ Dynamics of mean field spin glasses on short and long timescales ⋮ Diffusions interacting through a random matrix: universality via stochastic Taylor expansion ⋮ Bounding flows for spherical spin glass dynamics ⋮ The overlap gap property in principal submatrix recovery ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal detection of sparse principal components in high dimension
• 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
• Spectral gap estimates in mean field spin glasses
• The complexity of spherical \(p\)-spin models: a second moment approach
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Large deviations of the extreme eigenvalues of random deformations of matrices
• Statistical limits of spiked tensor models
• Bounding flows for spherical spin glass dynamics
• On the spectral gap of spherical spin glass dynamics
• Phase transition in the spiked random tensor with Rademacher prior
• Complexity of random smooth functions on the high-dimensional sphere
• Large deviations for the largest eigenvalue of rank one deformations of Gaussian ensembles
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Positive definite functions on spheres
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• p> 2 spin glasses with first-order ferromagnetic transitions
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• High-Dimensional Probability
• Random Matrices and Complexity of Spin Glasses
• The Landscape of the Spiked Tensor Model
• 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
• Most Tensor Problems Are NP-Hard

This page was built for publication: Algorithmic thresholds for tensor PCA