Slime Molds and Sparse Recovery

Speaker: Nisheeth Vishnoi , EPFL

Date: Tuesday, November 22, 2016

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G449

Event Type:

Room Description:

Host: Aleksander Madry

Contact: Aleksander Madry, madry@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/424

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) Seminar Series 2016.

Created by Aleksander Madry Email at Monday, November 21, 2016 at 9:17 AM.