Optimizing with Tensors
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Reductions show Max‑3SAT and planted‑clique become problems of maximizing a cubic form over unit vectors by encoding clauses or parity into an n×n×n tensor; a constant‑factor maximizer of that cubic recovers a planted clique down to size n^{1/3}. Any tensor admits a low‑rank sum of rank‑one tensors approximating it in spectral norm relative to Frobenius norm, and a polynomial‑time algorithm uses length‑squared sampling to find such an approximation (up to constant factors), yielding PTASes for dense CSPs and metric‑like “c‑dense” matrices. Open problems: tighter tensor algorithms for planted clique and stronger higher‑order relaxations.
AI-written summary · about
chapters (10)
- 0:00Intro
- 2:13Reducing MAX-r-CSP to Tensor Optimization
- 4:57Planted Clique Problem
- 9:26Tensor Optimization - What norms?
- 12:24Tensor Optimization What norms?
- 16:47Norm Maximization for tensors
- 22:36For what CSP's is this good?
- 24:09Generalizing Metrics. Dense problems
- 28:25Moment Tensors
- 30:41Epilogue
related talks
01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
43mGeometric Complexity Theory and Tensor Rank
45mSum of Squares SDP Relaxations on Random Tensors
10mDale Smith, Data Scientist, Nexidia
01h 03mRecent Progress in High-Dimensional Learning
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
52mAverage-Case Overcomplete Tensor Decomposition
53mThe Geometry of the Identifiability of Tensors