Uniqueness of Tensor Decomposition and Identifiability in Mixture Models

on YouTube ↗47m

" summary

Proves a robust version of Kruskal’s uniqueness: if the robust Kruskal ranks of the factor matrices sum to at least 2r+2, any tensor within ε' (where ε' is polynomially related to ε) has a rank‑r decomposition whose factors are within ε up to permutation. Uses tensor slice inner products, a permutation lemma, sunflower‑style combinatorics and a refined downward induction to replace the usual exponential error blowup with polynomial stability (1/poly noise → 1/poly parameter error). Leaves open a polynomial‑time algorithm under only Kruskal’s condition.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:18Background: "understanding" data
3. 1:01Topic model for documents
4. 3:18What about tensors?
5. 4:27Recipe for tensor methods in mixture models
6. 5:24Two caveats
7. 9:11A success story: the full rank case
8. 15:49Beyond non degeneracy
9. 17:31Kruskal's theorem (1977)
10. 22:07Our result
11. 24:43Remarks
12. 27:03Proof overview
13. 32:13Downward induction: base case SI = (n - 1)
14. 40:09Making things robust - permutation lemma
15. 41:34Issue with inductive proof
16. 43:02Directions

" related talks

• 01h 11mTensor Decompositions: Uniqueness and Smoothed AnalysisMoses Charikar · Semidefinite Optimization, Approximation and Applications 2014
• 01h 03mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 53mTensor Decompositions for Learning Latent Variable Models IIDaniel Hsu · Foundations of Machine Learning Boot Camp 2017
• 52mAverage-Case Overcomplete Tensor DecompositionDavid Steurer · Random Instances and Phase Transitions (Simons Institute, 2016)
• 56mTensor Decompositions for Learning Latent Variable Models IDaniel Hsu · Foundations of Machine Learning Boot Camp 2017
• 43mGeometric Complexity Theory and Tensor RankChristian Ikenmeyer · Geometric Complexity Theory 2014
• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 45mNoisy Estimation of Simultaneously Structured ModelsMaryam Fazel · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)