Slime Molds and Sparse Recovery
Date: Tuesday, November 22, 2016
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Aleksander Madry
Contact: Aleksander Madry, firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/424
Speaker URL: None
TALK: Slime Molds and Sparse Recovery
In this talk I will present an algorithmic connection between nature and humans arising in entirely different contexts. The first is the old and famous Iteratively Reweighted Least Squares (IRLS) algorithm to solve the ubiquitous Sparse
Recovery problem while the second is the curious dynamics of a Slime Mold in a maze. Despite its simplicity the convergence of the IRLS has remained a mystery. Our main realization is that the two dynamics are essentially the same. Subsequently, leveraging on this connection and taking inspiration from from the analysis of the Slime Mold dynamics, we derive the first convergence and complexity results for a (damped) version of the IRLS algorithm.
Based on joint works with Damian Straszak.
Created by Aleksander Madry at Monday, November 21, 2016 at 9:17 AM.