In this talk, we will discuss the following two problems.
Problem 1. Given independent random samples drawn from an (almost uniform) mixture of at most k spherical d-dimensional Gaussians of unit variance, can we devise an efficient algorithm that recovers the center's within arbitrary accuracy?
Problem 2. How can we integrate in the class of Lipschitz functions on d-dimensional sphere, computationally efficiently?
Efficient algorithms are known to deal with the first problem in the constant dimensions. We show that in the regime d= log k, Fourier analytic ideas can be employed to obtain an efficient algorithm, provided that minimum separation of the center's of the individual Gaussian components is O(✓d). This minimum separation is known to be optimal.
For the second problem, we find a computationally efficient method of finding an equidistributed net on a d-dimensional sphere. The techniques are inspired by work of Landau-Russell (2004) which used ideas from Fourier analysis on finite groups to get a quantitative improvement on the Alon-Roichman theorem that says a random Cayley graph is an expander.
These results are based on joint work with Hariharan Narayanan.
