Average-Case Overcomplete Tensor Decomposition
summary
Presents a concrete algorithmic path: use sum-of-squares pseudo-distributions to “lift third to sixth moments”, enforce a spectral-norm/maximum-entropy constraint, then apply a random-contraction + eigenvector rounding (Jennrich-style). Claims polynomial-time recovery for random overcomplete 3-tensors up to roughly n ≈ d^{1.5} (improving a prior quasi-poly result) with robustness to inverse-polynomial noise; offers a d^{3.33}-time implementation via a low-degree matrix polynomial that successfully reproduces the SoS rounding behavior.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:24Whats the tensor
- 2:18Why should you care
- 11:37Inverse problem
- 13:08Case quorum
- 14:27Injective norm
- 18:37Random vectors
- 27:00Contract
- 29:33General Approach
- 31:17Ideal Implementation
- 32:50Proof of Ideal Implementation
- 35:31Problems with Ideal Implementation
- 38:09Distributions
related talks
58mTensor Decomposition, Sparse Representations and Applications
01h 11mTensor Decompositions: Uniqueness and Smoothed Analysis
01h 00mSmoothed Analysis of Tensor Decompositions
39mFast Spectral Algorithms from Sum-of-Squares Analyses
48mOrthogonal Tensor Decomposition
54mLearning Overcomplete Latent Variable Models through Tensor Power Method
53mTensor Decompositions for Learning Latent Variable Models II
56mTensor Decompositions for Estimating Latent Variable Models