Iteratively reweighted least squares and slime mold dynamics: connection and convergence

We present a connection between two dynamical systems arising in entirely different contexts: the Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing and sparse recovery to find a minimum l(1)-norm solution in an affine space, and the dynamics of a slime mold (Physarum polycephalum) that finds the shortest path in a maze. We elucidate this connection by presenting a new dynamical system - Meta-Algorithm - and showing that the IRLS algorithms and the slime mold dynamics can both be obtained by specializing it to disjoint sets of variables. Subsequently, and building on work on slime mold dynamics for finding shortest paths, we prove convergence and obtain complexity bounds for the Meta-Algorithm that can be viewed as a damped version of the IRLS algorithm. A consequence of this latter result is a slime mold dynamics to solve the undirected transshipment problem that computes a (1 + epsilon)-approximate solution in time polynomial in the size of the input graph, maximum edge cost, and 1/epsilon - a problem that was left open by the work of (Bonifaci V et al. [10] Physarum can compute shortest paths. Kyoto, Japan, pp. 233-240).

Automated summary

This paper explores the connection between the IRLS algorithm and slime mold dynamics, showing that they can be related through a new dynamical system - the Meta-Algorithm. Convergence and complexity bounds for the Meta-Algorithm are proven, providing new possibilities for solving the undirected transshipment problem.