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

• 成果类型: Article
• 署名作者: Straszak, Damian; Vishnoi, Nisheeth K.
• 署名单位: Yale University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01644-z
• 发表日期: 2022
• 页码: 685-717
• 关键词: strongly polynomial algorithm; minimization; robust

摘要

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).