Applied Math Seminar/Nisheeth Vishnoi, Ecole Polytechnique Federale de Lausanne

Event time: 
Tuesday, November 15, 2016 - 4:15pm
AKW 200 See map
51 Prospect Street
New Haven, CT 06511
Event description: 

Applied Math Semiinar

Speaker: Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne

Refreshments (AKW, 1st Floor Break Area)
4:15 p.m. Seminar (AKW 200)

Title: Slime Molds and Sparse Recovery


We present an algorithmic connection between nature and humans arising in entirely different contexts. The first is the famous Iteratively Reweighted Least Squares (IRLS) algorithm used for the sparse recovery problem while the second is the dynamics of a slime mold. Despite its simplicity the convergence of the IRLS method has been shown only for a certain regularization of it and remains an important open problem. We show that the two dynamics are projections of the same dynamical system in higher dimensions. Subsequently,  we take inspiration from the analysis of the slime mold dynamics to show convergence and obtain complexity bounds for a damped version of the IRLS algorithm.  Joint work with Damian Straszak.