Clustering a Mixture of Gaussians with Unknown Covariance - Lecture

Explore a comprehensive lecture on clustering Gaussian mixtures with unknown covariance matrices in this 46-minute USC Probability and Statistics Seminar talk by Mateo Díaz from Caltech. Delve into the challenges of a simple clustering problem involving two equally-sized Gaussian components sharing an unknown, potentially ill-conditioned covariance matrix. Learn about the Max-Cut integer program derived from maximum likelihood estimation and its optimal misclassification rate. Discover an efficient iterative algorithm that achieves optimal performance with quadratic sample size, and examine the potential existence of a statistical-computational gap. Gain insights into various aspects of the problem, including statistical metrics, invariance, canonical form, and global convergence guarantees. Analyze numerical illustrations using FashionMNIST dataset and explore related topics such as spectral methods, hard testing problems, and Max-Cut Semidefinite relaxation.

Intro
The problem today
Challenges
How to measure separation?
Statistical metrics
Questions
Previous work: unknown covariance
Numerical illustration: FashionMNIST
Insight: Invariance
Canonical form
Maximum likelihood estimator
Optimality of Max-Cut
Two stage algorithm
Projected power iteration
Spectral algorithm
Global convergence guarantee
A statistical-computational gap?
A hard testing problem
Spectral methods lower bound
A reduction from testing
Max-Cut Semidefinite relaxation
Summary