IRLS and Slime Mold: Equivalence and Convergence
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.
Code (1)
Tasks
compressed sensingSimilar Papers 제목 키워드 기반
Evolution of the Ubiquitin-Activating Enzyme Uba1 (E1)
Ubiquitin tags diseased proteins and initiates an enzyme conjugation cascade, which has three stages. The first-stage enzyme Uba1 (E1) has evolved only modestly from slime mold to humans, and is > 14 times larger than Ub…
A revised model of fluid transport optimization in Physarum polycephalum
Optimization of fluid transport in the slime mold Physarum polycephalum has been the subject of several modeling efforts in recent literature. Existing models assume that the tube adaptation mechanism in P. polycephalum'…
validEINCASM: Emergent Intelligence in Neural Cellular Automaton Slime Molds
This paper presents EINCASM, a prototype system employing a novel framework for studying emergent intelligence in organisms resembling slime molds. EINCASM evolves neural cellular automata with NEAT to maximize cell grow…
Solving Large Steiner Tree Problems in Graphs for Cost-Efficient Fiber-To-The-Home Network Expansion
The expansion of Fiber-To-The-Home (FTTH) networks creates high costs due to expensive excavation procedures. Optimizing the planning process and minimizing the cost of the earth excavation work therefore lead to large s…
Evolutionary AlgorithmsSteiner Tree ProblemCell pelotons: a model of early evolutionary cell sorting, with application to slime mold D. discoideum
A theoretical model is presented for early evolutionary cell sorting within cellular aggregates. The model involves an energy-saving mechanism and principles of collective self-organization analogous to those observed in…