Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

DOI10.1145/2897518.2897529zbMath1377.68199arXiv1512.02337OpenAlexW2290522125MaRDI QIDQ5361828

David Steurer, Jonathan Shi, Samuel B. Hopkins, Tselil Schramm

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programming random matrices spectral methods tensor decomposition sparse recovery tensor principal component analysis

Mathematics Subject Classification ID

Semidefinite programming (90C22) Learning and adaptive systems in artificial intelligence (68T05) Random matrices (algebraic aspects) (15B52) Multilinear algebra, tensor calculus (15A69)

Related Items (30)

Disordered systems insights on computational hardness ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Smoothed analysis for tensor methods in unsupervised learning ⋮ On the optimization landscape of tensor decompositions ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Overcomplete Order-3 Tensor Decomposition, Blind Deconvolution, and Gaussian Mixture Models ⋮ Nonconvex Low-Rank Tensor Completion from Noisy Data ⋮ Statistical thresholds for tensor PCA ⋮ Statistical limits of spiked tensor models ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Long random matrices and tensor unfolding ⋮ High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling ⋮ Unnamed Item ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Phase transition in random tensors with multiple independent spikes ⋮ Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling ⋮ Sums of Squares and Sparse Semidefinite Programming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A geometric analysis of phase retrieval ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ The overlap gap property in principal submatrix recovery ⋮ On the computational tractability of statistical estimation on amenable graphs ⋮ Algorithmic thresholds for tensor PCA ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

This page was built for publication: Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors