Fast Spectral Algorithms from Sum-of-Squares Analyses

on YouTube ↗39m

" summary

Shows how to turn a degree-6 SOS guarantee for robust order‑4 symmetric tensor decomposition into a near‑linear spectral procedure: assume the square‑reshaping of noise has spectral norm ≤ ε and the tensor is orthogonal rank ≈ N, then SOS certifies vectors with ⟨u_i,v_i⟩^2 ≥ 1−O(ε). Algorithm computes a projection to top‑N eigenvalues of the square reshaping, then a projection to rectangular spectral‑norm ≤1, and recovers one component by random contraction + SVD; runtime is near‑input‑size per component.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to SOS
2. 2:36Limitations and solutions
3. 3:54Fast spectral algorithms
4. 5:55Strategy for speedups
5. 10:29Tensor decomposition basics
6. 15:49Yonnex algorithm
7. 20:04Robust tensor decomposition
8. 26:23SOS relaxation analysis
9. 30:06Fast algorithm implementation

" related talks

• 01h 00mSmoothed Analysis of Tensor DecompositionsAravindan Vijayaraghavan · Tensors in Computer Science and Geometry 2014
• 52mAverage-Case Overcomplete Tensor DecompositionDavid Steurer · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 31mA Positivity-First Approach to Sum-of-Squares Over the HypercubeTim Kunisky · Computational Phase Transitions (Simons Institute, 2020)
• 58mTensor Decomposition, Sparse Representations and ApplicationsBernard Mourrain · Tensors in Computer Science and Geometry 2014
• 45mSum of Squares SDP Relaxations on Random TensorsPrasad Raghavendra · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 11mTensor Decompositions: Uniqueness and Smoothed AnalysisMoses Charikar · Semidefinite Optimization, Approximation and Applications 2014
• 01h 11mOptimization and Sampling Under Symmetry: Part 1 -- ExamplesNisheeth Vishnoi · Geometric Methods in Optimization and Sampling Boot Camp