Subspace Clustering using Ensembles of K-Subspaces

on YouTube ↗34m

" summary

K-subspaces is NP-hard in worst case, so the practical method draws many random K-subspaces initializations, builds an averaged co-association matrix, thresholds it and runs spectral clustering; that ensemble version (EKSS) is simple to code, consistently lands in the top three on benchmark sets and empirically drops error (e.g. from ~50% to 2% error with 50 runs). Theory proves a one-step variant (EKSS0) has expected affinities that are monotonic functions of absolute inner products and gives guarantees based on an angular separation condition.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 1:17Acknowledgements
3. 3:36Applications
4. 15:05Results
5. 15:42What we know
6. 19:24Intuition
7. 22:17Overview
8. 24:49Random initializations
9. 25:27Onedimensional problems
10. 26:52Angular separation
11. 28:42Clustering Results
12. 29:35Other Algorithms
13. 30:24SSC Results
14. 30:52Summary
15. 31:35Conclusion

" related talks

• 01h 02mTheory and Big DataRavi Kannan · Big Data Boot Camp 2013
• 37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian MixturesPravesh K. Kothari · Computational Phase Transitions (Simons Institute, 2020)
• 55mFoundations of Data Science IIRavi Kannan · Foundations of Data Science Boot Camp 2018
• 28mCertified Sub-Linear Lower Bounds for K-Means ClusteringSoledad Villar · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 00mStreaming Euclidean k-median and k-means with o(log n) SpaceDavid P. Woodruff, Samson Zhou, Vincent Cohen-Addad · Sketching and Algorithm Design 2023
• 35mClustering: A Guide for the PerplexedLeland McInnes, John Healy · PyData DC 2016
• 43mSpectral Approaches to Nearest Neighbor SearchRobert Krauthgamer · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 40mThe Hidden Convexity of Spectral ClusteringLuis Rademacher · Spectral Algorithms: From Theory to Practice 2014