Recent Progress in High-Dimensional Learning
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28·
summary
Provable algorithms reconstruct mixtures of Airy disks from photon samples: for any fixed K a polynomial-time algorithm recovers centers to accuracy ε given polynomial many photons, using Fourier deconvolution, kernel density estimates and the matrix pencil method on Vandermonde systems. A statistical phase transition at ~1.15–1.53·πσ appears: above ~1.53·πσ a polynomial-time/sample algorithm exists, below ~1.15·πσ information-theoretically requires exp(K) photons. Tools include extremal Beurling–Selberg/Gonçalves constructions and band-limited exponential-sum analysis.
AI-written summary · about
chapters (20)
- 0:00Introduction to the problem
- 1:36Optical systems and blur
- 3:29The diffraction limit debate
- 5:43Defining rigorous limits
- 7:48Historical perspectives on resolution
- 10:58Provable algorithms for Airy disks
- 14:05Phase transition in resolution
- 17:26Experimental considerations
- 19:13Super resolution microscopy
- 23:16Visualizing the diffraction limit
- 26:39Deconvolution techniques
- 28:36Band-limited access analysis
- 32:48Solving the deconvolution problem
- 35:53Matrix pencil method
- 39:54Stability of reconstruction
- 44:18Higher dimensional analysis
- 48:25Extremal functions in 2D
- 52:13Future research and conclusion
- 56:32Q&A: Statistical and computational gaps
- 1:00:56Q&A: Dimensions and thermodynamics
related talks
29mApproximating Spherical Gaussian Mixtures
39mPhase Retrieval in High Dimensions: Statistical and Computational Phase Transitions
01h 31mUnsupervised Learning
12mIterative Methods and High-Dimensional Statistics
35mPhase Retrieval In High Dimensions: Statistical And Computational Phase Transitions
49mSpectral Algorithms for Learning Latent Variable Models
51mTwo Concise Representations for High-Dimensional Visual Data
01h 02mTheory and Big Data