Tata Institute of Fundamental Research
Fourier Analytic Techniques in Machine Learning
PhD Thesis Seminar
Speaker:
Somnath Chakraborty
Organiser:
Hariharan Narayanan
Date:
Wednesday, 12 Jan 2022, 09:00 to 10:00
Venue:
Via Zoom
(Scan to add to calendar)
Abstract:
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.
Join Zoom Meeting
https://zoom.us/j/97251350514?pwd=UVA5aTR4eFlZTVpER2dFRnZoRXJDUT09
Meeting ID: 972 5135 0514
Passcode: 844383
| Speaker: | Somnath Chakraborty |
| Organiser: | Hariharan Narayanan |
| Date: | Wednesday, 12 Jan 2022, 09:00 to 10:00 |
| Venue: | Via Zoom |
(Scan to add to calendar)
Abstract:
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.
Join Zoom Meeting
https://zoom.us/j/97251350514?pwd=UVA5aTR4eFlZTVpER2dFRnZoRXJDUT09
Meeting ID: 972 5135 0514
Passcode: 844383
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.
Join Zoom Meeting
https://zoom.us/j/97251350514?pwd=UVA5aTR4eFlZTVpER2dFRnZoRXJDUT09
Meeting ID: 972 5135 0514
Passcode: 844383