Tensor Decompositions: Uniqueness and Smoothed Analysis
summary
Proves a robust analog of Kruskal's theorem so noisy empirical moment tensors yield factor estimates with polynomially related error, and analyzes a smoothed analysis model where worst‑case factor vectors receive small random perturbations. Uses higher moments (collapse 6th‑order into N^2 slices), simultaneous diagonalization of two matrix slices, and standard tensor flattening to recover factors when two modes are full rank. Claims polynomial sample complexity and success with exponentially small failure probability, handling ranks up to roughly N^{(D‑1)/2}.
AI-written summary · about
chapters (15)
- 0:00Low-rank decompositions
- 2:58Kruskal's uniqueness theorem
- 5:17Tensor applications in learning
- 8:36Understanding Kruskal rank
- 12:05Generic tensor properties
- 16:51Robust uniqueness theorems
- 20:26Condition number and stability
- 27:19Computational complexity
- 30:45Tensor methods for learning
- 37:14Identifiability in models
- 40:05Smooth analysis approach
- 45:28Perturbation analysis
- 50:43Common diagonalization algorithm
- 55:10High-rank decomposition challenge
- 59:06Proof strategies and future work
related talks
01h 00mSmoothed Analysis of Tensor Decompositions
58mTensor Decomposition, Sparse Representations and Applications
01h 03mRecent Progress in High-Dimensional Learning
47mUniqueness of Tensor Decomposition and Identifiability in Mixture Models
53mTensor Decompositions for Learning Latent Variable Models II
56mTensor Decompositions for Estimating Latent Variable Models
52mAverage-Case Overcomplete Tensor Decomposition
48mOrthogonal Tensor Decomposition