When talking about slime, I always remember those reports from Marvin Zindler, a local news anchor in the Houston area, who was known for pointing out restaurants with food handling violations. One of those violations included his famous rallying cry "There was slimmmmeeee in the Iiiiiice Machine". Once you hear it, it's difficult to forget the sentence or the intonation. Today, we are mentioning some work that provides some overdue theoretical understanding of the convergence of the IRLS algorithm through the slime mold model mentioned earlier this week. Enjoy !
IRLS and Slime Mold: Equivalence and Convergence by Damian Straszak, Nisheeth K. Vishnoi
In this paper we present a connection between two dynamical systems arising in entirely different contexts: one in signal processing and the other in biology. The first is the famous Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing and sparse recovery while the second is the dynamics of a slime mold (Physarum polycephalum). Both of these dynamics are geared towards finding a minimum l1-norm solution in an affine subspace. 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. Our first result shows that the two dynamics are projections of the same dynamical system in higher dimensions. As a consequence, and building on the recent work on Physarum dynamics, we are able to prove convergence and obtain complexity bounds for a damped version of the IRLS algorithm.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment