Relative Error Tensor Low Rank Approximation

on YouTube ↗52m

" summary

Shows an algorithm that outputs a rank R = O(K^2/ε^2) tensor achieving Frobenius (1+ε) relative error to the best rank-K solution, runs in input-sparsity time NZ(A)+n·poly(K/ε), and yields a true rank-K solution with extra 2^{O(K^2/ε^2)} overhead (fixed-parameter tractable). Technique is an iterative existential sketching using three flattenings and small Gaussian sketches; also gives CUR-style column/row/tube selection, handles other robust norms, and notes border-rank pathologies that require tiny additive slack.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:21What is Tensor?
3. 2:05Matrix Low Rank Approximation (Frobenius Norm)
4. 6:01Tensor Low Rank Approximation (Frobenius Norm)
5. 12:35Real-life Tensor Datasets
6. 14:51Main Question, Tensor Low Rank Approximation
7. 24:36Main Bicriteria Algorithm
8. 26:08Main Rank-k Algorithm
9. 28:03Matrix CUR Decomposition Question
10. 35:18Hardness - Under Exponential Time Hypothesis
11. 41:05iterative Existential Argument

" related talks

• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?Rachel Ward · Optimization, Statistics and Uncertainty
• 01h 09mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 10mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 01h 13mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 46mSpectral Sparsification of GraphsNikhil Srivastava · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)