Theory and Big Data

on YouTube ↗01h 02m

" summary

Argues that linear algebra + randomness actually gives provable wins: computing the best-fit k-subspace via SVD and projecting reduces dimension and often acts as a denoiser, so mixtures of k spherical Gaussians whose means separate by a constant number of standard deviations become learnable from polynomial samples; projection followed by an approximate k-means recovers centers within a few standard deviations. Extends to Max-R-CSPs via low-rank approximations and to tensors by decomposing into 1/epsilon^2 rank‑1 tensors (algorithms randomized and exponential in 1/epsilon); asks for better analyses of row sampling without replacement.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 1:44What Makes an Algorithm Great - Richard Karp
3. 2:36Theme
4. 4:14Data as Vectors
5. 5:53Orthogonality, Volume Sampling
6. 9:05Randomness: Algorithm or Data can toss coins
7. 10:47Bootcamp: Singular Value Decomposition
8. 14:36Applications of SVD- Gaussian Mixtures
9. 19:18Clustering, k-means
10. 21:50Variance of a Clustering
11. 24:38Proiect and Cluster
12. 31:39SVD and Constraint Satisfaction
13. 46:52Norm Maximization for tensors
14. 55:10Teaching Chernoff bounds

" related talks

• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 44mSome Problems of Robust High-dimensional StatisticsGilad Lerman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 34mDimensionally reducing data squeezing out the good stuffAabir Abubaker Kar · PyData DC 2018
• 29mApproximating Spherical Gaussian MixturesAnanda Suresh · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search