Kernel Density Estimation through Density Constrained Near Neighbor Search

Kernel Density Estimation through Density Constrained Near Neighbor Search

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Intro

1 of 28

1 of 28

Intro

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Kernel Density Estimation through Density Constrained Near Neighbor Search

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Kernel Functions
  3. 3 Kernel Density
  4. 4 Motivation
  5. 5 A A Trivial Solution
  6. 6 Analysis of Random Sampling
  7. 7 Prior Work and Our Result
  8. 8 Can we do better than random sampling?
  9. 9 Importance Sampling Estimator
  10. 10 Locality Sensitive Hashing (LSH)
  11. 11 Charikar-Siminelakis'17
  12. 12 Some Simplifying Assumptions
  13. 13 Ideal Importance Sampling
  14. 14 Our Approach
  15. 15 Using Andoni-Indyk LSH for Recovery
  16. 16 Collision Probabilities
  17. 17 Density Constraints
  18. 18 Size of Query's Bucket (Simplified)
  19. 19 Size of Query's Bucket (Detailed)
  20. 20 Query Time
  21. 21 Space
  22. 22 Basics of Data Dependent LSH
  23. 23 General Approach in Data Dependent LSH
  24. 24 Log-Density
  25. 25 Density Evolution of Query's Bucket
  26. 26 Effect of Hashing on Log-Densities
  27. 27 Technical Steps
  28. 28 Open Questions

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.